The binary tree consists of nodes each with a number key, and two child
subtrees called left-parent and right-parent.
(require eopl)
(define-datatype tree tree?
[leaf (key number?)]
[node (key number?) (left-parent tree?) (right-parent tree?)])A sample tree using the data structure can be as follows. Here, it has 2 leaf nodes (1, 2), and 1 parent node (3).
(define node-1
(leaf 1))
(define node-2
(leaf 2))
(define root
(node 3 node-1 node-2))This function tree/map returns a new tree by applying unary function f to
each node of tree tr. The base case is a tree with a single leaf, in which
case it applies f to its key. In the recursive case, the tree is a node
with 2 subtrees, so it maps the 2 substrees and applies f to its key.
tree is leaf? -> leaf(f(key)) tree is node? -> node(f(key), map(left), map (right))
; (tree/map f tr): F X TR -> TR
; returns a new tree by applying each node to tr
(define tree/map
(lambda (f tr)
(cases tree tr
(leaf (key)
(leaf (f key)))
(node (key left-parent right-parent)
(node (f key) (tree/map f left-parent) (tree/map f right-parent))))))This function tree/reduce reduces a tree of values to a single value by
applying binary function f to each node of the tree and the reduced value
of its subtree. It takes an initial value init and the tree itself tr.
tree is leaf? -> leaf(f(key, init)) tree is node? -> node(f(key, f(map(left), map(right))))
; (tree/reduce f init tr): F X V X TR -> V
; reduces tree of values to a single value
(define tree/reduce
(lambda (f init tr)
(cases tree tr
(leaf (key)
(f key init))
(node (key left-parent right-parent)
(f key (f (tree/reduce f init left-parent) (tree/reduce f init right-parent)))))))
(define treeduce tree/reduce)
(define reduce tree/reduce)This function tree/filter returns a tree with only those nodes, who themselves
as well as all their parents satisfy the function f, applied to their key.
if a node's key does not satisfy f, both its subtrees are removed and its key set to 0 if a leaf's key does not satisfy f, its key is set to 0
; (tree/filter f tr): F X TR -> TR
; filter part of tree which satisfies f
(define tree/filter
(lambda (f tr)
(cases tree tr
(leaf (key)
(if (f key) (leaf key) (leaf 0)))
(node (key left-parent right-parent)
(if (f key) (node key (tree/filter f left-parent) (tree/filter f right-parent)) (leaf 0))))))This function tree/path returns a list of lefts, rights showing a path to n
in tree tr. It returns #f if no such number is found.
in case of leaf, key=n? -> () else #f in case of node, key=n? -> (), in left subtree -> (left subtree), ...right, else #f
; (tree/path n tr): N X TR -> L
; returns list of lefts, rights showing path to n in tree tr, #f if not found
(define tree/path
(lambda (n tr)
(cases tree tr
(leaf (key)
(if (= key n) (list) #f))
(node (key left-parent right-parent)
(cond
[(= key n) (list)]
[(tree/path n left-parent) (cons `left (tree/path n left-parent))]
[(tree/path n right-parent) (cons `right (tree/path n right-parent))]
[else #f])))))
(define path tree/path)This function is supposed to be able to reverse a list using reduce for lists.
Let a basic reduce implementation for list reduce be as follows:
(base case) lst=null? -> init (indc case) else -> f(lst[0], reduce(lst[1..end]))
; (list/reduce f init lst): F X V X L -> V
; reduces list of values to a single value
(define list/reduce
(lambda (f init lst)
(if (null? lst)
init
(f (car lst) (list/reduce f init (cdr lst))))))How can list/reduce be used to implement list/reverse? Even though
the reduce function picks the elements of the list from the end one by
one, using cons simply results back into the original list. If instead
of plain cons, the picked value is somehow appended to the end of the
working list, the result should be a reversed list.
reduce with plain cons lst=(1 2 3 `4) acc=(4) lst=(1 2 `3 4) acc=(3 4) lst=(1 `2 3 4) acc=(2 3 4)
reduce with append lst=(1 2 3 `4) acc=(4) lst=(1 2 `3 4) acc=(4 3) lst=(1 `2 3 4) acc=(4 3 2)
Say, list append is a function which takes a number n, and a list lst
and appends the value n to the end of the list. Think of this as applying
reduce with cons to a list which only contains n.
construct using each value of list to the value as list
; (list/append n lst): N X L -> L
; appends a value to end of list
(define list/append
(lambda (n lst)
(list/reduce cons (list n) lst)))Now this append function can be used in place of “plain” cons with
reduce and it would be able to reverse the list.
for each value from the end, append it to the list
; (list/reverse lst): L -> L
; reverses the order of elements in a list
(define list/reverse
(lambda (lst)
(list/reduce list/append (list) lst)))
(define reverse list/reverse)The objective here is to write a procedure g such that number-elements
could be defined as:
(define number-elements
(lambda (lst)
(if (null? lst)
'()
(g (list 0 (car lst))
(number-elements (cdr lst))))))It appears that g is behaving as a cons function as well as incrementing
the first value of each pair in list. Let there be a function to increment the
first value of a pair.
; (pair/add1 p): P -> P
; increments first value of pair only
(define pair/add1
(lambda (p)
(cons (add1 (car p)) (cdr p))))A list map function can be used to apply pair/add1 to every pair in the list.
; (list/map f lst): F X L -> L
; applies a function to every element of list
(define list/map
(lambda (f lst)
(if (null? lst)
(list)
(cons (f (car lst)) (list/map f (cdr lst))))))The above map function can be used to increment the first value of all pairs
in the list, and cons the desired value to it finally. This would enable
element numbering.
; (g el lst): E X L -> L
; increment 1st value of all pairs, and return (el . lst)
(define g
(lambda (el lst)
(cons el (list/map pair/add1 lst))))The objective here is to write the bubble sort algorithm without using any assignment. To begin with, lets make sure that the list has atleast 2 elements (or the inverted case, atmost 1 element).
; (atmost1? lst): L -> B
; return #t if list has atmost 1 element(s).
(define atmost1?
(lambda (lst)
(or (null? lst) (null? (cdr lst)))))Now lets use the desired swap function to swap the first 2 elements of the list.
; (swap lst): L -> L
; swaps the first two elements of list
(define swap
(lambda (lst)
(if (atmost1? lst)
lst
(cons (cadr lst) (cons (car lst) (cddr lst)))))); (swap-by lst f): L X F -> L
; swaps the first 2 elements of list using given function
(define swap-by
(lambda (lst f)
(if (or (atmost1? lst) (f (car lst) (cadr lst)))
lst
(swap lst))))Now that we have the ability to conditionally swap two elements in a list, lets write a single pass on bubble sort through the list. This would have the effect of bringing the largest value to the bottom of the list, in case of an ascending sort order.
; (bubble-once-by lst f): L X F -> L
; runs a single pass of bubble sort on list
(define bubble-once-by
(lambda (lst f)
(if (atmost1? lst)
lst
(let ([lst (swap-by lst f)])
(cons (car lst) (bubble-once-by (cdr lst) f))))))Finally, multiple bubblings lead to a completely sorted list.
; (bubble-sort-by lst f): L X F -> L
; bubble sorts a list with given predicate f
(define bubble-sort-by
(lambda (lst f)
(if (atmost1? lst)
lst
(bubble-once-by (cons (car lst) (bubble-sort-by (cdr lst) f)) f))))
; (bubble-sort lst): L -> L
; bubble sorts a list in ascending order
(define bubble-sort
(lambda (lst)
(bubble-sort-by lst <=)))<<tree_defn>>
<<tree_ex>>
<<tree_map>>
<<tree_reduce>>
<<tree_filter>>
<<tree_path>>
<<list_reduce>>
<<list_append>>
<<list_reverse>>
<<pair_add1>>
<<list_map>>
<<g>>
<<atmost1>>
<<swap>>
<<swap_by>>
<<bubble_once_by>>
<<bubble_sort>>