Understanding LazyList in Scala


#1

I have this lazy list defined

val naturals : LazyList[Int] = 1 #:: naturals.map(_ + 1)

On executing

naturals take 10 foreach println

it prints numbers from 1 to 10. But according to my understanding of lazy list :

It should have expanded as 1 #:: 2 #:: 2 #:: 3 #:: 2 #:: 3 #:: 3 #:: 4

EDIT#1

When you want to two elements the list is expanded to 1 #:: 2 #::naturals.map(_ + 1)
When you want to 3 elements, it sees that the 3rd element needs to be evaluated - 1 #:: 2#:: (1 #:: 2#:: naturals.map(_ + 1)).map(_ + 1).

Is this not how the expansion works?


#2

I don’t understand the reasoning behind your expected expansion…?


#4

Have edited the post to include my reasoning


#5

Actually, when you want to two elements the list is expanded to 1 #:: 2 #:: naturals.tail.map(_ + 1), i.e. the lazy list is split into its head and tail expanding naturals = naturals.head #:: natural.tail.

regards,
Siddhartha


#6

I think the mistake you made is thinking that naturals.map(_ + 1) gets reevaluated every time an element of naturals gets computed.


#7

You’re still trying to take multiple steps at once and getting it wrong. Simply substituting (1 #:: naturals.map(_ + 1)) for naturals a few times without any further rewriting gives you:

1 #:: naturals.map(_ + 1)

1 #:: (1 #:: naturals.map(_ + 1)).map(_ + 1)

1 #:: (1 #:: (1 #:: naturals.map(_ + 1)).map(_ + 1)).map(_ + 1)

1 #:: (1 #:: (1 #:: (1 #:: naturals.map(_ + 1)).map(_ + 1)).map(_ + 1)).map(_ + 1)

Notice how the consecutive elements are nested under an increasing number of map(_ + 1) calls. If you distribute map(_ + 1) over #:: one by one you get:

1 #:: 2 #:: (2 #:: (2 #:: naturals.map(_ + 1).map(_ + 1)).map(_ + 1)).map(_ + 1)

1 #:: 2 #:: 3 #:: (3 #:: naturals.map(_ + 1).map(_ + 1).map(_ + 1)).map(_ + 1)

1 #:: 2 #:: 3 #:: 4 #:: naturals.map(_ + 1).map(_ + 1).map(_ + 1).map(_ + 1)

#8

got it. thank you. But it’s kind of getting confusing. When you apply this kind of substitution to the fibonacci series -

val fibs = 0 #:: 1 #:: fibs.tail.zip(fibs).map(n => n._1 + n._2)

val fibs = 0 #:: 1 #:: (0 #:: 1 #:: fibs.tail.zip(fibs).map(n => n._1 + n._2)).tail.zip((0 #:: 1 #:: fibs.tail.zip(fibs).map(n => n._1 + n._2))).map(n => n._1 + n._2)

After the second expansion above, I guess the third element is available due to zip.

3rd element - (1 #:: fibs.tail.zip(fibs).map(n => n._1 + n._2)).zip(0 #:: 1 #:: fibs.tail.zip(fibs).map(n => n._1 + n._2))
((1,0),(fibs.tail.zip(fibs).map(n => n._1 + n._2), 1)).map(n => n._1 + n._2)

eventually

0 #:: 1 #:: 1 #:: (fibs.tail.zip(fibs).map(n => n._1 + n._2) + 1)

Fine till here. You can see that there is +1 at the end. How do you add 1 to a list?