CODEWITHSUNDEEP
haskellrecursionlazy-evaluation
jvans
jvans

Reputation: 2915

foldr not returning with an infinite list

I've read https://www.haskell.org/haskellwiki/Foldl_as_foldr and a few other blog posts about the difference between foldl and foldr. Now I'm trying to write the fibonacci sequence as an infinite list with a foldr and I've come up with the following solution:

fibs2 :: [Integer]
fibs2 = foldr buildFibs [] [1..]
  where
    buildFibs :: Integer -> [Integer] -> [Integer]
    buildFibs _ [] = [0]
    buildFibs _ [0] = [1,0]
    buildFibs _ l@(x:s:z) = (x + s):l

But when I do take 3 fibs2, the function doesn't return. I thought foldr being body recursive allows for you to use it with infinite lists in these types of situation. Why won't this work with my solution?

Upvotes: 1

Views: 126

Answers (2)

bheklilr
bheklilr

Reputation: 54058

This is a great exercise for equational reasoning:

fibs2 = foldr buildFibs [] [1..]

foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

foldr buildFibs [] [1..] =
    buildFibs 1 (foldr buildFibs [] [2..]) =
    buildFibs 1 (buildFibs 2 (foldr buildFibs [] [3..])) =
    buildFibs 1 (buildFibs 2 (buildFibs 3 (foldr buildFibs [] [4..]))) =
    ...

I hope by now you can see the problem: foldr is trying to traverse the entire list before returning. What happens if we were to use foldl instead?

foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

buildFibs' = flip buildFibs

foldl buildFibs' [] [1..] =
    foldl buildFibs' (buildFibs 1 []) [2..] = 
    foldl buildFibs' [0] [2..] =
    foldl buildFibs' (buildFibs 2 [0]) [3..] =
    foldl buildFibs' [0,1] [3..] =
    foldl buildFibs' (buildFibs 3 [0,1]) [4..] =
    foldl buildFibs' (0+1 : [0,1]) [4..] =
    foldl buildFibs' [1,0,1] [4..] =
    foldl buildFibs' (buildFibs 4 [1,0,1]) [5..] =
    foldl buildFibs' (1+0 : [1,0,1]) [5..] =
    foldl buildFibs' [1,1,0,1] [5..] =
    foldl buildFibs' (buildFibs 5 [1,1,0,1]) [6..] =
    foldl buildFibs' [2,1,1,0,1] [6..] =
    -- For brevity I'll speed up the substitution
    foldl buildFibs' [3,2,1,1,0,1] [7..] =
    foldl buildFibs' [5,3,2,1,1,0,1] [8..] =
    foldl buildFibs' [8,5,3,2,1,1,0,1] [9..] =
    ...

So as you can see you can actually calculate the Fibonacci numbers using buildFibs and foldl, but unfortunately you're building an infinite list of them backwards, you'll never be able to calculate a specific element in the list because foldl will never terminate. You can calculate a finite number of them though:

> take 10 $ foldl buildFibs' [] [1..10]
[34,21,13,8,5,3,2,1,1,0]

Upvotes: 4

Daniel Wagner
Daniel Wagner

Reputation: 152707

Ask yourself: which fibonacci number will be the first one in the list? My reading of your code is that the answer to this question is, "the biggest one" (notionally, each iteration of buildFibs adds a slightly larger number to the head of the resulting list). Since there are infinitely many fibonacci numbers, this takes a while to compute!

Upvotes: 7

Related Questions