CODEWITHSUNDEEP
haskelllist-comprehensionfibonacci
Sam
Sam

Reputation: 3180

Representing Fibonacci numbers using a list comprehension in Haskell

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.

Upvotes: 6

Views: 3925

Answers (4)

lazuxd
lazuxd

Reputation: 46

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]

Upvotes: 2

J. Abrahamson
J. Abrahamson

Reputation: 74394

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]

Upvotes: 8

Don Stewart
Don Stewart

Reputation: 138007

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]

Upvotes: 6

Shoe
Shoe

Reputation: 76298

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

Upvotes: 10

Related Questions