Scala vs Skalleh

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.

Apply2

Submitted by Dan Doel on Sun, 05/10/2009 - 22:56.

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!

I haven't thought about it very hard, but my guess is that you're noticing that Haskell's kinds are (roughly) equivalent to the types of the simply typed lambda calculus. So when you say:

type Apply2 f a b = f a b

Apply2 has to be given some monomorphic kind. This can be any of


(* -> * -> *) -> * -> * -> *
(* -> * -> * -> *) -> * -> * -> * -> *
...

But indeed, it must just be one of them. If polymorphic kinds were available you could give it a type:

Forall k. (* -> * -> k) -> * -> * -> k

But as far as I know, UHC/EHC is the only Haskell compiler that's even experimented with that kind of thing, but I can't make it work with even a single use of Apply2, like:


data A a b c = A Int

type Apply2 f a b = f a b

foo :: Int -> Apply2 A a b c
foo i = A i

So testing out kind polymorphism is a no-go.

Dan, I haven't compiled your

Submitted by Max Bolingbroke on Mon, 05/11/2009 - 04:46.

Dan, I haven't compiled your code, but I think the problem is that you actually need to write:

data A (a :: * -> *) (b :: *) = A Int

type Apply2 f a b = f a b

foo :: Int -> Apply2 A a b
foo i = A i

The need to write explicit kind signatures is annoying, and basically arises because GHC defaults the kind of phantom type variables to *, rather than doing something moderately sane like introducing kind polymorphism.

Well, it's true that GHC

Submitted by Dan Doel on Mon, 05/11/2009 - 07:01.

Well, it's true that GHC doesn't accept that code either without kind signatures on f. It clearly infers the type as:


Apply2 :: (* -> * -> *) -> * -> * -> *

However, I wasn't talking about trying it in GHC, but in UHC, which is supposed to have some level of kind polymorphism. However, even when I add a signature:


-- actual uhc-allowed code
Apply2 :: (* -> * -> * -> *) -> * -> * -> * -> *
type Apply2 f a b = f a b

it just fails with "panic: Ty.FitsIn: no spine info".

However, fiddling around just now, I did notice that I can write:


Apply2 :: forall k. (* -> * -> k) -> * -> * -> k

and it merely fails with the same error, rather than spitting out syntax errors. So presumably that's the sort of type it's actually inferring/using (although it's probably polymorphic in the other kinds, too).

Playing more, I've come up with an example that does work; behold:


data A a = A Int

foo :: A Int
foo = A 1

bar :: A Maybe
bar = A 2

baz :: A A
baz = A 3

GHC will work with either foo, inferring A :: * -> *, or bar provided you specify the kind of its parameter, but not both. baz is impossible to reconcile with simple typing, because if you try to give A the kind K, then it needs to be kind K -> * to be applied to itself. However, uhc accepts all of them together without any help, due it its inferring polymorphic kinds, giving A :: forall k. k -> *. Quite luxurious.

Thanks, guys!

Submitted by matt on Tue, 05/12/2009 - 08:46.

Yes, I think this is the same limitation I had in mind. Sorry for the somewhat cryptic off-hand comment in the original post, I probably should have included an example. Here's an example more like what I originally had in mind, and no kind annotations are necessary:

type Apply2 f a b = f a b

data A a b c = A (a b c)
data B a b c = B (a b) (a c)

-- either of the following will work alone, but both together
-- will not compile (with GHC 6.10.1, at least).
type A2 = Apply2 A Either Int
type B2 = Apply2 B [] Int

Without thinking about it much, I think it's similar enough to your example, and I suspect that uhc would accept this code. If you have a chance to check, please let me know!

It doesn't seem to be a particularly severe limitation, since types like Apply2 are rather rarely needed in Haskell. But I found it a little surprising, all the same, that GHC wouldn't infer a polymorphic kind for it.

Anyway, thanks for your comments!

New example

Submitted by Dan Doel on Tue, 05/12/2009 - 12:39.

Yes, UHC does accept that code.

Awesome!

Submitted by matt on Tue, 05/12/2009 - 16:37.

That is indeed "luxurious!"