Korevrasia and Kodata

Question

I would like to get a step-by-step explanation of the next function in Haskell

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

I understand that "fibers" are generally "lazy", so the next element will be calculated "on demand", but I'm not sure how the "tail" function will work in an infinite list.

Thus, an illustration of how this works with some intermediate data will help.

Answer 1

Initially, the assessment is as follows:

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

If we replace fibs with his score, it looks like this:

 fibs = 0 : 1 : zipWith (+) (0 : 1 : ?) (1 : ?) 

Where ? denotes an unappreciated thunk. Let the following fibs element be evaluated:

 fibs = 0 : 1 : zipWith (+) (0 : 1 : ?) (1 : ?) ==> fibs = 0 : 1 : 1 : zipWith (+) (1 : ?) (?) 

The first element of each of the zipWith argument lists is zipWith . Now that we have rated it, we also know what the value of the next thunk is, and we can fill it. This allows us to evaluate the next cell and so on:

 fibs = 0 : 1 : 1 : zipWith (+) (1 : ?) (?) ==> fibs = 0 : 1 : 1 : zipWith (+) (1 : 1 : ?) (1 : ?) ==> fibs = 0 : 1 : 1 : 2 : zipWith (+) (1 : ?) (?) ==> fibs = 0 : 1 : 1 : 2 : zipWith (+) (1 : 2 : ?) (2 : ?) ==> fibs = 0 : 1 : 1 : 2 : 3 : zipWith (+) (2 : ?) (?) ==> ... 

Answer 2

tail in an infinite list is very simple: first generate the first argument, then throw it away.

So,

 fibs = 0 : 1 : fibs' tail fibs = 1 : fibs' 

and

 tail fibs = 1 : 1 : fibs'' tail (tail fibs) = 1 : fibs'' 

and

 tail (tail fibs) = 1 : 2 : fibs''' tail (tail (tail fibs)) = 2 : fibs''' 

and etc.

Answer 3

Starting at the back:

• tail returns the contents of the list with a head, for example. tail [1,2,3] → [2,3]
• zipWith applies the function differently to the contents of two lists, for example. zipWith (+) [1,2] [10,20] → [11,22]
• fibs defined as a list starting with 0 and 1, and then the result of the zipWith operation

Here is a diagram that explains what happens in zipWith

  v-searching the third value of fibs fibs: [0,1,...] tail: [1,.....] -------------- sum: [1,.....] now fibs is sum together with the leading 0 and 1: v-searching the fourth value of fibs fibs: [0,1,1,.....] tail: [1,1,.......] ------------------- sum: [1,2,.......] now fibs is sum together with the leading 0 and 1: v-searching the fifth value of fibs fibs: [0,1,1,2,.....] tail: [1,1,2,.......] ---------------------- sum: [1,2,3,.......] now fibs is sum together with the leading 0 and 1: v-searching the sixth value of fibs fibs: [0,1,1,2,3,.....] tail: [1,1,2,3,.......] ------------------------ sum: [1,2,3,5,.......] 

So, you can see that you can get the whole list if you act "step by step", which is possible due to Haskell's lazy behavior.