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

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

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

Answer 3

Actually, because Haskell's laziness is call by need, having defined

xs = 1 : map (+1) xs

then calling e.g. print xs proceeds as

xs
xs  where  xs = 1 : map (+ 1) xs
xs  where  xs = x1 : xs2 ; x1 = 1 ; xs2 = map (+ 1) xs
x1 : xs2  where  xs2 = map (+ 1) (x1 : xs2) ; x1 = 1
x1 : xs2  where  xs2 = (x1+1) : map (+ 1) xs2 ; x1 = 1
x1 : xs2  where  xs2 = x2 : xs3 ; x2 = x1+1 ; xs3 = map (+ 1) xs2 ; x1 = 1
1 : x2 : xs3  where  xs3 = map (+ 1) (x2 : xs3) ; x2 = 2
1 : x2 : xs3  where  xs3 = (x2+1) : map (+ 1) xs3 ; x2 = 2
1 : 2 : x3 : xs4  where  xs4 = map (+ 1) (x3 : xs4) ; x3 = 3
1 : 2 : 3 : x4 : xs5  where  xs5 = map (+ 1) (x4 : xs5) ; x4 = 4
.....

so that there's no repeated computations of n+1 by repeated additions of 1s. The n is already computed.

We just give a name to every place, so that the name holds a computation to be performed, at first, and then its value, afterwards. Since the name is shared among other computations, there's no repeated calculations of its value.

Same thing happens with the calculation of the Fibonacci numbers list.

---

So then xs indeed generates the list [1,2..]. The process of repeated additions of 1 is naturally expressed as iterate (+1) 1, as already noted in another answer.

We could also define this as

nums1 = xs where
        ys = 1 : ys
        xs = zipWith (+) (0 : xs) ys

which is perhaps what you were trying to express.

The definition of a list by zipping with itself shifted by one step (as in the Fibonacci list definition) gives the mapping function access to two previous elements of the list simultaneously while defining the current element.

Similarly, the definition of a list by zipping itself shifted by one step and another list (as with the definition of nums1 above) gives the mapping function access to the previous element while defining a current one.

We say "mapping function" because zipWith is a binary map:

zipWith f xs ys = map (\(x,y) -> f x y) (zip xs ys)