Scala is growing on me very fast. Here are some thoughts on a refactoring technique, spun from an example of slightly iffy writing I saw online.

To quickly give the lay of the land - suppose one has a finite but arbitrarily large series of datesets with associated types A, B, C, ... R, each type wrapped with some common external dimensions that one wants to join on. These joins happen pairwise and it is uncertain whether we will get the left, right, or both sides. In each join, then, we go from types X and Y to an algebraic joined type Tuple2[Option[X], Option[Y]]. Once all of these are joined, we want a case class out of the other end, looking something like:

case class Combo(maybeA: Option[A],
                 maybeB: Option[B],
                 ...
                 maybeR: Option[R])

Now in the example I saw, unpacking to this case class was done by a lot of very long chains of .flatMap(_.left).flatMap(_.right).... Not only are these hard to read, they obscure something important; we only actually want the ordering of the values. For our purposes here, these pairings should be asscociative. That is to say, we can quotient under Tuple2[P, Tuple2[Q, R]] ~ Tuple2[Tuple2[P, Q], Option[R] (where each of P, Q, R are Options). The obvious solution, then, is to use a list-style data type. For this sort of generic programming, shapeless is the obvious bet in Scala, and it gives us a lot for free.

The suggestion, then, is that we can lift a type U to type Option[U] :: HNil (this can in fact be specified as a monadic unit). This gives us an HList where each element subtypes Option - we’ll call this a KList[Option] type. Then given a pair of KList[Option]s, be they lifted from a single type or a product of multiple of our initial types, we can concatenate them to get a third, as:

(Option[A] :: Option[B] ::  ... ::  Option[C] :: HNil) 
    ++ (Option[P] :: Option[Q] :: ... :: Option[R] :: HNil) 
    = Option[A] :: ... :: Option[C] 
        :: Option[P] :: ... :: Option[R] :: HNil

And there we go, we’ve unravelled our left/right tangle into a single ordered list, without even having to do anything, by leaning on shapeless and a simple monad. More to the point, we can now utilise the full power of shapeless to easily populate a Combo from this, with Generic[Combo].from.

At this point we notice an issue; our types might match up, but what happens when we have an HList which is None in the join? Given a type T, where T is an KList[Option], how does one construct the instance of T where each of its contained values are None? In other words, we want to build the following map from KList[Option] types to KList[Option] instances:

Option[A] :: Option[B] :: ... :: Option[R] :: HNil 
    ⟼ Option.empty[A] :: Option.empty[B] :: ... :: Option.empty[R] :: HNil

The solution proved a little tricky to spot, but here we go. One can define a trait which, for conformance, requires defining a generator for the instance we want.

trait ProvidesHListOfNones[T] {
    def getHListOfNones: T
}

Now we need to make this work when T is a KList[Option]. We can go via implicits to create a dependently typed function.

object ProvidesHListOfNones {
    implicit def caseHNil: ProvidesHListOfNones[HNil] = new ProvidesHListOfNones[HNil] {
        def getHListOfNones: HNil = HNil
    }
    implicit def caseCompoundHList[H, T <: HList : *->*[Option]#λ](implicit tail: ProvidesHListOfNones[T]): ProvidesHListOfNones[Option[H] :: T] = 
        new ProvidesHListOfNones[Option[H] :: T] {
            def getHListOfNones: Option[X] :: T = None :: tail.getHListOfNones
    }
}

Note that in the second one here, we are using a context type bound to force this to only be applied to KList[Option] types. We don’t want to accidentally provide this conformance further afield.

Now so long as we provide a finite KList[Option] type, the compiler will be able to recursively apply these implicits to construct evidence that it conforms to ProvidesHListOfNones[T]. However, we have to tell the compiler to actually try and find this conformance. So, if we want to use this somewhere, we need to do the following:

def funcThatWantsTheInstance[U <: HList : *->*[Option]#λ](implicit evidence: ProvidesHListOfNones[U]) = {
    ...
    evidence.getHListOfNones
    // or...
    implicitly[ProvidesHListOfNones[U]].getHListOfNones
    ...
}

Again, note the context bound - this forces U to be be both a KList[Option] and to satisfy ProvidesHListOfNones.

And there we go! I won’t get into the compile-time or runtime performance details of this approach, but purely from a readability standpoint, I thought this made for a very cute solution.