module Fibonacci where

-- Liste der Fibonacci-Zahlen
fibs :: [Int]
fibs@(_:xs) = 0:1:zipWith (+) fibs xs

fib :: Int -> Int
fib = (fibs !!)

-- Zeckendorf-Sequenzen als Umformungsvorschrift
zecks :: [[Bool]]
zecks = []:map makeZeck zecks where
  makeZeck (True:xs)            =  False:      makeZeck xs
  makeZeck (False:x@(False:xs)) =  True :               x
  makeZeck (False:True:xs)      =  False:False:makeZeck xs
  makeZeck []                   = [True ]

-- Zeckendorf-Sequenzen als Algorithmus
zeck' :: Int -> [Bool]
zeck' n = zeck_ n (lower_fib n) where
  zfib         = (fibs!!).(2+)
  lower_fib 0  = -1
  lower_fib n  = lower_fib' 0 n
  lower_fib' n k | zfib n >= k = n
                 | otherwise   = lower_fib' (n+1) k
  zeck_ _ (-1) = []
  zeck_ n k      | n < zfib k  = zeck_ n (k-1) ++ [False]
	             | otherwise   = zeck_ (n-zfib k) (k-1) ++ [True]

zecks' :: [[Bool]]
zecks' = map zeck' [0..]

zeck :: Int -> [Bool]
zeck = (zecks !!)

unzeck :: [Bool] -> Int
unzeck = unzeck' (drop 2 fibs) 0 where
  unzeck' (f:fs) n (True :zs) = unzeck' fs (n+f) zs
  unzeck' (_:fs) n (False:zs) = unzeck' fs  n    zs
  unzeck'  _     n [        ] =             n
  unzeck'  []    _ _          = error "Fibonaccis alle ;-)"