There was an unanswered question from our discussion of Scala Laziness last night: Why do we need all that
code for managing the evaluation of the tail of a Stream?
package scala.collection.immutable
object Stream {
...
final class Cons[+A](hd: A, tl: => Stream[A])
extends Stream[A] {
override def isEmpty = false
override def head = hd
@volatile private[this]
var
tlVal: Stream[A] = _
def
tailDefined: Boolean = tlVal ne null
override def
tail: Stream[A] = {
if
(!tailDefined)
synchronized {
if
(!tailDefined) tlVal = tl
}
tlVal
}
}
}
It seemed like passing the tail
parameter using call-by-name might be sufficient. Here’s my first
attempt at trying that out:
abstract
class
MyStream1[+A] {
def
isEmpty: Boolean
def
head: A
def
tail: MyStream1[A]
}
object
MyStream1 {
object
Empty extends
MyStream1[Nothing] {
override
def
isEmpty = true
override
def
head = { throw
new
Exception("Bad!")
}
override
def
tail = { throw
new
Exception("Bad!")
}
}
class
Cons[A](head: A, tail: => MyStream1[A])
extends MyStream1[A] {
extends MyStream1[A] {
override
def
isEmpty = false
}
}
Uh-oh, the compiler isn’t happy with
this definition of Cons:
class
Cons needs to be abstract, since:
method tail in class MyStream1 of type => MyStream1[A] is not defined
method head in class MyStream1 of type => A is not defined
method tail in class MyStream1 of type => MyStream1[A] is not defined
method head in class MyStream1 of type => A is not defined
This Cons
doesn’t implement head and tail as specified in the parent class.
It looks like putting them in the constructor argument list isn’t
enough. So let’s try this:
abstract
class
MyStream2[+A] {
def
isEmpty: Boolean
def
head: A
def
tail: MyStream2[A]
}
object
MyStream2 {
object
Empty extends
MyStream2[Nothing] {
override
def
isEmpty = true
override
def
head = { throw
new
Exception("Bad!")
}
override
def
tail = { throw
new
Exception("Bad!")
}
}
class
Cons[A](hd: A, tl: => MyStream2[A])
extends MyStream2[A] {
extends MyStream2[A] {
override
def
isEmpty = false
override
val
head = hd
override
lazy
val
tail = tl
}
}
OK, that compiles. Let’s try running
this:
object
Foo2 {
def
from(n: Int): MyStream2[Int] = {
println("from("
+ n + ")")
new
MyStream2.Cons(n, from(n + 1))
}
def
main(args: Array[String]) {
val
ints = from(0)
println(ints.head)
println(ints.tail.head)
println(ints.tail.tail.head)
println(ints.head)
println(ints.tail.head)
println(ints.tail.tail.head)
}
}
Here’s what we get:
from(0)
0
from(1)
1
from(2)
2
0
1
2
Cool, that seems to work. We see the
side effect of the node evaluation the first time we visit each node,
but not afterwards.
So we need the tail passed as
call-by-name to delay its evaluation, and we need to override head
and tail to match the definition of the abstract parent class. I used
lazy val for the tail,
so that it isn’t evaluated right away when the node is constructed.
Try changing that to just val:
...
from(1538)
from(1539)
from(1540)
Exception
in thread "main" java.lang.StackOverflowError
Oops! Now as soon as you create a node,
the tail is evaluated, and its tail is evaluated, and its tail…
So why doesn’t the Stream implementation in the Scala standard library use lazy val for the tail? I suspect it’s an optimization because I don’t think lazy val would have any threading issues. Or it could be that the tailDefined attribute is useful elsewhere in the class.
