Functional programming in scala - infinite streams

Question

I'm working through the exercises and concepts of the book: Functional Programming in Scala. Say I need to define a constant function, which returns an infinite stream by the given value.

Here is my version:

def constant[A](a: A): Stream[A] = Stream.cons(a, constant(a))

and the answer in GitHub:

def constant[A](a: A): Stream[A] = {
  lazy val tail: Stream[A] = Cons(() => a, () => tail)
  tail
}

The comment says the latter is more efficient than the former since it's just one object referencing itself. I can't understand this, any help would be greatly appreciated. (and sorry for my broken English :)

Answer 1

Say you define constant the first way. Now,

constant(something)

This is one Cons cell, and it has a reference to the lazy values something and constant(something)

Cons(() => something, () => constant(something))

Now, let's try to get the 1000th element. We need to evaluate the tail, because we need to go deeper than just the first element. So, we execute constant(something), and we get a new Cons cell that looks just like the original:

Cons(() => something, () => constant(something))

And we try to get 999th element of this Stream. This is inefficient, because this object is the same as the one from before, so we just wasted our time making it. We will continue to waste time and memory making 1000 identical Cons cells. (Excuse the terrible drawing.)

Now, define constant the second way.

constant(something)
{ lazy val self = Cons(something, self); self }

Now, your Stream simply has a reference to itself. Getting the tail of this Stream does not create a new Cons cell; it simply returns the original stream (self.tail eq self), which means you waste no memory, and the time cost goes down because you also don't waste time allocating and filling that memory.