Haskell how to generate this infinite list?

Question

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 1

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

Solution 2

Yes.

Think about how you could write out each element of your list:

1
1 + 1
1 + 1 + 1
1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

After each entry, every subsequent entry has an extra + 1. So we want to start at 1 and then add 1 to each subsequent element. Then we want to take the second element and add 1 to everything after that.

Here's how we can do this:

let xs = 1 : map (+ 1) xs

This expands like this:

1 : map (+ 1) xs
1 : (1 + 1) : map (+ 1) xs
1 : (1 + 1) : ((1 + 1) + 1) : map (+ 1) xs

and so on.

Comments

[kqr]

nats = iterate succ 1 gives an even better intuition for what happens, in my opinion. Applying the successor function over and over will naturally yield the set of naturals.

[yatima2975]

@kqr: If you start at zero, that is!

[nutella_eater]

how can you append the list, without knowing what list actually is? I mean, after : sign everything should be evaluated in order to append the list.

[Tikhon Jelvis]

That's basically how it works :). This can be a tricky idea, so I wrote a blog post about it a while ago with some illustrations: jelv.is/blog/Lazy-Dynamic-Programming

[nutella_eater]

I've asked my teacher today and he said that it is not evaluated. It is evaluated when we call take or other function. But print somehow can evaluate it, without actually evaluate the end