Logic and Proof Exercise 17.19 Haskell solution

logic_and_proof_ch17_ex19.hs

-- Logic and Proof Exercise 17.19
-- Finds an increasing list of Fibonacci numbers that sum to the given natural number.
-- The algorithm is linear in the input number, and tail recursive.

main = mapM_ print $ map fibsSummingTo [0..100]

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

fibsSummingTo :: Integer -> [Integer]
fibsSummingTo n = loop n ltFibs []
    where
        ltFibs = reverse $ takeWhile (<= n) fibs
        loop :: Integer -> [Integer] -> [Integer] -> [Integer]
        loop targ remFibs acc =
            let hd : tl = remFibs in
                case compare hd targ of
                    EQ -> hd : acc
                    GT -> loop targ tl acc
                    LT -> loop (targ - hd) tl (hd : acc)