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:

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

A simple ADT

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:

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:

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:

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:

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:

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:

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.

Putting everything together:

Testing with the newly created methods: