Lambda Calculus Trees. 

Trees are not built into the λinterpreter (they could be) but they can be implemented using lists: fork = lambda e. lambda L. lambda R. { tree ops } e::L::R::nil, leaf = lambda e. e::nil::nil::nil, emptyTree = nil, isEmptyTree = lambda T. null T, elt = lambda T. hd T, left = lambda T. hd tl T, right = lambda T. hd tl tl T To perform infix traversal of a tree, producing a list of values: infix = lambda T. { : Tree e > List e, O(T)time } let rec inf = lambda inT. lambda op. if isEmptyTree inT then op else inf (left inT) (elt inT::inf (right inT) op) in inf T nil Note that function inf above, which does all the work of traversal,
has an accumulating A tree can also be traversed in breadthfirst order. A queue, Q, of trees is used, subtrees being taken off the front of the queue and their children, if any, being added to the other end. BFT = lambda T. { : Tree e > List e } let rec Q = T :: (traverse Q 1), traverse = lambda Q. lambda n. { n is remaining length of Q } if n = 0 then nil else let rec T1 = hd Q, Lf = left T1, Rt = right T1, rest = traverse tl Q in if isEmptyTree Lf then if isEmptyTree Rt then rest (n1) else Rt :: rest n else Lf :: if isEmptyTree Rt then rest n else Rt :: rest (n+1) in if isEmptyTree T then nil else map elt Q Note that the queue datastructure, Q, and the function, traverse, that builds Q are mutually recursive, making this a circular program (Bird 1984, Allison 1989, 1993). A binary search tree can be built from a given list of values: BST = lambda L. { binary search tree of L; both may be infinite } if null L then emptyTree else let hdL = hd L, tlL = tl L in fork hdL (BST (filter (gt hdL) tlL)) (BST (filter (lt hdL) tlL)) An element can be added to an existing binary search tree: BSTadd = lambda T. lambda e. { : Tree e > e > Tree e } if isEmptyTree T then leaf e else let eT = elt T in if e = eT then T else if e < eT then fork eT (BSTadd (left T) e) (right T) else { e > eT } fork eT (left T) (BSTadd (right T) e)and another way to build a binary search tree from a list of values, L, is foldl BSTadd emptyTree L


