Trees

Trees are not built into the λ-interpreter (they could be) but they can be implemented using lists to give 'fork', 'leaf', 'emptyTree', 'elt', 'left' and 'right', 'infix' and breadth-first 'BFT' tree traversals, and to create a binary search tree 'BST'.

let {scroll down!}
cons = lambda H. lambda T. H::T {constructor fn},
lt = lambda x. lambda y. x < y,
gt = lambda x. lambda y. x > y,

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

in let rec
map = lambda f. lambda L.
  {[f L1, f L2, ..., f Ln]}
  if null L then nil
  else (f hd L)::(map f tl L),

filter = lambda p. lambda L.
{those elements of L that satisfy p}
  if null L then nil
  else let hdL = hd L in
  if p hdL then hdL::(filter p tl L)
  else filter p tl L,

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,

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,

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)),

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)

in BFT (BST (2::1::2::4::1::3::4::3::nil))

Note that the queue, 'Q', inside 'BFT' (breadth-first traversal) is a recursively defined list, a data-structure, making this an example of a circular program [All89,All93] (corecursion).

There are more λ-calculus examples here.

References

[All89] Lloyd Allison, 'Circular Programs and Self-Referential Structures', Software Practice & Experience, 19(2), pp.99-109, doi:10.1002/spe.4380190202, arxiv:2403.01866, February 1989.
[All93] Lloyd Allison, 'Applications of Recursively Defined Data Structures', Australian Computer Journal, 25(1), pp.14-20, arxiv:2206.12795, 1993.
And other publications.