Menu

Subtype type classes don't work

The common encoding of type classes in Scala relies on subtyping. This singular fact gives us a certain cleanliness in the code, but at what cost?

Problem

Consider the following hierarchy of type classes. A similar hierarchy can be found in both Cats and Scalaz 7.

trait Functor[F[_]]

trait Applicative[F[_]] extends Functor[F]

trait Monad[F[_]] extends Applicative[F]

trait Traverse[F[_]] extends Functor[F]

For purposes of demonstration I will be using Cats for the rest of this post, but the same arguments apply to Scalaz 7.

We will also assume that there is syntax accompanying this hierarchy, allowing us to call methods like map, flatMap, and traverse directly on some F[A], provided F has the appropriate type class instances (Functor, Monad, and Traverse, respectively).

import cats._
import cats.implicits._

One important consequence is we can use for comprehensions in methods parameterized over some Monad.

def foo[F[_]: Monad]: F[Int] = for {
  a <- Monad[F].pure(10)
  b <- Monad[F].pure(20)
} yield a + b

Notice that due to how for comprehensions desugar, there is also a call to map in there. Since our type class hierarchy is encoded via subtyping Scala knows a Monad[F] implies a Functor[F], so all is well. Or is it?

Consider a case where we want to abstract over a data type that has both Monad and Traverse.

// Ignore the fact we're not even using `Traverse` - we can't even call `map`!
def foo[F[_]: Monad: Traverse]: F[Int] = Monad[F].pure(10).map(identity)
// <console>:19: error: value map is not a member of type parameter F[Int]
//        def foo[F[_]: Monad: Traverse]: F[Int] = Monad[F].pure(10).map(identity)
//                                                                   ^
// <console>:19: error: missing argument list for method identity in object Predef
// Unapplied methods are only converted to functions when a function type is expected.
// You can make this conversion explicit by writing `identity _` or `identity(_)` instead of `identity`.
//        def foo[F[_]: Monad: Traverse]: F[Int] = Monad[F].pure(10).map(identity)
//                                                                       ^

We’re already in trouble. In order to call map we need F to have a Functor instance, which it does via Monad as before.. but now also via Traverse. It is for precisely this reason that this does not work. Because our encoding of type classes uses subtyping, a Monad[F] is a Functor[F]. Similarly, a Traverse[F] is a Functor[F]. When implicit resolution attempts to find a Functor[F], it can’t decide between Monad[F]’s or Traverse[F]’s and bails out. Even though the instances may be, and arguably should be, the same, the compiler has no way of knowing that.

This problem generalizes to anytime the compiler decides an implicit is ambiguous, such as method calls.

// The fact we don't actually use `Functor` here is irrelevant.
def bar[F[_]: Applicative: Functor]: F[Int] = Applicative[F].pure(10)
def callBar[F[_]: Monad: Traverse]: F[Int] = bar[F]
// <console>:19: error: ambiguous implicit values:
//  both value evidence$2 of type cats.Traverse[F]
//  and value evidence$1 of type cats.Monad[F]
//  match expected type cats.Functor[F]
//        def callBar[F[_]: Monad: Traverse]: F[Int] = bar[F]
//                                                        ^

What do we do? For map it is easy enough to arbitrarily pick one of the instances and call map on that. For function calls you can thread the implicit through explicitly.

def foo[F[_]: Monad: Traverse]: F[Int] = Monad[F].map(Monad[F].pure(10))(identity)

def callBar[F[_]: Monad: Traverse]: F[Int] = bar(Monad[F], Monad[F])
                                       // or bar(Monad[F], Traverse[F])

For foo it’s not too terrible. For bar though we are already starting to see it get unwieldy. While we could have passed in Monad[F] or Traverse[F] for the second parameter which corresponds to bar’s Functor[F] constraint, we can only pass in Monad[F] for the first parameter to satisfy Applicative[F]. Because implicit resolution can’t disambiguate the Functor[F] by itself we’ve had to pass it in explicitly, but by doing so we also have to pass in everything else explicitly! We become the implicit resolver. And this is with just two constraints, what if we had three, four, five?

And the trouble doesn’t end there. We asked for a Monad so let’s try using a for comprehension.

def foo[F[_]: Monad: Traverse]: F[Int] = for {
  a <- Monad[F].pure(10)
  b <- Monad[F].pure(20)
} yield a + b
// <console>:21: error: value map is not a member of type parameter F[Int]
//          b <- Monad[F].pure(20)
//                            ^

This is also broken! Because of how for comprehensions desugar, a map call is inevitable which leads to the for comprehension breaking down. This drastically reduces the ergonomics of doing anything monadic.

As with map we could call flatMap on Monad directly, but this quickly becomes cumbersome.

def foo[F[_]: Monad: Traverse]: F[Int] = {
  val M = Monad[F]
  M.flatMap(M.pure(10)) { a =>
    M.map(M.pure(20)) { b =>
      a + b
    }
  }
}

These same problems arise if you ask for two or more type classes that share a common superclass. Some examples of this:

This suggests every type class have only one subclass. That is quite limiting as is readily demonstrated by the extremely useful Applicative and Traverse type classes. What do we do?

Solution (?)

This more or less remains an open problem in Scala. There has been an interesting alternative prototyped in scato, now making its way to Scalaz 8, that has received some positive feedback. The gist of the encoding completely throws out the notion of subtyping, encoding the hierarchy via members instead.

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

trait Applicative[F[_]] {
  def functor: Functor[F]

  def pure[A](a: A): F[A]
  def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C]
}

// Definitions elided for space
trait Monad[F[_]] { def applicative: Applicative[F] }

trait Traverse[F[_]] { def functor: Functor[F] }

