CODEWITHSUNDEEP
haskell
RosaryLightning X
RosaryLightning X

Reputation: 157

Lazy evaluation in Haskell with zipWith and two infinite lists

Evaluating the Haskell code here:

lazee = 0 : zipWith (+) (map (+1) lazee) (map (2*) lazee)

and then calling take 5 lazee yields this result:

[0,1,4,13,40]

I don't understand the order in which the above functions are evaluated. They are infinite lists and I have a bit of trouble wrapping my head around that. Consequently I'm not sure how Haskell would have gotten this result.

Upvotes: 1

Views: 602

Answers (1)

chi
chi

Reputation: 116139

It roughly works like this

lazee = 0 : lazee1
lazee1 = zipWith (+) (map (+1) lazee) (map (2*) lazee)

therefore

lazee = 0 : lazee1
lazee1 = zipWith (+) (map (+1) (0:lazee1)) (map (2*) (0:lazee1))

but map (+1) (0:lazee1) is 1 : map (+1) lazee1. Similarly for the other map. Therefore

lazee = 0 : lazee1
lazee1 = zipWith (+) (1 : map (+1) lazee1) (0 : map (2*) lazee1)

Now zipWith knows the first elements, and can compute (+) 1 0. We get

lazee = 0 : lazee1
lazee1 = 1 : lazee2
lazee2 = zipWith (+) (map (+1) lazee1) (map (2*) lazee1)

Now repeat the same steps as above:

lazee2 = zipWith (+) (map (+1) (1:lazee2)) (map (2*) (1:lazee2))
       = zipWith (+) (2 : map (+1) lazee2) (2 : map (2*) lazee2)
       = 4 : zipWith (+) (map (+1) lazee2) (map (2*) lazee2)

And so on.

Upvotes: 3

Related Questions