Fibonacci

LA home
Computing
 Algorithms
 Bioinformatics
 FP,  λ
 Logic,  π
 MML
 Prog.Langs

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

Some runs, 6/2002:
fib 9: 1414 evals289 env cells used17 cells used
fib 10: 1693 evals343 env cells used19 cells used
fib 10 + fib 9: 1824 evals368 env cells used19 cells used
fib 10 + fib 10: 1824 evals368 env cells used19 cells used
fib 10 + fib 11: 2107 evals422 env cells used21 cells used
References
[1] L. Allison. Applications of Recursively Defined Data Structures. Australian Computer Journal, 25(1), pp14-20, 1993.
window on the wide world:

Computer Science Education Week

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite,
ver 3.4+

The GIMP
~ free photoshop
Firefox
web browser
FlashBlock
like it says!

λ ...
:: 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, 21-Nov-2014 09:48:41 EST.