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].

let
pair = lambda x. lambda y. x :: y :: nil, {std fns}
fst  = lambda xy. hd xy,
snd  = lambda xy. hd tl xy,

plus  = lambda x. lambda y. x+y, {ops as fns}
minus = lambda x. lambda y. x-y,
times = lambda x. lambda y. x*y,
over  = lambda x. lambda y. x/y,

lt  = lambda x. lambda y. x <  y,
le  = lambda x. lambda y. x <= y,
gt  = lambda x. lambda y. x >  y,
ge  = lambda x. lambda y. x >= y,
eq  = lambda x. lambda y. x =  y,
ne  = lambda x. lambda y. x <> y,

even = lambda n. (n/2)*2=n,
odd  = lambda n. not(even n),

compose = lambda p. lambda q. lambda x.
    p(q x) { i.e. p o q },

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  {the above are just standard list and tree fns}

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

in fib 10  {say}

 

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

 

NB. The applet above needs Java on.

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.