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 parameter, op.
A tree can also be traversed in breadth-first 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 (n-1)
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 data-structure, 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