Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Haskell how to generate this infinite list?

I saw this code to generate Fibonacci numbers.

fibs = 1:1:(zipWith (+) fibs (tail fibs))

Can a similar styled code be written to generate the infinite list [1..]?

I saw this link on cyclic structures on the Haskell website.

There an example is given

cyclic = let x = 0 : y
         y = 1 : x
     in  x

I tried to define a list for my problem in a cyclic manner, but could not succeed. What I want is a list defined in terms of itself and which evaluates to [1..] in Haskell.

Note: The Haskell [1..] evaluates to [1,2,3,4,5...] and not to [1,1,1...].

like image 792
Tem Pora Avatar asked Nov 03 '13 02:11

Tem Pora


1 Answers

The following should give you the desired result:

nats = 1 : map (+1) nats

Or, more idiomatically:

nats = iterate (+1) 1

It's easy to see why the first snippet evaluates to [1,2,3...] by using equational reasoning:

nats = 1 : map (+1) nats 
     = 1 : map (+1) (1 : map (+1) nats) 
     = 1 : map (+1) (1 : map (+1) (1 : map (+1) nats))
     = 1 : 1 + 1 : 1 + 1 + 1 : .... 
     = [1,2,3...]
like image 187
Mikhail Glushenkov Avatar answered Sep 21 '22 10:09

Mikhail Glushenkov