Matt Hellige / blog

I apologize for what you're about to see...

As a little experiment, I decided to translate part of this pearl from Haskell to Scala. By this I mean literal translation, as opposed to an idiomatic implementation in Scala. Of course, this goes deeply against the grain of the Scala language. On the other hand, as I wrote here:

It certainly cuts across the grain of current practice, and the grain of the libraries. But I think it takes a long time to discern the grain of a language. And I think it takes a lot of pushing and prodding, which is why I think this kind of experimentation is so important.

For now, it's a reasonable default to stick to a style that reflects the origins of the language (mostly Java-style OO with some functional goodies and richer types). I definitely think we should be open to the possibility that Scala style will diverge more radically from this tradition.

At this point, I'd probably replace the word "important" with "fun and maybe sort of worthwhile." Anyway, let's get started...

I won't really explain what's going on. For that, please see the original paper. I'll only discuss the Scala novelties. First, a couple of terms, leaving the recursion open:

case class Val[E](i: Int)
case class Add[E](left: E, right: E)

Now the fixed point operator:

case class Expr[F[X]](e: F[Expr[F]])

You might think of this as a somewhat perverse way of making types like Val and Add subclasses of an as-yet-unknown Expr type. But we want to compose them, of course, so now we define the coproduct of types. In Haskell, we write:

data (f :+: g) e = (f e) :+: (g e)

In Scala, I call this Sum because it's shorter than Coproduct, although I realize it's easy to confuse it with Add.

sealed trait Sum[F[X], G[X], E]
case class Inl[F[X], G[X], E](l: F[E]) extends Sum[F,G,E]
case class Inr[F[X], G[X], E](r: G[E]) extends Sum[F,G,E]

Each of these is a functor, and we want to take advantage of this. So we'll need a simple functor trait. We encode type classes as traits, and instances as implicit instances:

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

And now we define the two obvious instances:

implicit object ValFunctor extends Functor[Val] {
  def map[A,B](f: A => B, v: Val[A]): Val[B] =
    Val(v.i)
}
implicit object AddFunctor extends Functor[Add] {
  def map[A,B](f: A => B, v: Add[A]): Add[B] =
    Add(f(v.left), f(v.right))
}

Now here's where things become severely unsatisfactory. In Haskell, we write:

instance (Functor f, Functor g) => Functor (f :+: g) where
  ...

But in Scala, Sum is not curried, and there's no easy way to partially apply it. So it's much more difficult. We need to use the following type-level combinator, and project out the type It (of the desired kind * -> *):

trait Apply2Of3[F[A[_],B[_],_],A[_],B[_]] {
  type It[C] = F[A,B,C]
}

Note that this is a highly specialized combinator: the kinds of all arguments are fully known and annotated. This is unfortunate.

(Aside: in Haskell, we can just write

type Apply2 f a b = f a b

which is much more general. However, we can't seem to use this at multiple kinds in the same module. I don't know the name of this limitation in Haskell. If anyone knows, please enlighten me!)

Anyway, using Apply2Of3, we can show that coproducts are functors:

implicit def sumFunctor[F[_],G[_]](implicit ff: Functor[F],
    gf: Functor[G]) =
  new Functor[Apply2Of3[Sum,F,G]#It] {
    type Tmp[X] = Apply2Of3[Sum,F,G]#It[X]
    def map[A,B](f: A => B, v: Tmp[A]): Tmp[B] = v match {
      case Inl(l) => Inl[F,G,B](ff.map(f, l))
      case Inr(r) => Inr[F,G,B](gf.map(f, r))
    }
  }

We can fold over the fixed points of functors. By now, the type annotations are becoming pretty cumbersome:

def foldExpr[F[X],A](f: F[A] => A, expr: Expr[F])
    (implicit functor: Functor[F]): A =
  f(functor.map[Expr[F],A](foldExpr[F,A](f, _), expr.e))

Evaluation is an algebra on a functor F. However, I don't actually require the Functor instance here, because it simplifies the translation. These are very similar to the above Functor definitions:

trait Eval[F[X]] {
  def eval(f: F[Int]): Int
}

implicit object ValEval extends Eval[Val] {
  def eval(v: Val[Int]): Int = v.i
}
implicit object AddEval extends Eval[Add] {
  def eval(v: Add[Int]): Int = v.left + v.right
}

implicit def sumEval[F[_],G[_]](implicit fe: Eval[F],
    ge: Eval[G]) =
  new Eval[Apply2Of3[Sum,F,G]#It] {
    type Tmp[X] = Apply2Of3[Sum,F,G]#It[X]
    def eval(v: Tmp[Int]): Int = v match {
      case Inl(l) => fe.eval(l)
      case Inr(r) => ge.eval(r)
    }
  }

With these definitions in hand, we can evaluate expressions:

def eval[F[_]](e: Expr[F])(implicit fe: Eval[F],
    ff: Functor[F]) =
  foldExpr[F,Int](fe.eval(_), e)

Of course we want to test it. Here, things are horribly ugly. It's possible to make things a bit better with a temporary type alias, but even so, it's very unpleasant:

type Tmp[X] = Apply2Of3[Sum,Val,Add]#It[X]
val addExample: Expr[Tmp] =
  Expr[Tmp](
    Inr[Val,Add,Expr[Tmp]](
      Add(
        Expr[Tmp](Inl[Val,Add,Expr[Tmp]](Val(118))),
        Expr[Tmp](Inl[Val,Add,Expr[Tmp]](Val(1219))))))

And unfortunately, Scala cannot figure out how to automatically apply the implicit conversions necessary to produce the following instances, so we need to write them down by hand. (I might add that the error messages are particularly incomprehensible if we try to have these inferred.)

implicit val ev = sumEval[Val,Add](ValEval, AddEval)
implicit val fc = sumFunctor[Val,Add](ValFunctor, AddFunctor)

Finally:

def test = println("eval addExample: " +
  eval[Tmp](addExample))

That brings us through the end of section 3 of the paper. Wonderful! I take a few things from this little exercise:

• Fully curried definitions is the right default! This is not news, but over time, I've become more and more convinced of this.
• No matter the default, we need to be able to define types with kinds like * -> * -> *, rather than just (*,*) -> *.
• We would really like to be able to write kind-polymorphic types (like Apply2Of3, but as liberal as possible in the kinds of its arguments).
• Scala's inability to infer types with kinds other than * is a pretty big problem.
• Scala needs to be better at inferring implicit conversions and parameters.
• Haskell syntax is amazingly sweet and elegant. This is also not news.
• All told, it is possible to express these ideas in Scala.
• I need to get some code highlighting going on this blog.

UPDATE: Continued in part 2.