Higher-Rank Polymorphism in Scala

I was reading Tim Carstens’s post about Haskell features he’d like to see in other languages, and one of those features was rank-2 types. Tim says that the killer application for this to ensure the safety of resource access, in the type system. In short, this feature enables us to make sure that if we have a value of a particular type, then it represents a system resource which can be safely accessed, and that it’s a compile-time type error to access a closed or unopened resource. I find it really fascinating that we can get this kind of assurance from a type system.

First, a brief explanation of rank-2 polymorphism. A regular (rank-1) polymorphic function in Scala might look like this:

```def apply[A](f: A => A, a: A): A = f(a)
```

This will apply the given function to a given value of any particular type, and it’s ensured that the argument and return types of the function are the same as the value to which it is applied. There’s only one type involved here, but it can be any particular type. But what if we wanted to say that the function `f` should work for all types? For example, a function that puts its argument in a list. Such a function should work for all types, as long as the input and output type match. For example:

def singletonList[A](a: A): List[A] = List(a)

Now say we want to take such a function as an argument to another function. With just rank-1 polymorphism, we can’t do this:

```def apply[A,B](f: A => List[A], b: B, s: String): (List[B], List[String]) =
(f(b), f(s))
```

It’s a type error because, `B` and `String` are not `A`. That is, the type `A` is fixed on the right of the quantifier `[A,B]`. We really want the polymorphism of the argument to be maintained so we can apply it polymorphically in the body of our function. Here’s how that might be expressed if Scala had rank-n types:

```def apply[B](f: (A => List[A]) forAll { A }, b: B, s: String): (List[B], List[String]) =
(f(b), f(s))
```

That’s not legal Scala code, so let’s see how we could work around this. Note that a method can be polymorphic in its arguments, but a value of type Function1, Function2, etc, is monomorphic. So what we do is represent a rank-2 polymorphic function with a new trait that accepts a type argument in its `apply` method:

```trait ~>[F[_],G[_]] {
def apply[A](a: F[A]): G[A]
}
```

This trait captures something more general than `Function1`, namely a natural transformation from functor `F` to functor `G`. Note that `A` appears nowhere in the type and isn’t given until the apply method is actually called. We can now model a function that takes a value and puts it in a list, as a natural transformation from the identity functor to the List functor:

```type Id[A] = A

val singletonList = new (Id ~> List) {
def apply[A](a: A): List[A] = List(a)
}
```

And we can now take such a function as an argument:

```def apply[B](f: Id ~> List, b: B, s: String): (List[B], List[String]) =
(f(b), f(s))
```

I wonder if we can use this to get static guarantees of safe resource access, as in the SIO monad detailed in Lightweight Monadic Regions.

12 thoughts on “Higher-Rank Polymorphism in Scala”

1. cheatex says:

I’ve tried this code in scala 2.7.6 and got next error:

error: type mismatch;
found : List[Any]
required: List[B]
(f(b), f(s))

• Rúnar says:

It works with 2.8.0.RC6. You might need more type annotation for an earlier version of Scala.

2. This is a very cool example! Precisely the type of thing I was hoping to see.

3. Matt R says:

We really want the polymorphism of the argument to be maintained so we can apply it polymorphically in the body of our function.

Being devil’s advocate for a moment, you could achieve a similar effect arguably more straightforwardly:

``` trait Listifier {```

``` def apply[A](a: A): List[A] } val singletonList = new Listifier { def apply[A](a: A) = List(a) } def apply[B](f: Listifier, b: B, s: String): (List[B], List[String]) = (f(b), f(s)) ```

What are the benefits of using the “~>” trait over this approach?

• Rúnar says:

Your “listifier” is natural transformation specialized to the identity and List functors. More specific (less general), but in no way more straightforward.

What are the benefits of Function1 over this trait?

trait Intifier {
def apply[A](a: A): Int
}

And what are the benefits of Listifier over this trait?

trait IntListifier {
def apply(a: Int): List[Int]
}