Technical knowledge base Study Notes Scala 201.02 - Lazy evaluation

201.02 - Lazy evaluation

Structural Induction on Trees

Streams

To find the second prime number greater than 1000:

((1000 to 10000) filter isPrime)(1)

This is much shorter than the recursive version:

def secondPrime(from: Int, to: Int): Int = nthPrime(from, to, 2)

def nthPrime(from: Int, to: Int, n:Int): Int = {
  if (from >= to) throw new Error("No prime")
  else if (isPrime(from)) 
    if (n==1) from else nthPrime(from + 1, to, n - 1)
  else nthPrime(from + 1, to, n)
}

But, the condensed version is inefficient, because it calculates all prime numbers between 1000 and 10000, only to retain the second of them.

Trick: avoid computing the tail of an expression until it is needed for evaluating a result. This is what streams are for. Streams are similar to lists, but their tail is evaluated on demand.

Streams are defined:

from a constant Stream.empty
and a constructor Stream.cons

val xs = Stream.cons(1, Stream.cons(2, Stream.empty))

or, by using the object Stream as a factory:

val xs = Stream(1, 2, 3)

The toStream method of a collection transforms the collection into a Stream:

(1 to 1000).toStream

The (lo until hi).toStream method could be implemented similar to the following:

def streamRange(lo: Int, hi: Int): Stream[Int] = 
  if (lo > hi) Stream.empty
  else 
    Stream.cons(lo, streamRange(lo + 1, hi))

Compare to the same function that produces a list:

def listRange(lo: Int, hi: Int): List[Int] = 
  if (lo > hi) Nil
  else 
    lo :: listRange(lo + 1, hi)

Streams behave like lists, so we could write our original functions as follows:

((1000 to 10000).toStream filter isPrime)(1)

One caveat:

x :: xs

always produces a List, not a Stream. However:

x #:: xs

produces a Stream and is equivalent to:

Stream.cons(x, xs)

The implementation of Streams is close to the implementation of Lists:

trait Stream[+A] extends Seq[A] {
  def isEmpty: Boolean
  def head: A
  def tail: Stream[A]
  ...
}

The implementation looks like this:

object Stream {
  def cons[T](hd: T, tl: => Stream[T]): Stream[T] = new Stream[T] {
    def isEmpty = false
    def head = hd
    def tail = tl
  }

  val empty = new Stream[Nothing] {
    def isEmpty = true
    def head = throw new NoSuchElementException("empty.head")
    def tail = throw new NoSuchElementException("empty.tail")   
  }
}

Lazy evaluation

The Stream evaluation suffers from another potential problem. If the tail is requested several times, it will be calculated every single time. The result could be cached, because pure functions have no side effects. This is what the lazy evaluation is about, as opposed as by-name evaluation or strict evaluation (by value).

Haskell uses lazy evaluation by default. In Scala, it is triggered by:

lazy val x = expr

Using lazy evaluation, the Stream.cons.tail function can be implemented more efficiently:

  def cons[T](hd: T, tl: => Stream[T]): Stream[T] = new Stream[T] {
    def isEmpty = false
    def head = hd
    lazy val tail = tl
  }

Computing with infinite sequences

Example: a stream of all integers starting with a given number:

def from(n: Int): Stream[Int] = n #:: from(n + 1)

val naturalNumbers = from(0)
val multiplesOfFour = naturalNumbers map (_ * 4)

The Sieve of Erathostenes algorithm for finding prime numbers works like this:

Start with 2;
Eliminate all numbers that divide by 2;
Take the next (non-eliminated) number: 3;
Eliminate all numbers that divide by 3;
...

This can be implemented as follows:

def sieve(s: Stream[Int]): Stream[Int] = 
  s.head #:: sieve(s.tail filter (_ % s.head != 0))

val primes = sieve(from(2))

primes.take(10).toList

Case Study: the water pouring problem

class Pouring(capacity: Vector[Int]) {

  // States
  type State = Vector[Int]
  val initialState = capacity map (x => 0)

  // Moves
  trait Move {
    // A method that defines state changes
    def change(state: State): State
  }
  case class Empty(glass: Int) extends Move {
    def change(state: State) = state updated (glass, 0) // Remember: updated 
                                                        // creates a new vector 
                                                        // with an element changed
  }
  case class Fill(glass: Int) extends Move {
    def change(state: State) = state updated (glass, capacity(glass))
  }
  case class Pour(from: Int, to: Int) extends Move {
    def change(state: State) = {
      val amount = state(from) min (capacity(to) - state(to))
      state updated (to, state(to) + amount) updated (from, state(from) - amount)
    }
  }

  val glasses = 0 until capacity.length

  val moves =
    // for g 'taken from' glasses
    (for (g <- glasses) yield Empty(g)) ++ // Empty a glass
    (for (g <- glasses) yield Fill(g)) ++ // Fill up a glass
    (for (from <- glasses; to <- glasses if from != to) yield Pour(from, to))

  // Paths, sequences of moves
  class Path(history: List[Move], val endState: State) { // val: Available from 
                                                         // outside
    def extend(move: Move) = new Path(move :: history, move change endState)
    override def toString = (history.reverse mkString " ") + "--> " + endState
  }

  val initialPath = new Path(Nil, initialState)

  // Path generating function (state exploration function)
  def from(paths: Set[Path], explored: Set[State]): Stream[Set[Path]] =
    if (paths.isEmpty) Stream.empty
    else {
      val more = for {
        path <- paths
        next <- moves map path.extend
        if !(explored contains next.endState) // Restrict moves to states that are 
                                              // unexplored
      } yield next
      paths #:: from(more, explored ++ (more map (_.endState)))
    }

  val pathSets = from(Set(initialPath), Set(initialState))

  def solutions(target: Int): Stream[Path] =
    for {
      pathSet <- pathSets
      path <- pathSet
      if path.endState contains target
    } yield path
}