Repmin

Replace every leaf of a tree by the tree's minimum, in one traversal. The traversal returns the minimum and the rebuilt tree together, and the rebuilt tree's leaves refer to the minimum the same traversal is still computing. It works because the reference is lazy.

The direct program walks the tree twice, once for the minimum and once to rebuild. Bird's version does both in one pass by feeding the pass's own result back into it:^[1]

Bird's program, in Haskell.

data Tree = Leaf Int | Node Tree Tree
 
repmin :: Tree -> Tree
repmin t = t'
  where
    (m, t') = go t
    go (Leaf n)   = (n, Leaf m)
    go (Node l r) = let (a, l') = go l
                        (b, r') = go r
                    in (min a b, Node l' r')

go never inspects m; it only stores it in the new leaves. By the time anything reads a leaf, go has returned and m is known. m depends on the output of go, which depends on m, and the cycle is harmless because nothing on it is demanded before it exists.

In OCaml the knot is tied by hand: the leaves hold a suspension, and a recursive lazy value closes the loop.

type tree = Leaf of int | Node of tree * tree
 
(* The result's leaves hold a suspended minimum, forced only when read. *)
type rtree = RLeaf of int Lazy.t | RNode of rtree * rtree
 
(* One pass returns the minimum of a subtree and the rebuilt subtree, whose
   leaves all point at m: the minimum of the whole tree, which is only
   known once this same pass has finished. *)
let repmin t =
  let rec go m = function
    | Leaf n -> (n, RLeaf m)
    | Node (l, r) ->
        let a, l' = go m l in
        let b, r' = go m r in
        (min a b, RNode (l', r'))
  in
  let rec result = lazy (go (lazy (fst (Lazy.force result))) t) in
  snd (Lazy.force result)
 
let rec show = function
  | RLeaf m -> string_of_int (Lazy.force m)
  | RNode (l, r) -> "(" ^ show l ^ " " ^ show r ^ ")"

Running it.

repmin ((5 2) (8 (3 7)))  ->  ((2 2) (2 (2 2)))

Forcing a leaf before the pass has finished raises Lazy.Undefined, which is how a strict language reports a circular dependency that a lazy one would have sent into a loop.

The same program is an attribute grammar: the minimum is a synthesized attribute, computed bottom-up, and its value at the leaves an inherited one, passed top-down. Circular programs are how a lazy language evaluates such grammars in a single traversal.