Fibonacci

". . . trees are defined [...] and used as memo-structures to store the results of functions so that later calls can access them quickly without recomputation. In general, one or more functions and structures are defined using mutual recursion. . . ." [1].

fib =
  let rec
    fibtree = fork 1 (fork 1 (build 4) (build 5))
                     (build 3),  { infinite memo-tree }

    build = lambda n. fork (f(n-2)+f(n-1))
                           (build(2*n)) (build(2*n+1)),

    f = lambda n. lookup n elt,    { search memo-tree }

    lookup = lambda n. lambda g.   { O(log n)-time    }
      if n=1 then g fibtree
      else lookup (n/2)
           (compose g (if even n then left else right))
  in f

fibtree:

               1:[1]
                .   .
              .       .
            .           .
          .               .
      2:[1]             3:[2]
       .   .             .   .
      .     .           .     .
     .       .         .       .
  4:[3]   5:[5]     6:[8]   7:[13]
   .   .   .   .     .   .   .   .
  .     . .     .   .     . .     .
8:[21] etc.

key: m:[n] where m=node number & n=m^th Fibonacci number

Some runs, 6/2002:

fib 9:	1414 evals	289 env cells used	17 cells used
fib 10:	1693 evals	343 env cells used	19 cells used
fib 10 + fib 9:	1824 evals	368 env cells used	19 cells used
fib 10 + fib 10:	1824 evals	368 env cells used	19 cells used
fib 10 + fib 11:	2107 evals	422 env cells used	21 cells used

References

[1] L. Allison. Applications of Recursively Defined Data Structures. Australian Computer Journal, 25(1), pp14-20, 1993.