Strictness And Laziness

Functional programming in Scala

The following set of sections represent the exercises contained in the book "Functional Programming in Scala", written by Paul Chiusano and Rúnar Bjarnason and published by Manning. This content library is meant to be used in tandem with the book. We use the same numeration for the exercises for you to follow them.

For more information about "Functional Programming in Scala" please visit its official website.

Strict and non-strict functions

NOTE: This section is only for educational purposes. In Scala 2.13, scala.collection.immutable.Stream is deprecated and scala.collection.immutable.LazyList is recommended for replacement. For more information, check the Scala Stream and LazyList documentation.

Exercise 5.1:

Now let's write a few helper functions to make inspecting streams easier, starting with a function to convert a Stream to a List (which will force its evaluation): 

def toList[A](s: Stream[A]): List[A] =
  s match {
    case Cons(h, t) => h() :: toList(t())
    case _ => List()
  }

val s = Stream(1, 2, 3)
toList(s) shouldBe res0

Exercise 5.2:

Let's continue by writing the function take for returning the first n elements of a Stream. Note that in the following implementation, we're using Stream's smart constructors cons and empty, defined as follows:

def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
  lazy val head = hd
  lazy val tail = tl
  Cons(() => head, () => tail)
}

def empty[A]: Stream[A] = Empty
def take[A](s: Stream[A], n: Int): Stream[A] =
  s match {
    case Cons(h, t) if n > 0 => cons[A](h(), t().take(n - res0))
    case Cons(h, _) if n == 0 => cons[A](h(), Stream.empty)
    case _ => Stream.empty
  }

take(Stream(1, 2, 3), 2).toList shouldBe List(1, 2)

drop is similar to take, but skips the first n elements of a Stream instead: 

def drop[A](s: Stream[A], n: Int): Stream[A] =
  s match {
    case Cons(_, t) if n > 0 => t().drop(n - res0)
    case _ => s
  }

drop(Stream(1, 2, 3, 4, 5), 2).toList shouldBe List(3, 4, 5)

Exercise 5.3:

We can also implement takeWhile to return all starting elements of a Stream that match a given predicate: 

def takeWhile[A](s: Stream[A], f: A => Boolean): Stream[A] =
  s match {
    case Cons(h, t) if f(h()) => cons(h(), t() takeWhile f)
    case _ => Stream.empty
  }

takeWhile(Stream(1, 2, 3, 4, 5), (x: Int) => x < 3).toList shouldBe res0
takeWhile(Stream(1, 2, 3, 4, 5), (x: Int) => x < 0).toList shouldBe res1

Separating program description from evaluation

Laziness lets us separate the description of an expression from the evaluation of that expression. This gives us a powerful ability — we may choose to describe a “larger” expression than we need, and then evaluate only a portion of it. As an example, let’s look at the function exists that checks whether an element matching a Boolean function exists in this Stream:

def exists(p: A => Boolean): Boolean = this match {
  case Cons(h, t) => p(h()) || t().exists(p)
  case _ => false
}

Exercise 5.4:

Let's implement forAll, a function that checks that all elements in the Stream match a given predicate. Note that the implementation will stop as soon as it encounters a non-matching value. 

def forAll[A](s: Stream[A], f: A => Boolean): Boolean =
  s.foldRight(res0)((a, b) => f(a) && b)

forAll(Stream(1, 2, 3), (x: Int) => x % 2 == 0) shouldBe false
forAll(Stream("a", "b", "c"), (x: String) => x.size > 0) shouldBe true

Exercise 5.5:

Let's put foldRight to good use, by implementing takeWhile based on it:

def takeWhile_1(f: A => Boolean): Stream[A] =
  foldRight(empty[A])((h, t) =>
    if (f(h)) cons(h, t)
    else empty)

Exercise 5.6:

We can also do the same with headOption:

def headOption: Option[A] = foldRight(None: Option[A])((h, _) => Some(h))

Exercise 5.7:

Implementations for map, filter, append and flatMap using foldRight should sound familiar already:

def map[B](f: A => B): Stream[B] = foldRight(empty[B])((h, t) => cons(f(h), t))

