Roll-your-own Scala

I've always really liked this passage from On the Genealogy of Morals:

[T]here is a world of difference between the reason for something coming into existence in the first place and the ultimate use to which it is put, its actual application and integration into a system of goals… anything which exists, once it has come into being, can be reinterpreted in the service of new intentions, repossessed, repeatedly modified to a new use by a power superior to it.

A couple of months ago at LambdaConf I had a few conversations with different people about why we like (or at least put up with) Scala when there are so many better languages out there. Most of the answers were the usual ones: the JVM, the ecosystem, the job market, the fact that you don't have to deal with Cabal, etc.

For me it's a little more complicated than that. I like Scala in part because it's a mess. It's not a "fully" dependently typed language, but you can get pretty close with singleton types and path dependent types. It provides higher-kinded types, but you have to work around lots of bugs and gaps and underspecified behaviors to do anything very interesting with them. And so on—it's a mix of really good ideas and a few really bad ideas and you can put them together in ways that the language designers didn't anticipate and probably don't care about at all.

The rest of this blog post will be a long story about one example of this kind of thing involving Scalaz's UnapplyProduct.

Type lambdas🔗

Type lambdas are one example of a Scala "feature" that's both hugely useful (and sometimes necessary) and apparently totally accidental. Suppose we've got a simple functor type class:

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

And we want to create an instance for the List type constructor. This is easy:

implicit val listFunctor: Functor[List] = new Functor[List] {
  def map[A, B](fa: List[A])(f: A => B): List[B] = fa.map(f)
}

Now suppose we want to create an instance for Either[String, ?]. This is a little trickier. Scala doesn't provide a direct way to partially apply a multi-parameter type constructor, but we can define a type alias with the left-hand type filled in and then use that in our instance definition:

type StringOr[A] = Either[String, A]

implicit val stringOrXFunctor: Functor[StringOr] = new Functor[StringOr] {
  def map[A, B](fa: StringOr[A])(f: A => B): StringOr[B] = fa.right.map(f)
}

This trick won't work very well if we want the left-hand type to be generic, though—there's simply no way to fit a type alias between the generic type parameter on our defining method and that method's return type. We could try to put the type alias inside the method and let the return type be inferred:

implicit def eitherFunctor[E] = {
  type EOr[A] = Either[E, A]

  new Functor[EOr] {
    def map[A, B](fa: EOr[A])(f: A => B): EOr[B] = fa.right.map(f)
  }
}

But that won't actually work:

scala> type StringOr[A] = Either[String, A]
defined type alias StringOr

scala> implicitly[Functor[StringOr]]
<console>:14: error: could not find implicit value for parameter e: Functor[StringOr]
       implicitly[Functor[StringOr]]
                 ^

Things are looking pretty bleak, but there is a way we can define this instance. It's just not the kind of thing you're likely to guess would work if you hadn't seen it before.

