CODEWITHSUNDEEP
haskellfunctional-programminglist-comprehensionfibonacci
eyes enberg
eyes enberg

Reputation: 586

Defining an infinite sequence of Fibonacci numbers using list comprehension in Haskell

How would I do this? It's part of an exercise in my lecture slides and the hints are to use the library functions tail :: [a] -> [a] and zip :: [a] -> [b] -> [(a,b)]. Also, the type of the function is fibs :: [Integer]

I know how list comprehension works, how to write a recursive Fibonacci function that takes in a value and am familiar with both the tail and zip functions - however, I just can't figure this one out and haven't been able to find an example online. Can anybody show me how its done?

Also out of curiosity, how are functions like this (that produce an infinite list) used in Haskell? If I write fibs (the function name) in the ghci command prompt for example will it continue to print the elements in the list until the end of time?

Thanks in advance for any help.

Upvotes: 1

Views: 678

Answers (3)

khadj999
khadj999

Reputation: 11

Here is the solution I found using zip and tail:

fibs :: [Integer]
fibs = 0:1:[x + y | (x,y) <- zip fibs (tail fibs)]

If you run fibs, it will keep printing until the computer runs out of memory and crashes. You can call functions that return infinite lists through take and takeWhile to return a finite list. Haskell uses lazy evaluation to make handling infinite data structures more efficient.

Example:

take 10 fibs

prints:

[0,1,1,2,3,5,8,13,21,34]

Upvotes: 1

Random Dev
Random Dev

Reputation: 52270

here is another one chi style (I hope you don't mind):

write the fibs:

fibs = 1 1 2 3 5 8 13 ...

write it again but shift one left:

fibs       = 1 1 2 3 5 8 13 ...
(??? fibs) = 1 2 3 5 8 13 ...

add them:

fibs       = 1 1 2 3 5 8 13 ...
(??? fibs) = 1 2 3 5 8 13 ...
--------------------
(+ em)     = 2 3 5 8 13 21 ...

looks familiar?

Now you only have to prepend something (again) and think about what shift left means here (hint you mentioned it):

fibs       = 1 1 2 3 5 8 13 ...
(??? fibs) = 1 2 3 5 8 13 ...
--------------------
(+ em)     = 2 3 5 8 13 21 ...
=> fibs = ? : ((+ em) fibs (??? fibs))

Also summing up can be done nicely with zipWith (+)

Have fun

Upvotes: 3

chi
chi

Reputation: 116139

Here's a hint.

Take the sequence of powers of two.

p2 = [1, 2, 4, 8, 16 ...

zip it with itself

zip p2 p2 = [(1,1), (2,2), (4,4), ...]

Sum every pair in the list (this can be done using a list comprehension)

[2, 4, 8, ...

Prepend 1:

[1, 2, 4, 8, ...

So we got the p2 list again. If you express all of this in Haskell, you end up with some code of the form

p2 = 1 : ... something involving p2 ...

which is a working program generating the powers of two.

Once you get this working, you can change it slightly and obtain Fibonacci as well.

For the last point: yes, printing p2 will print the whole infinite sequence. You can print just a few elements using

take 10 p2

Upvotes: 8

Related Questions