def filter(f: A => Boolean): Stream[A] = foldRight(empty[A])((h, t) =>
  if (f(h)) cons(h, t)
  else t)

def append[B >: A](s: => Stream[B]): Stream[B] = foldRight(s)((h, t) => cons(h, t))

def flatMap[B](f: A => Stream[B]): Stream[B] = foldRight(empty[B])((h, t) => f(h) append t)

Exercise 5.x:

Let's look at a simplified program trace for the next piece of code.

Stream(1, 2, 3, 4).map(_ + 10).filter(_ % 2 == 0)

We'll convert that expression to a List to force evaluation. Try to follow with what's happening in each step: 

val startingPoint = Stream(1, 2, 3, 4).map(_ + 10).filter(_ % 2 == 0).toList

// Apply map to the first element:
val step1 = cons(res0, Stream(2, 3, 4).map(_ + 10)).filter(_ % 2 == 0).toList
// Apply filter to the first element:
val step2 = res1.map(_ + 10).filter(_ % 2 == 0).toList
// Apply map to the second element:
val step3 = cons(12, res2.map(_ + 10)).filter(_ % 2 == 0).toList
// Apply filter to the second element. Produce the first element of the result:
val step4 = 12 :: Stream(3, 4).map(_ + 10).filter(_ % 2 == 0).toList
val step5 = 12 :: cons(res3, res4.map(_ + 10)).filter(_ % 2 == 0).toList
val step6 = 12 :: Stream(4).map(_ + 10).filter(_ % 2 == 0).toList
val step7 = 12 :: cons(res5, Stream[Int]().map(_ + 10)).filter(_ % 2 == 0).toList
// Apply filter to the fourth element and produce the final element of the result.
val step8 = 12 :: 14 :: Stream[Int]().map(_ + 10).filter(_ % 2 == 0).toList
// map and filter have no more work to do, and the empty stream becomes the empty list.
val finalStep = 12 :: 14 :: List()

startingPoint shouldBe step1
step1 shouldBe step2
step2 shouldBe step3
step3 shouldBe step4
step4 shouldBe step5
step5 shouldBe step6
step6 shouldBe step7
step7 shouldBe step8
step8 shouldBe finalStep

Infinite streams and corecursion

Exercise 5.x:

Here’s an example of an infinite Stream of 1s:

val ones: Stream[Int] = Stream.cons(1, ones)

The functions we’ve written so far only inspect the portion of the stream needed to generate the demanded output. Take a look at this example: 

ones.take(5).toList shouldBe res0
ones.exists(_ % 2 != 0) shouldBe res1
ones.map(_ + 1).exists(_ % 2 == 0) shouldBe res2
ones.forAll(_ != 1) shouldBe res3

Exercise 5.8:

Let's generalize ones slightly to the function constant, which returns an infinite Stream of a given value:

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

Exercise 5.9:

Of course, we can generate number series with Streams. For example, let's write a function that generates an infinite stream of integers (n, n + 1, n + 2...): 

def from(n: Int): Stream[Int] =
  cons(n, from(n + res0))

from(100).take(5).toList shouldBe List(100, 101, 102, 103, 104)

Exercise 5.10:

We can also create a function fibs that generates the infinite stream of Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8... 

val fibs = {
  def go(f0: Int, f1: Int): Stream[Int] =
    cons(f0, go(f1, f0 + f1))
  go(res0, res1)
}

fibs.take(7).toList shouldBe List(0, 1, 1, 2, 3, 5, 8)

Exercise 5.11:

Now we're going to write a more general stream-building function: unfold which takes an initial state, and a function for building both the next state and the next value in the stream to be generated:

def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] = f(z) match {
  case Some((h, s)) => cons(h, unfold(s)(f))
  case None => empty
}

Exercise 5.12:

Now that we have unfold, let's rewrite our previous generator functions based on it, starting from fibs: 

val fibsViaUnfold =
  unfold((res0, res1)) { case (f0, f1) => Some((f0, (f1, f0 + f1))) }

fibsViaUnfold.take(7).toList shouldBe List(0, 1, 1, 2, 3, 5, 8)

from follows a similar principle, albeit a little simpler: 

