rosetta/fibonacci_sequence.bruijn

Problem description

:import std/Combinator .
:import std/Math .
:import std/List .

# unary/Church fibonacci (moderately fast but very high space complexity)
fib-unary [0 [[[2 0 [2 (1 0)]]]] k i]

:test (fib-unary (+6u)) ((+8u))

# ternary fibonacci using infinite list iteration (very fast)
fib-list \index fibs
	fibs head <$> (iterate &[[0 : (1 + 0)]] ((+0) : (+1)))

:test (fib-list (+6)) ((+8))

# recursive fib (very slow)
fib-rec y [[0 <? (+1) (+0) (0 <? (+2) (+1) rec)]]
	rec (1 --0) + (1 --(--0))

:test (fib-rec (+6)) ((+8))