Making a list of lists in scheme using datatypes and recursion -
i learning scheme , have learned inductive sets , recursion. defined datatype btree binary tree
(define-datatype btree btree? (leaf (datum number?)) (node (value symbol?) (left btree?) (right btree?)))
which works fine. want create function when given btree, return list of paths root (which lists), each of leaves, in left indicated 0 , right indicated 1.
(define btree-path (lambda (tree) (cases btree tree (leaf (datum) '()) (node (value left right) (list (cons 0 (btree-path left)) (cons 1 (btree-path right)))))))
my thought process if sees leaf, returns nothing current list. if node, new list created. in list function called recursively both left , right subtrees cons operator 0 , 1 respectively (meaning on step left , 1 step right). proven wrong result test tree included nested lists. result should ( (0 1) (0 0) (1) ) means there 3 leaves can found going left twice, right once or left , right.
working leaves root not work because not know whether leaf left or right leaf. calling list everytime node found causing nesting. there way can call 2 lists @ same time using 2 recursive calls left , right subtrees? possibly function or operation?
since result of (btree-path left)
(or @ least should be) list of paths left
leaves in subtree, need add 0
each 1 of paths.
likewise right subtree.
the function each element of list map
:
(map (lambda (path) (cons 0 path)) (btree-path left))
next, want merge 2 lists of paths – left , right – 1 list, , function append
.
putting left exercise.
Comments
Post a Comment