Just a small follow-up to the fib function on Optlam.

gistfile1.txt

This is a follow-up to [my previous post](https://gist.github.com/SrVictorMaia/b735f9e06f8461585974).

There is a small remark to make regarding the Fibonacci function. The previous
post takes the premise the "natural" way to encode fib is:

    fib 1 = 1
    fib x = fib (x - 1) + fib (x - 2)

But, lets take a look at the actual recursive schema for the fib sequence:

    f0 = 1
    f1 = (+ 1 1)
    f2 = (+ (+ 1 1) 1)
    f3 = (+ (+ (+ 1 1) 1) (+ 1 1))
    f4 = (+ (+ (+ (+ 1 1) 1) (+ 1 1)) (+ (+ 1 1) 1))

If you analyse it carefully, you can see that:

    f0 = 0
    f1 = 1
    f2 = (+ 1 1)
    f3 = (+ b 1)
    f4 = (+ c b)
    f5 = (+ d c)

Directly encoding that schema as a λ expression, this is what we get:

    fib = (nth -> (nth (fib -> (fib (a b t -> (t (nat.add a b) a)))) (t -> (t 1 0)) (a b -> a)))

That looks scary for the unaccustomed eyes, but it basically says a fib
is the sum of itself with its previous self, starting with (1,0), naturally
capturing the reucursive schema generated by unfolding the fibonacci function. As an
evidence that this is the "natural" definition of fib, look at its size, as
compared to the previous definition:

    new_fib = (λa.(a(λb.(b(λcde.(e(λfg.(cf(dfg)))c))))(λb.(b(λcd.(cd))(λcd.d)))(λbc.b)))

    old_fib = (λa.(a(λbc.(c(λdefg.(bef(b(e(λhi.i)(λhij.(j(λk.(kij)))))fg)))(λdef.(ef))))
        (λb.b)(a(λbcd.(c(λe.(ecd))b))(λbc.(c(λd.(dbc))))(λbc.c)(λbcd.(d(λe.(ecd)))))))

It is not only much shorter, it is possibly **the** shortest fib definition
possible. Now, if instead of adding the fibs, we took a small modulus at each
step (as otherwise the result itself would grow exponentially)...

    mod_fib = (λab.(a(λc.(c(λdef.(f(b(λgh.(g(λi.(h(λjk.(j(ijk)))i))))(λg.(g(λhi.i)))
        (λg.(d(b(λhij.(h(λk.(ikj))))(λh.h)(λhi.(ih)))(e(b(λhij.(h(λk.(ikj))))(λh.h)
        (λhi.(ih)))(b(λhi.h)(λh.h)(λh.h))))))d))))(λc.(c(λde.(de))(λde.e)))(λcd.c)))

Then Optlam would have no problem in computing it linear time. Here is the result
for modulus 13 - that is, (fib(x) = (fib(x-1)+fib(x-2))%13):

mod_fib of 0:
--------------
Result       : 1 (church encoded)
Time         : 0.002s
Stats        : {"iterations":23,"applications":7,"used_memory":1467}


mod_fib of 200:
--------------
Result       : 0 (church encoded)
Time         : 0.015s
Stats        : {"iterations":56851,"applications":28322,"used_memory":78516}


mod_fib of 400:
--------------
Result       : 1 (church encoded)
Time         : 0.023s
Stats        : {"iterations":113367,"applications":56680,"used_memory":156636}


mod_fib of 600:
--------------
Result       : 0 (church encoded)
Time         : 0.029s
Stats        : {"iterations":169889,"applications":84943,"used_memory":234486}


mod_fib of 800:
--------------
Result       : 0 (church encoded)
Time         : 0.049s
Stats        : {"iterations":227851,"applications":113522,"used_memory":312516}


mod_fib of 1000:
--------------
Result       : 1 (church encoded)
Time         : 0.057s
Stats        : {"iterations":283767,"applications":141880,"used_memory":390636}


mod_fib of 1200:
--------------
Result       : 0 (church encoded)
Time         : 0.074s
Stats        : {"iterations":340289,"applications":170143,"used_memory":468486}


mod_fib of 1400:
--------------
Result       : 0 (church encoded)
Time         : 0.078s
Stats        : {"iterations":398851,"applications":198722,"used_memory":546516}


mod_fib of 1600:
--------------
Result       : 1 (church encoded)
Time         : 0.124s
Stats        : {"iterations":454167,"applications":227080,"used_memory":624636}


mod_fib of 1800:
--------------
Result       : 0 (church encoded)
Time         : 0.157s
Stats        : {"iterations":510689,"applications":255343,"used_memory":702486}


mod_fib of 2000:
--------------
Result       : 0 (church encoded)
Time         : 0.152s
Stats        : {"iterations":569851,"applications":283922,"used_memory":780516}


mod_fib of 2200:
--------------
Result       : 1 (church encoded)
Time         : 0.146s
Stats        : {"iterations":624567,"applications":312280,"used_memory":858636}


mod_fib of 2400:
--------------
Result       : 0 (church encoded)
Time         : 0.171s
Stats        : {"iterations":681089,"applications":340543,"used_memory":936486}


mod_fib of 2600:
--------------
Result       : 0 (church encoded)
Time         : 0.188s
Stats        : {"iterations":740851,"applications":369122,"used_memory":1014516}


mod_fib of 2800:
--------------
Result       : 1 (church encoded)
Time         : 0.187s
Stats        : {"iterations":794967,"applications":397480,"used_memory":1092636}


mod_fib of 3000:
--------------
Result       : 0 (church encoded)
Time         : 0.197s
Stats        : {"iterations":851489,"applications":425743,"used_memory":1170486}


mod_fib of 3200:
--------------
Result       : 0 (church encoded)
Time         : 0.223s
Stats        : {"iterations":911851,"applications":454322,"used_memory":1248516}


mod_fib of 3400:
--------------
Result       : 1 (church encoded)
Time         : 0.232s
Stats        : {"iterations":965367,"applications":482680,"used_memory":1326636}


mod_fib of 3600:
--------------
Result       : 0 (church encoded)
Time         : 0.253s
Stats        : {"iterations":1021889,"applications":510943,"used_memory":1404486}


mod_fib of 3800:
--------------
Result       : 0 (church encoded)
Time         : 0.269s
Stats        : {"iterations":1082851,"applications":539522,"used_memory":1482516}


mod_fib of 4000:
--------------
Result       : 1 (church encoded)
Time         : 0.285s
Stats        : {"iterations":1135767,"applications":567880,"used_memory":1560636}


mod_fib of 4200:
--------------
Result       : 0 (church encoded)
Time         : 0.303s
Stats        : {"iterations":1192289,"applications":596143,"used_memory":1638486}


mod_fib of 4400:
--------------
Result       : 0 (church encoded)
Time         : 0.293s
Stats        : {"iterations":1253851,"applications":624722,"used_memory":1716516}


mod_fib of 4600:
--------------
Result       : 1 (church encoded)
Time         : 0.314s
Stats        : {"iterations":1306167,"applications":653080,"used_memory":1794636}


mod_fib of 4800:
--------------
Result       : 0 (church encoded)
Time         : 0.313s
Stats        : {"iterations":1362689,"applications":681343,"used_memory":1872486}


mod_fib of 5000:
--------------
Result       : 0 (church encoded)
Time         : 0.368s
Stats        : {"iterations":1424851,"applications":709922,"used_memory":1950516}


mod_fib of 5200:
--------------
Result       : 1 (church encoded)
Time         : 0.354s
Stats        : {"iterations":1476567,"applications":738280,"used_memory":2028636}


mod_fib of 5400:
--------------
Result       : 0 (church encoded)
Time         : 0.379s
Stats        : {"iterations":1533089,"applications":766543,"used_memory":2106486}


mod_fib of 5600:
--------------
Result       : 0 (church encoded)
Time         : 0.391s
Stats        : {"iterations":1595851,"applications":795122,"used_memory":2184516}


mod_fib of 5800:
--------------
Result       : 1 (church encoded)
Time         : 0.383s
Stats        : {"iterations":1646967,"applications":823480,"used_memory":2262636}


mod_fib o 6000:
--------------
Result       : 0 (church encoded)
Time         : 0.424s
Stats        : {"iterations":1703489,"applications":851743,"used_memory":2340486}