9

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

Community
  • 1
  • 1
Tem Pora
  • 2,043
  • 2
  • 24
  • 30

3 Answers3

18

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...]
Mikhail Glushenkov
  • 14,928
  • 3
  • 52
  • 65
  • `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. – kqr Nov 03 '13 at 08:21
  • @kqr: If you start at zero, that is! – yatima2975 Nov 04 '13 at 10:35
8

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.

Tikhon Jelvis
  • 67,485
  • 18
  • 177
  • 214
  • 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. – nutella_eater Oct 26 '21 at 07:42
  • 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: https://jelv.is/blog/Lazy-Dynamic-Programming/ – Tikhon Jelvis Oct 26 '21 at 17:10
  • 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 – nutella_eater Oct 26 '21 at 18:19
0

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)
Will Ness
  • 70,110
  • 9
  • 98
  • 181