module OpenTheory.Natural.Fibonacci
where
import qualified Data.List as List
import qualified OpenTheory.Primitive.Natural as Natural
import qualified OpenTheory.Stream as Stream
fibonaccis :: [Natural.Natural]
fibonaccis = Stream.unfold (\(p, f) -> (p, (f, p + f))) (0, 1)
decode :: [Bool] -> Natural.Natural
decode =
dest 1 0
where
dest _ _ [] = 0
dest f p (h : t) =
let s = f + p in let n = dest s f t in if h then s + n else n
encode :: Natural.Natural -> [Bool]
encode =
\n -> find n 1 0
where
find n f p = let s = f + p in if n < s then mk [] n f p else find n s f
mk l n f p =
if p == 0 then l
else if f <= n then mk (True : l) (n f) p (f p)
else mk (False : l) n p (f p)
zeckendorf :: [Bool] -> Bool
zeckendorf [] = True
zeckendorf (h : t) =
if List.null t then h else not (h && head t) && zeckendorf t