Search code examples
listhaskellinfinitecyclic

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...].


Solution

  • 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...]