Collecting Transformations in Scala

September 7, 2017

Given a list of numbers and a function that (noisily) increments a number:

val list: List[Int] = (1 to 100).toList

def inc(x: Int): Int = {
  val y: Int = x + 1
  println(s"inc($x) = $y")
  y
}

Observe that mapping the function over the list produces a lot of noise, because List eagerly applies transformations:

val mappedList: List[Int] = list map inc map inc map inc

inc(0) = 1
inc(1) = 2
...
inc(99) = 100
inc(100) = 101
inc(2) = 3
inc(3) = 4
...
inc(100) = 101
inc(101) = 102
inc(3) = 4
inc(4) = 5
...
inc(101) = 102
inc(102) = 103

Implement a lazy linked list called Stream and a Functor instance that defers map transformations until take is applied:

sealed trait Stream[+A] {
  def take(n: Int): List[A]
}

trait Functor[F[_]] {
  def map[A,B](fa: F[A])(f: A => B): F[B]
}

implicit class FunctorOps[A,F[_]:Functor](fa: F[A]) {
  def map[B](f: A => B): F[B] =
    implicitly[Functor[F]].map(fa)(f)
}

Bonus

Implement a mapNth enrichment method that defers a single transformation on an indexed value in the stream.

Solution

Here is one possible solution.

case object Empty extends Stream[Nothing] {
  def take(n: Int) = Nil
}

case class Cons[A]( headF: () => A
                  , tailF: () => Stream[A]
                  ) extends Stream[A] {

  lazy val head: A = headF()
  lazy val tail: Stream[A] = tailF()

  def take(n: Int): List[A] =
    if (n <= 0) Nil else head :: tail.take(n - 1)

}

implicit val streamFunctor: Functor[Stream] =
  new Functor[Stream] {
    def map[A,B](fa: Stream[A])(f: A => B): Stream[B] =
      fa match {
        case Empty => Empty
        case c@Cons(_, _) => Cons(() => f(c.head), () => c.tail map f)
      }
  }

def range(from: Int, to: Int): Stream[Int] =
  if (from > to) Empty else Cons(() => from, () => range(from + 1, to))

val stream: Stream[Int] = range(1, 100)

val mappedStream: Stream[Int] = stream map inc map inc map inc

println("About to take...")
println(mappedStream.take(3))

inc(1) = 2
inc(2) = 3
inc(3) = 4
inc(2) = 3
inc(3) = 4
inc(4) = 5
inc(3) = 4
inc(4) = 5
inc(5) = 6
List(4, 5, 6)

Bonus

implicit class MapNth[A](fa: Stream[A]) {
  def mapNth[B >: A](f: A => B, n: Int): Stream[B] =
    fa match {
      case Empty => Empty
      case c@Cons(_, _) =>
        Cons( () => if (n == 0) f(c.head) else c.head
            , () => c.tail mapNth (f, if (n == 0) -1 else n - 1)
            )
    }
}

val mappedStream2: Stream[Int] = stream map inc mapNth (inc, 2) map inc

println("About to take...")
println(mappedStream2.take(3))

inc(1) = 2
inc(2) = 3
inc(2) = 3
inc(3) = 4
inc(3) = 4
inc(4) = 5
inc(5) = 6
List(3, 4, 6)

Demo

This file is literate Scala, and can be run using Codedown:

$ curl https://earldouglas.com/exercises/scala-transformations.md |
  codedown scala |
  xargs -0 scala -nc -e
About to take...
inc(1) = 2
inc(2) = 3
inc(3) = 4
inc(2) = 3
inc(3) = 4
inc(4) = 5
inc(3) = 4
inc(4) = 5
inc(5) = 6
List(4, 5, 6)
About to take...
inc(1) = 2
inc(2) = 3
inc(2) = 3
inc(3) = 4
inc(3) = 4
inc(4) = 5
inc(5) = 6
List(3, 4, 6)