Monthly Archives: August 2020

Traversing A Scala Collection

Leave a reply

When we have a custom class in the form of an ADT, say, `Container[A]` and are required to process a collection of the derived objects like `List[Container[A]]`, there might be times we want to flip the collection “inside out” to become a single “container” of collection `Container[List[A]]`, and maybe further transform the inner collection with a function.

For those who are familiar with Scala Futures, the nature of such transformation is analogous to what method Future.sequence does. In case the traversal involves also applying to individual elements with a function, say, `f: A => Container[B]` to transform the collection into `Container[List[B]]`, it’ll be more like how Future.traverse works.

To illustrate how we can come up with methods `sequence` and `traverse` for the collection of our own ADTs, let’s assemble a simple ADT `Fillable[A]`. Our goal is to create the following two methods:

  def sequence[A](listFA: List[Fillable[A]]): Fillable[List[A]]
  def traverse[A, B](list: List[A])(f: A => Fillable[B]): Fillable[List[B]]

For simplicity, rather than a generic collection like IterableOnce, we fix the collection type to `List`.

A simple ADT

sealed trait Fillable[A]
case class Filled[A](a: A) extends Fillable[A]
case object Emptied extends Fillable[Nothing]

It looks a little like a home-made version of Scala `Option`, but is certainly not very useful yet. Let’s equip it with a companion object and a couple of methods for transforming the element within a `Fillable`:

sealed trait Fillable[+A] { self =>
  def map[B](f: A => B): Fillable[B] = self match {
    case Filled(a) => Filled(f(a))
    case Emptied   => Emptied
  }

  def flatMap[B](f: A => Fillable[B]): Fillable[B] = self match {
    case Filled(a) => f(a)
    case Emptied   => Emptied
  }
}

object Fillable {
  def apply[A](a: A): Fillable[A] = Filled(a)
}

case class Filled[A](a: A) extends Fillable[A]

case object Emptied extends Fillable[Nothing]

With slightly different signatures, methods `map` and `flatMap` are now available for transforming the element “contained” within a `Fillable`.

A couple of quick notes:

  • Fillable[A] is made covariant so that method `map/flatMap` is able to operate on subtypes of `Fillable`.
  • Using of self-type annotation isn’t necessary here, but is rather a personal coding style preference.

Testing the ADT:

val listF: List[Fillable[String]] = List(Filled("a"), Filled("bb"), Emptied, Filled("dddd"))

Filled("bb").map(_.length)
// res1: Fillable[Int] = Filled(2)

Filled("bb").flatMap(s => Fillable(s.length))
// res2: Fillable[Int] = Filled(2)

listF.map(_.map(_.length))
// res3: List[Fillable[Int]] = List(Filled(1), Filled(2), Emptied, Filled(4))

Sequencing a collection of Fillables

Let’s assemble method `sequence` which will reside within the companion object. Looking at the signature of the method to be defined:

  def sequence[A](listFA: List[Fillable[A]]): Fillable[List[A]]

it seems logical to consider aggregating a `List` from scratch within `Fillable` using Scala `fold`. However, trying to iteratively aggregate a list out of elements from within their individual “containers” isn’t as trivial as it may seem. Had there been methods like `get/getOrElse` that unwraps a `Fillable` to obtain the contained element, it would’ve been straight forward – although an implementation leveraging a getter method would require a default value for the contained element to handle the `Emptied` case.

One approach to implement `sequence` using only `map/flatMap` would be to first `map` within the `fold` operation each `Fillable` element of the input `List` into a list-push function for the element’s contained value, followed by a `flatMap` to aggregate the resulting `List` by iteratively applying the list-push functions within the `Fillable` container:

  def pushToList[A](a: A)(la: List[A]): List[A] = a :: la

  def sequence[A](listFA: List[Fillable[A]]): Fillable[List[A]] =
    listFA.foldRight(Fillable(List.empty[A])){ (fa, acc) =>
      fa match {
        case Emptied => acc
        case _       => fa.map(pushToList).flatMap(acc.map)
      }
    }

Note that `pushToList` within `map` is now regarded as a function that takes an element of type `A` and returns a `List[A] => List[A]` function. The expression `fa.map(pushToList).flatMap(acc.map)` is just a short-hand for:

  fa.map(a => pushToList(a)).flatMap(fn => acc.map(fn))

In essence, the first `map` transforms element within each `Fillable` in the input list into a corresponding list-push function for the specific element, and the `flatMap` uses the individual list-push functions for the inner `map` to iteratively aggregate the list inside the resulting `Fillable`.

Traversing the Fillable collection

Next, we’re going to define method `traverse` with the following signature within the companion object:

 def traverse[A, B](list: List[A])(f: A => Fillable[B]): Fillable[List[B]]

In case it doesn’t seem obvious, based on the method signatures, `sequence` is really just a special case of `traverse` with `f(a: A) = Fillable(a)`

Similar to the way `sequence` is implemented, we’ll also use `fold` for iterative aggregating the resulting list. Since an element of type Fillable[A] when `flatMap`-ed with the provided function `f` would yield a Fillable[B], we’re essentially dealing with the same problem we did for `sequence` except that we type `A` is now replaced with type `B`.

  def traverse[A, B](list: List[A])(f: A => Fillable[B]): Fillable[List[B]] =
    list.foldRight(Fillable(List.empty[B])) { (a, acc) =>
      val fb = f(a)
      fb match {
        case Emptied => acc
        case _ => fb.map(pushToList).flatMap(acc.map)
      }
    }

Putting everything together:

sealed trait Fillable[+A] { self =>
  def map[B](f: A => B): Fillable[B] = self match {
    case Filled(a) => Filled(f(a))
    case Emptied   => Emptied
  }

  def flatMap[B](f: A => Fillable[B]): Fillable[B] = self match {
    case Filled(a) => f(a)
    case Emptied   => Emptied
  }
}

object Fillable {
  def apply[A](a: A): Fillable[A] = Filled(a)

  def pushToList[A](a: A)(la: List[A]): List[A] = a :: la

  def sequence[A](listFA: List[Fillable[A]]): Fillable[List[A]] =
    listFA.foldRight(Fillable(List.empty[A])){ (fa, acc) =>
      fa match {
        case Emptied => acc
        case _       => fa.map(pushToList).flatMap(acc.map)
      }
    }

  def traverse[A, B](list: List[A])(f: A => Fillable[B]): Fillable[List[B]] =
    list.foldRight(Fillable(List.empty[B])) { (a, acc) =>
      val fb = f(a)
      fb match {
        case Emptied => acc
        case _ => fb.map(pushToList).flatMap(acc.map)
      }
    }
}

case class Filled[A](a: A) extends Fillable[A]

case object Emptied extends Fillable[Nothing]

Testing with the newly created methods:

val listF: List[Fillable[String]] = List(Filled("a"), Filled("bb"), Emptied, Filled("dddd"))

Fillable.sequence(listF)
// res1: Fillable[List[Int]] = Filled(List(a, bb, dddd))

val list: List[String] = List("a", "bb", "ccc", "dddd")

Fillable.traverse[String, Int](list)(a => Fillable(a.length))
// res2: Fillable[List[Int]] = Filled(List(1, 2, 3, 4))

Fillable.traverse[String, Int](list)(_ => Emptied)
// res3: Fillable[List[Int]] = Filled(List())