Lambda Calculus Trees.

LA home
Computing
FP
 λ-calc.
  Intro
  Syntax
  Examples
   Ints
   Bools
   Lists(1)
   arithmetic
   Y (lazy)
   Y (strict)
   Lists(2)
   Trees
   Primes(1)
   Fibonacci(1)
   Unique
   Hamming#s
   Composites
   Fibonacci(2)
   Thue seqs.
   Edit-dist.
   Lists
   Trees
  others
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
foldl BSTadd emptyTree L
 



Reference:
L. Allison, Circular programs and self referential structures. Software Practice and Experience, 19(2), pp.99-109, doi:10.1002/spe.4380190202, Feb 1989.
L. Allison, Applications of Recursively Defined Data Structures, Australian Computer Journal, 25(1), pp.14-20, 1993.
www #ad:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Tuesday, 19-Mar-2024 03:18:01 UTC.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.