Thursday, November 12, 2009

Another encoding of typeclasses in Scala

I've been thinking about different ways of doing typeclass-like things in Scala, using Scala's first-class modules (aka objects), and functions over these modules (aka classes). More generally, I'm interested in exploring whether there's anything as convenient as typeclasses that could be implemented in a dynamic language.

Haskell's typeclasses can be encoded pretty directly in Scala, using an implicit module derived from some polymorphic type parameter:
  def dot[A](a: List[A], b: List[A])(
implicit r: Ring[A]): A = ...

def sequence[M[_],A](l: List[M[A]])(
implicit a: Applicative[M]): M[List[A]] = ...
From what I understand, Haskell's implementation of typeclasses works similarly: bounded polymorphic functions receive one or more hidden dictionary (module) parameters. Except in Haskell modules are not first class objects that the programmer can access or manipulate. (Although I'm unsure how much of a restriction this is.)

Given that modules are first class in Scala, though, why don't we just pass the module in at some outer scope?
  class ApplicativeM[M[_]](a: Applicative[M]) {
def sequence[A](l: List[M[A]]): M[List[A]] = ...
// other Applicative derived functions here
We can then put all the Applicative-derived functions nested within the body of this class. If we then give a name to our ApplicativeM[List] instance, like ListA, we can have syntax like ListA.sequence(blah), which is almost the best you can do. One thing I like about this is we avoid having to restate the bound for each and every Applicative-derived function - all functions simply reference M, where the bound on M is stated in the outer scope.

Incidentally, this sounds very similar to the encoding discussed here:
The translation from Haskell type classes to ML modules encodes type classes as signatures and instances of type classes as functors that yield structures of these signatures.
Sidebar question for ML people: In ML, can you have higher-kinded modules like Applicative, and can ML functors receive such modules as arguments? Or are you limited to accepting first-order modules like Ring?

Per-function implicit parameters is still more flexible, though, since it allows the functions derived from a typeclass to be spread out over multiple modules. The most logical place to put a function isn't necessarily in the module with the typeclass definition since the bound is often somewhat incidental. Per-function implicits scale better, too - you don't need to have a separate module for every combination of type bounds (although I doubt very many combinations occur in real programs).

I wonder if it would be possible to get around this first restriction somehow by adding a few operators to modules - perhaps union, subtraction, and renaming?


Jorge Ortiz said...

In Scala 2.8, the first encoding can be made a little less verbose with the new "context bound" feature. Your two definitions are equivalent to:

def dot[A : Ring](a: List[A], b: List[A]) = ...
def sequence[M[_] : Applicative, A](l: List[M[A]]): M[List[A]] = ...

The implicit instances of Ring[A] and Applicative[M] can be recovered using the new method "implicitly" defined in Predef:


Paul Chiusano said...

@Jorge - yes that's not bad. Although if you end up having to call implicitly anyway, you don't really save much typing.

Jason Zaugg said...

You might like to take a look at Scalaz 5, which has an extensive array of type classes and instances, and convenient object oriented invocation.

We take the type class instances as method parameters. Many methods require more than one type class.

Start with Scalaz, Identity, MA, Pure, Bind, Monad.

The context bounds can still be useful if you only need to pass the implicit param on to another call. For example, see Show.IterableShow or ListW.takeWhileM, or Pure.Tuple2Pure.

George said...

In regards to your ML question, although it didn't make it into the Definition of Standard ML, most variants of Standard ML support some form of higher-order functors as does OCaml. The semantics of this feature (primarily its interaction with generative types) varies considerably among the different implementations and formal developments.