Why does a recursive lazy list flush the stack in Scala?
I saw this Haskell snippet in this proud haskeller's answer on Meta PPCG:
x=2:x
I thought, "Wait, I can do this in Scala!" So I tried:
lazy val x: List[Int] = 2 :: x
Compiled and my console printed good x: List[Int] = <lazy>
. But each of these lines results in StackOverflowException
:
x take 1
x.head
x(1)
x
Based on the latter, it looks like any attempt to use x
hits the stack when trying to compute x
(either that or a stack overflow happens when trying to print it to the console). How does Scala laziness differ from Haskell's dexterity in this example? Is this a Scala feature lazy val
or List
does the class just require a full tail?
You want def x: Stream[Int] = 2 #:: x
. It creates immutable.Stream[Int]
.
The spurious variable is only evaluated when needed, but it is fully evaluated. A Stream
, on the other hand, is a collection of lazy values. Each item is only evaluated when needed, but the entire collection can never be evaluated, so it can be infinite.
Well, it looks like I figured it out by formulating the question. This is more of a problem with List
than with lazy val
. To try this, I made a simple implementation LazyList
:
class LazyList(h: Int, t: => LazyList) {
val head = h
lazy val tail = t
}
Then I can do:
lazy val x: LazyList = new LazyList(1, x)
x.head // 1
x.tail.tail.tail.head // 1
So, Scala laziness is actually lazy if you make everything lazy at least.