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]

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.

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 ^ ")"

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.

• HylomorphismA function that unfolds a seed into a recursive structure and folds that structure into a result, written so the structure is never built: hylo f g = f . fmap (hylo f g) . g. The call tree of the recursion is the intermediate structure.
• ZipperA zipper represents a data structure together with a focus, a position inside it: the substructure at the focus, and the path from the focus back to the root together with everything to either side of that path. Moving the focus one step and editing at the focus take constant time, and the structure is persistent, so edits share everything off the path. The type of paths is the derivative of the structure's type, in the sense of calculus.
• Lazy evaluationLazy evaluation, or call-by-need, delays computing an expression until its value is needed and then remembers the value, so it is computed at most once. It lets programs define infinite structures and consume only part of them, separates generating candidate values from choosing among them, and avoids work whose result is never used. Its costs are the memory held by unevaluated suspensions, which can cause space leaks, and harder reasoning about when work happens. Haskell is lazy by default; OCaml provides it explicitly through Lazy.t and Seq.

1. [1]R. S. Bird, “Using circular programs to eliminate multiple traversals of data”, Acta Informatica 21 (1984).
2. [2]T. Johnsson, “Attribute grammars as a functional programming paradigm”, FPCA (1987).

last updated 27 September 2026