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.

About these ads

12 thoughts on “Higher-Rank Polymorphism in Scala

  1. 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))

  2. 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?

    • 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]
      }

      Same answer.

  3. Pingback: Type-Level Programming in Scala, Part 7: Natural transformation literals « Apocalisp

  4. Pingback: Towards an Effect System in Scala, Part 1 « Apocalisp

  5. Hello.

    Can you suggest where the following syntax (you use it for ~> trait) is defined?

    class Test[A, B]
    val t = new (Int Test String)

  6. Pingback: First-class polymorphic function values in shapeless (2 of 3) — Natural Transformations in Scala | Chuusai

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s