## Fibonacci

 LA home Computing FP  λ-calc.   Intro   Syntax   Examples    Ints    Bools    Lists(1)    arithmetic    Y (lazy)    Y (strict)    Lists(2)    Trees    Primes(1)    Fibonacci(1)    Unique    Hamming#s    Composites    Fibonacci(2)    Thue seqs.    Edit-dist.    Fibonacci     Fib'memo-tree  ACJ93
". . . 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=mth 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.