Joining the dots on recent Implicit Prioritization changes and some Scala history

Language Design
1

For those of us using typeclass-based (TC) abstraction hierarchies, including Cats & Typelevel libraries, I’m not sure the full impact of the recent change to implicit resolution has been fully appreciated, nor its link to historical events fully traced.

As the PR and associated recent blog entry describe, the implicit resolution algorithm now searches for the most general, and not the most specific, given type that satisfies the constraint.

To steal from the classic blog post example, this addresses an age-old problem that crops up when combining multiple typeclass constraints in Cats:

trait Functor[F[_]]:
  extension [A, B](x: F[A]) def map(f: A => B): F[B]
trait Monad[F[_]] extends Functor[F] { ... }
trait Traverse[F[_]] extends Functor[F] { ... }

def fmap[F[_] : Functor, A, B](c: F[A])(f: A => B): F[B] = c.map(f)

fmap(List(1,2,3))(_.toString)
// ^ rejected by Scala < 3.7, now accepted by Scala 3.7

This problem was popularized by a 2016/7 blog and talk by Adelbert Chang (who no longer seems to be involved with Scala), The Limitations of Type Classes as Subtyped Implicits.

This led to several long threads Think about type class/implicits encoding and Allow Typeclasses to Declare Themselves Coherent.

One approach to the ambiguity problem that saw some adoption (example by @armanbilge) was the so-called “Scato encoding”. The gist of it is that typeclasses don’t inherit/subtype one another, but rather subtypes contain members that reference their superclasses.

Overall, the above-linked discussions tended to drift towards some idea of “Coherence” (an idea from Haskell) and my impression is that may have been a false path. Actually, I think @kai deserves some more recognition for one of the earliest proposals resembling what’s made it into Scala 3.6.

I am intrigued by how, after much discussion, a fairly simple inversion of the prioritization rules seems sufficient to address at least the classic Monad+Traverse example of this TC-inheritance problem.

When I recently compiled an existing TC-based codebase with Scala 3.6 for the first time, I did notice a number of warnings appear where different given instances would now be selected. In my case at least, each of the changes seemed desirable and correct; preferring Cats’ Eq over Order for equality comparisons, for example.

However, it will be interesting to see, as this change makes its way “into the wild”, whether it proves problematic at scale, or if new problems are identified as a consequence…

11 Likes
2

Actually I thought the classic Monad<->Traverse problem was the following:

def foo[F[_] : Traverse : Monad, A, B](c: F[A])(f: A => B): F[B] =
  c.map(f)
    ^^^^^^ ambiguity

Is that also solved by this change?

1 Like
3

Is that also solved by this change?

Yes, because you can now write

def foo[F[_] : {Functor, Traverse, Monad}, A, B](c: F[A])(f: A => B): F[B] =
  c.map(f)

and it will resolve to the Functor. Previously, adding the common superclass would have made ambiguities worse. Now, it solves the problem.

1 Like
4

Indeed, thanks for holding me to account, that is often the way the problem would show up in the wild.

As @odersky notes, we now need to “annotate” the TC constraint at the class (or classes :wink: ) where the two arms intersect. The arms here being Traverse and Monad and the intersection being Functor.

Of course, in Scala’s multi-inheritance model there might be more than one such intersection. How bad could it get, in practice? To estimate that, I tried to concoct a deliberately problematic arrangement using the fairly extensive cats.algebra hierarchy. I was able to require two additional TC constraints, on two distinct intersections above Rng & Semifield (scastie):

object Test:
  import algebra.*
  import algebra.ring.*
  def foo[N: AdditiveMonoid: MultiplicativeSemigroup: Rng: Semifield]: Unit =
    val zero = AdditiveMonoid[N].zero
    MultiplicativeSemigroup[N].times(zero, zero)
    Rng[N].negate(zero)
    Semifield[N].reciprocal(zero)

Can anyone do worse? ie find a real-world-ish example that requires 3 additional TC constraints to eliminate all ambiguity…

1 Like