Representing Fibonacci numbers using a list comprehension in Haskell

Question

I have written the following code to generate a list containing the Fibonacci numbers.

fibonacci = [a + b | a <- 1:fibonacci, b <- 0:1:fibonacci]

I would expect the output of the list to be [1,2,3,5,8,13..], however, the output is not the Fibonacci sequence.

I can't quite understand why it doesn't work.

My reasoning is that, if the Fibonacci numbers are [1,2,3,5,8,13..] then this will be equal to the sum of the 2 lists [1,1,2,3,5,8,13..] and [0,1,1,2,3,5,8,13..], which are equivalent to 1:[1,2,3,5,8,13..] and 0:1:[1,2,3,5,8,13..] or 1:fibonacci and 0:1:fibonacci

I have looked up other ways of implementing this sequence, however I would really like to know why my code doesn't work.

Answer 1

The problem

With:

fibonacci = [a + b | a <- 1:fibonacci, b <- 0:1:fibonacci]

you are generating every possible combinations of the two lists. For example with:

x = [a + b | a <- [1, 2], b <- [3, 4]]

the result will be:

[1 + 3, 1 + 4, 2 + 3, 2 + 4]

Live demo

With zipWith

The closest you can get is with zipWith:

fibonacci :: [Int]
fibonacci = zipWith (+) (1:fibonacci) (0:1:fibonacci)

Live demo

Answer 2

List comprehensions model

• Non-determinism
• Cartesian products
• Nested for-loops

which are all equivalent. So your Fibonacci sequence is wrong because it's computing way too many elements. In pseudocode it's a bit like

fibonacci = 
  for i in 1:fibonacci:
    for j in 0:1:fibonacci:
      i + j

What you really want is to zip the lists together, to perform computations in the order of the length of fibonacci instead of its square. To do that we can use zipWith and, with a little algebra, get the standard "tricky fibo"

fibonacci = zipWith (+) (1:fibonacci) (0:1:fibonacci)
fibonacci = zipWith (+) (0:1:fibonacci) (1:fibonacci)          -- (+) is commutative
fibonacci = zipWith (+) (0:1:fibonacci) (tail (0:1:fibonacci)) -- def of tail

Then we just define

fibonacci' = 0:1:fibonacci
fibonacci' = 0:1:zipWith (+) (0:1:fibonacci) (tail (0:1:fibonacci))
fibonacci' = 0:1:zipWith (+) fibonacci' (tail fibonacci')

which is the standard with

fibonacci = drop 2 fibonacci'

You can also use the ParallelListComprehension extension which lets you do zipping in list comprehensions with a slightly different syntax

{-# ParallelListComp #-}
fibonacci = [a + b | a <- 1:fibonacci | b <- 0:1:fibonacci]

> take 10 fibonacci
[1,2,3,5,8,13,21,34,55,89]

Answer 3

List comprehensions don't work like that. You've written a nested traversal, whereas what you are trying to do is a zip.

To see the difference, consider:

Prelude> let fibs = [ a + b | (a,b) <- zip (1 : fibs) (0 : 1 : fibs) ]
Prelude> take 10 fibs
[1,2,3,5,8,13,21,34,55,89]

Which works as you'd expect.

There is a syntactic extension to Haskell that allows for parallel comprehensions, so the syntax does a zip for you. You can enable it with -XParallelListComp and then write:

Prelude> let fibs = [ a + b | a <- 1 : fibs | b <- 0 : 1 : fibs ]
Prelude> take 10 fibs
[1,2,3,5,8,13,21,34,55,89]

Answer 4

Another solution without zip or ParallelListComprehension is:

> fib = 0:1:[ last x + head y | x:y:[] <- [ [take i fib, drop i fib] | i <- [1,2..] ] ]
> take 10 fib
[0,1,1,2,3,5,8,13,21,34]