implicit def eitherFunctor[E]: Functor[({ type L[x] = Either[E, x] })#L] =
  new Functor[({ type L[x] = Either[E, x] })#L] {
    def map[A, B](fa: Either[E, A])(f: A => B): Either[E, B] = fa.right.map(f)
  }

This horrible syntax is an abuse of two Scala language features that at first seem completely unrelated to the task at hand: type refinements and type projections. These language features seem completely unrelated to this problem at least in part because they were designed for completely unrelated purposes—see for example this comment by Paul Phillips on a Scala issue I opened in 2012:

Type lambdas are cool and all, but not a single line of the compiler was ever written with them in mind. They're just not going to work right: the relevant code is not robust.

This is one of the nice things about creating cool stuff by accident—you don't have to support it (even when it becomes an idiomatic part of the language—type lambdas for example have had special support in IntelliJ for years, and kind-projector, a compiler plugin that provides syntactic sugar for type lambdas, is becoming increasingly widely used).

SI-2712🔗

Now that we've got a functor instance for any Either[E, ?] we probably want to be able to use it in methods like the following:

def incrementInside[F[_]: Functor](fa: F[Int]): F[Int] =
  implicitly[Functor[F]].map(fa)(_ + 1)

Which works like this on lists:

scala> val myList = List(1, 2, 3)
myList: List[Int] = List(1, 2, 3)

scala> val myIncrementedList = incrementInside(myList)
myIncrementedList: List[Int] = List(2, 3, 4)

And like this on Either:

val myEither: Either[String, Int] = Right(1)
val myIncrementedEither: Either[String, Int] = incrementInside(myEither)

Just kidding, that doesn't actually compile. Scala isn't capable of figuring out that Either[String, Int] can be seen as a F[Int] where F is Either[String, ?] (which of course we have a functor instance for).

This limitation is tracked in SI-2712, an issue that will celebrate its sixth birthday this November (it's also one of the five or six Scala issues that I can recognize by number).

Fortunately there's (another) workaround, due originally to Miles Sabin and now available in both Scalaz and cats:

trait Unapply[TC[_[_]], MA] {
  type M[_]
  type A
  def instance: TC[M]
  def apply(ma: MA): M[A]
}

object Unapply {
  implicit def unapplyMA[TC[_[_]], M0[_], A0](implicit
    instance0: TC[M0]
  ): Unapply[TC, M0[A0]] {
    type M[X] = M0[X]
    type A = A0
  } = new Unapply[TC, M0[A0]] {
    type M[X] = M0[X]
    type A = A0
    def instance = instance0
    def apply(ma: M0[A0]): M[A] = ma
  }

  implicit def unapplyMAB[TC[_[_]], M0[_, _], A0, B0](implicit
    instance0: TC[({ type L[x] = M0[A0, x] })#L]
  ): Unapply[TC, M0[A0, B0]] {
    type M[x] = M0[A0, x]
    type A = B0
  } = new Unapply[TC, M0[A0, B0]] {
    type M[x] = M0[A0, x]
    type A = B0
    def instance = instance0
    def apply(ma: M0[A0, B0]): M[A] = ma
  }
}

Now we can rewrite our incrementInside method like this:

def incrementInside[FA](fa: FA)(implicit
  U: Unapply[Functor, FA] { type A = Int }
): U.M[Int] = U.instance.map(U(fa))(_ + 1)

And then:

scala> incrementInside(myList)
res4: List[Int] = List(2, 3, 4)

scala> incrementInside(myEither)
res5: scala.util.Either[String,Int] = Right(2)

Fortunately in practice we usually only need to define methods that take an Unapply instance for a small handful of generic operations (a common convention is to add a U to the end of the method name to distinguish these versions—so for example in Scalaz the syntax for Traverse provides both traverse and traverseU methods).

So now we've used implicit resolution to work around a limitation involving higher-order unification for a type class instance that we defined using type refinements and type projections to work around a limitation involving partial application of type parameters. Next we'll add even more dead body parts to the monster.

Multiple implicit parameter sections🔗

Sometimes we need more complex Unapply machinery than the relatively simple version above. One example is syntax for things that are bitraversable. For example, we might want to take a tuple (or Either) and do some kind of logging in a Writer monad for both sides (or either):

import scalaz._, Scalaz._

(1, 'a).bitraverseU(_.set("saw int" :: Nil), _.set("saw sym" :: Nil))

This in effect lets us map two functions returning writers over the two sides of our tuple and then turn the whole thing inside out, giving us a writer that logs to a list of strings and returns a (Int, Symbol). We need the bitraverseU version again because of SI-2712—the Scala compiler isn't able to recognize the pieces it needs in the return types of the functions we're mapping over the two sides.

Unfortunately this doesn't actually work in Scalaz at the moment. It relies on an Unapply variant called UnapplyProduct that was added to Scalaz in 2011 by Jason Zaugg, but it's always been necessary to construct these instances by hand (which is extremely inconvenient and boilerplate-y). From Jason's original comments, which are still in the source today:

// This seems to motivate multiple implicit parameter sections. Is there another way?

And:

// Would be nice, but I'm not sure we can conjure UnapplyProduct implicitly, at least without multiple implicit
// parameter lists.

The issue is that the signature for the implicit method that generates UnapplyProduct instances seems to need to look like the following, since we have to confirm that the M types in our Unapply instances for the left and right sides are the same:

implicit def unapply[TC[_[_]], MA0, MB0](implicit
  U1: Unapply[TC, MA0],
  U2: Unapply[TC, MB0]
)(implicit iso: U1.M <~> U2.M): UnapplyProduct[TC, MA0, MB0] { // ...

Scala doesn't allow types to be referred to by other types in the same parameter list, so we can't just stick the <~> in with the other instances. The problem is that Scala also doesn't support multiple implicit parameter lists. This is a more arbitrary limitation, but I've never seen any serious discussion of changing it.

So we're out of luck. I should know by now that if Jason Zaugg is asking for help on a problem, I should stay away from it, but over the past three or four years I've burned at least two or three Saturdays trying to find a way to implement this unapply method.

More workarounds!🔗

In February Miles Sabin posted a gist demonstrating what he called "a new approach to encoding dependently-typed chained implicits, using singleton types". It's a pretty clever trick, and my first thought when I saw it was that we could use it to fix Scalaz's UnapplyProduct. And it worked, although I didn't get around to submitting a pull request until this week.

The implementation looks like this:

case class SingletonOf[T, U <: { type A; type M[_] }](
  widen: T { type A = U#A; type M[x] = U#M[x] }
)

object SingletonOf {
  implicit def mkSingletonOf[T <: { type A; type M[_] }](implicit
    t: T
  ): SingletonOf[T, t.type] = SingletonOf(t)
}

implicit def unapply[
  TC[_[_]],
  MA0,
  MB0,
  U1 <: { type A; type M[_] },
  U2 <: { type A; type M[_] }
](implicit
  sU1: SingletonOf[Unapply[TC, MA0], U1],
  sU2: SingletonOf[Unapply[TC, MB0], U2],
  iso: U1#M <~> U2#M
): UnapplyProduct[TC, MA0, MB0] {
  type M[x] = U1#M[x]
  type A = U1#A
  type B = U2#A
} = new UnapplyProduct[TC, MA0, MB0] {
  type M[x] = U1#M[x]
  type A = U1#A
  type B = U2#A
  def TC = sU1.widen.TC
  def _1(ma: MA0) = sU1.widen(ma)
  def _2(mb: MB0) = iso.from(sU2.widen(mb))
}

The key idea is that the U1 and U2 type parameters will be inferred to be the singleton types for our two Unapply instances, and our SingletonOf type class captures the way that these types line up with our TC, MA0, and MB0. This allows us to refer to the M type parameters for the Unapply instances in the same implicit parameter list that gathers the Unapply instances themselves (or rather their SingletonOf wrappers).

Note that SingletonOf here is less generic than Miles's original formulation, which would also work if we were willing to do some (safe) casting. Since this is the only interesting application that I can think of for this trick, I'm not worried about using a less generic formulation.

To demonstrate that it works, you can check out my pull request and run something like the following:

import scalaz._, Scalaz._

val w = (1, 'a).bitraverseU(_.set("saw int" :: Nil), _.set("saw sym" :: Nil))

And then:

scala> w.run
res0: (List[String], (Int, Symbol)) = (List(saw int, saw sym),(1,'a))

To recap: we've taken a few basic (but still pretty broken) Scala language features—singleton types, refinement types, type projections, and the implicit resolution system—and we've very painfully built a language for ourselves that at least kind of looks like it supports partial type parameter application, higher-order unification, and multiple implicit parameter sections.

I think that's pretty neat, but I can also understand why almost everyone else would find it horrifying.

home

Roll-your-own Scala

Type lambdas🔗

SI-2712🔗

Multiple implicit parameter sections🔗

More workarounds!🔗