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 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.
www #ad:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Tuesday, 19-Mar-2024 06:57:27 UTC.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.