## Fibonacci

 home1 home2  Bib  Algorithms  Bioinfo  FP  Logic  MML  Prog.Lang and the  Book

FP
Lambda
Introduction
Examples
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].

 ```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=mth Fibonacci number
 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 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 { Fibonacci numbers, memo-tree by circular program } { 1 1 2 3 5 8 13 21 34 55... }
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.
 Coding Ockham's Razor, L. Allison, Springer A Practical Introduction to Denotational Semantics, L. Allison, CUP

 Linux  Ubuntu free op. sys. OpenOffice free office suite The GIMP ~ free photoshop Firefox web browser

λ ...
 :: list cons nil the [ ] list null predicate hd head (1st) tl tail (rest)

 © L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated), Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University, was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.) Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Friday, 01-Mar-2024 15:49:03 AEDT.