". . . 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}