Representing Fibonacci numbers using a list comprehension in Haskell

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

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]

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]