def fromViaUnfold(n: Int) = unfold(n)(n => Some((n, n + res0)))

fromViaUnfold(100).take(5).toList shouldBe List(100, 101, 102, 103, 104)

Again, constant can be implemented in terms of unfold in a very similar way:

def constantViaUnfold[A](a: A) = unfold(a)(_ => Some((a, a)))

Follow the same pattern to implement ones using unfold: 

val onesViaUnfold = unfold(1)(_ => res0)

onesViaUnfold.take(10).toList shouldBe List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

Exercise 5.13:

Now we're going to re-implement some of the higher-order functions for Streams, starting with map:

def mapViaUnfold[B](f: A => B): Stream[B] = unfold(this) {
  case Cons(h, t) => Some((f(h()), t()))
  case _ => None
}

take can also be rewritten via unfold, let's try it: 

def takeViaUnfold[A](s: Stream[A], n: Int): Stream[A] =
  unfold((s, n)) {
    case (Cons(h, t), 1) => Some((h(), (Stream.empty, res0)))
    case (Cons(h, t), n) if n > 1 => Some((h(), (t(), n - res1)))
    case _ => None
  }

takeViaUnfold(Stream(1, 2, 3, 4, 5), 5).toList shouldBe List(1, 2, 3, 4, 5)

Let's continue by rewritting takeWhile in terms of unfold:

def takeWhileViaUnfold(f: A => Boolean): Stream[A] = unfold(this) {
  case Cons(h, t) if f(h()) => Some((h(), t()))
  case _ => None
}

We can also bring back functions we saw previously with Lists, as zipWith:

def zipWith[B, C](s2: Stream[B])(f: (A, B) => C): Stream[C] = unfold((this, s2)) {
  case (Cons(h1, t1), Cons(h2, t2)) =>
    Some((f(h1(), h2()), (t1(), t2())))
  case _ => None
}

zipAll can also be implemented using unfold. Note that it should continue the traversal as long as either stream has more elements - it uses Option to indicate whether each stream has been exhausted:

def zipAll[B](s2: Stream[B]): Stream[(Option[A], Option[B])] = zipWithAll(s2)((_, _))

def zipWithAll[B, C](s2: Stream[B])(f: (Option[A], Option[B]) => C): Stream[C] =
  Stream.unfold((this, s2)) {
    case (Empty, Empty) => None
    case (Cons(h, t), Empty) => Some(f(Some(h()), Option.empty[B]) -> (t(), empty[B]))
    case (Empty, Cons(h, t)) => Some(f(Option.empty[A], Some(h())) -> (empty[A] -> t()))
    case (Cons(h1, t1), Cons(h2, t2)) => Some(f(Some(h1()), Some(h2())) -> (t1() -> t2()))
  }

Exercise 5.14:

Now we're going to try to implement startsWith using the functions we've seen so far:

def startsWith[A](s: Stream[A]): Boolean =
  zipAll(s).takeWhile(!_._2.isEmpty) forAll {
    case (h, h2) => h == h2
  }

Exercise 5.15:

We can also write tails using unfold. tails returns the Stream of suffixes of a given Stream, starting with the original Stream. For example, for Stream(1,2,3), it should return Stream(Stream(1,2,3), Stream(2,3), Stream(3), Stream()). 

def tails[A](s: Stream[A]): Stream[Stream[A]] =
  unfold(s) {
    case Empty => None
    case s1 => Some((s1, s1 drop res0))
  } append Stream(Stream.empty)

tails(Stream(1, 2, 3)).toList
  .map(_.toList) shouldBe List(List(1, 2, 3), List(2, 3), List(3), List())

Exercise 5.16:

We can generalize tails to the function scanRight, which is like a foldRight that returns a stream of the intermediate results:

def scanRight[B](z: B)(f: (A, => B) => B): Stream[B] =
  foldRight((z, Stream(z)))((a, p0) => {
    lazy val p1 = p0
    val b2 = f(a, p1._1)
    (b2, cons(b2, p1._2))
  })._2

For example: 

Stream(1, 2, 3).scanRight(0)(_ + _).toList shouldBe res0