Fibonacci function

11 Feb 2015 01:16 by volodymyr.velyky

Graphical lambda calculus representation of an efficient Fibonacci calculator. Input and output are Church-encoded natural numbers.

fib n == first (n next-pair (pair 0 1))

pair x y == \z.zxy

first p == p(\xy.x)

second p == p(\xy.y)

0 == \fx.x

1 == \fx.fx

plus m n == \fx.mf(nfx)

next-pair p == pair (second p) (plus (first p) (second p))

Put this in proper lambdas, and partially evaluate everything you can without n, and here we are.