Because there is no relation between the type classes, there is no danger of implicit ambiguity. However, for that very reason, having a Monad[F] no longer implies having a Functor[F]. Not currently anyway. What we can do is use implicit conversions to re-encode the hierarchy.

implicit def applicativeIsFunctor[F[_]: Applicative]: Functor[F] =
  implicitly[Applicative[F]].functor

implicit def traverseIsFunctor[F[_]: Traverse]: Functor[F] =
  implicitly[Traverse[F]].functor

But now we’re back to square one.

// Syntax for Functor
implicit class FunctorOps[F[_], A](fa: F[A])(implicit F: Functor[F]) {
  def map[B](f: A => B): F[B] = F.map(fa)(f)
}
def foo[F[_]: Applicative: Traverse]: F[Int] =
  implicitly[Applicative[F]].pure(10).map(identity)
// <console>:19: error: value map is not a member of type parameter F[Int]
//          implicitly[Applicative[F]].pure(10).map(identity)
//                                              ^
// <console>:19: error: missing argument list for method identity in object Predef
// Unapplied methods are only converted to functions when a function type is expected.
// You can make this conversion explicit by writing `identity _` or `identity(_)` instead of `identity`.
//          implicitly[Applicative[F]].pure(10).map(identity)
//                                                  ^

Since both implicits have equal priority, the compiler doesn’t know which one to pick. However, Scala has mechanisms for prioritizing implicits which solves the problem.

object Prioritized { // needed for tut, irrelevant to demonstration
  trait Functor[F[_]] {
    def map[A, B](fa: F[A])(f: A => B): F[B]
  }

  // Prioritize implicit conversions - Functor only for brevity
  trait FunctorConversions1 {
    implicit def applicativeIsFunctor[F[_]: Applicative]: Functor[F] =
      implicitly[Applicative[F]].functor
  }

  trait FunctorConversions0 extends FunctorConversions1 {
    implicit def traverseIsFunctor[F[_]: Traverse]: Functor[F] =
      implicitly[Traverse[F]].functor
  }

  object Functor extends FunctorConversions0

  trait Applicative[F[_]] {
    def functor: Functor[F]

    def pure[A](a: A): F[A]
    def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C]
  }

  // Definition elided for space
  trait Traverse[F[_]] { def functor: Functor[F] }

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

  def foo[F[_]: Applicative: Traverse]: F[Int] = {
    implicitly[Applicative[F]] // we have Applicative
    implicitly[Traverse[F]]    // we have Traverse
    implicitly[Functor[F]]     // we also have Functor!

    // and we have syntax!
    implicitly[Applicative[F]].pure(10).map(identity)
  }
}

Because implicit resolution treats implicits in subtypes with higher priority, we can organize conversions appropriately to prevent ambiguity. Here this means that applicativeIsFunctor has lower priority than traverseIsFunctor, so when both Applicative and Traverse instances are in scope and the compiler is looking for a Functor, traverseIsFunctor wins.

One thing to note is that we’ve baked the implicit hierarchy into Functor itself - in general this means all superclasses are aware of their subclasses. This is convenient from a usability perspective as companion objects are considered during implicit resolution, but from a modularity perspective is strange and in this case would prevent extensions to the hierarchy from external sources. This can be solved by removing the hierarchy from the superclasses (removing Functor’s extends FunctorConversions0), but comes at the cost of needing an import at use sites to bring the implicits into scope.

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

trait Applicative[F[_]] {
  def functor: Functor[F]

  def pure[A](a: A): F[A]
  def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C]
}

trait Traverse[F[_]] { def functor: Functor[F] }

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

// Separate from type class definitions

trait FunctorConversions1 {
  implicit def applicativeIsFunctor[F[_]: Applicative]: Functor[F] =
    implicitly[Applicative[F]].functor
}

trait FunctorConversions0 extends FunctorConversions1 {
  implicit def traverseIsFunctor[F[_]: Traverse]: Functor[F] =
    implicitly[Traverse[F]].functor
}

object Prelude extends FunctorConversions0
// Need this import to get implicit conversions in scope
import Prelude._

def foo[F[_]: Applicative: Traverse]: F[Int] = {
  implicitly[Applicative[F]]
  implicitly[Traverse[F]]
  implicitly[Functor[F]]

  implicitly[Applicative[F]].pure(10).map(identity)
}

Prelude could be provided by the base library, but external libraries with their own type classes can still extend the hierarchy and provide their own Prelude.

A more developed form can be seen in the BaseHierarchy of Scalaz 8.

Do we win? I’m not sure. This encoding is certainly more cumbersome than what we started with, but solves the problems we ran into.

Compromise?

Another thing we can try is to make some compromise of the two. We can continue to use subtyping for a blessed subset of the hierarchy, and use members for any branching type class.

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

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

trait Applicative[F[_]] extends Functor[F] {
  def pure[A](a: A): F[A]
  def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C]
}

trait Monad[F[_]] extends Applicative[F]

trait Traverse[F[_]] { def functor: Functor[F] }

def foo[F[_]: Applicative: Traverse]: F[Int] =
  implicitly[Applicative[F]].pure(10).map(identity)

This works, but is even messier than the alternatives. We have to decide which type classes get to live in the subtype hierarchy and which are doomed (blessed?) to express the relationship with members. But maybe the pros outweigh the cons. Pull requests with this change have been filed for Cats and Scalaz 7.3.

I’m not convinced that the story is over though. Maybe there’s another solution yet to be discovered.

For further reading, there are open tickets for both Cats and Scalaz 7 documenting the subtyping problem. A discussion around the Scato encoding for Scalaz 8 can be found here.

This article was tested with Scala 2.11.8 and Cats 0.7.2 using tut.

Licensing

Unless otherwise noted, all content is licensed under a Creative Commons Attribution 3.0 Unported License.

Back to blog
comments powered by Disqus