Functional Programming – Is Higher-Rank Parametric Polymorphism Useful?

functional programminggenericsprogramming-languagestype-systems

I'm pretty sure everyone is familiar with generic methods of the form:

T DoSomething<T>(T item)

This function is also called parametrically polymorphic (PP), specifically rank-1 PP.

Let's say this method can be represented using a function object of the form:

<T> : T -> T

That is, <T> means it takes one type parameter, and T -> T means that it takes one parameter of type T and returns a value of the same type.

Then the following would be a rank-2 PP function:

(<T> : T -> T) -> int

The function takes no type parameters itself, but takes a function which takes a type parameter. You can continue this iteratively, making the nesting deeper and deeper, getting PP of higher and higher rank.

This feature is really rare among programming languages. Even Haskell doesn't allow it by default.

Is it useful? Can it describe behaviors that are difficult to describe otherwise?

Also, what does it mean for something to be impredicative? (in this context)

Best Answer

In general, you use higher-rank polymorphism when you want the callee to be able to select the value of a type parameter, rather than the caller. For example:

f :: (forall a. Show a => a -> Int) -> (Int, Int)
f g = (g "one", g 2)

Any function g that I pass to this f must be able to give me an Int from a value of some type, where the only thing g knows about that type is that it has an instance of Show. So these are kosher:

f (length . show)
f (const 42)

But these are not:

f length
f succ

One particularly useful application is in using the scoping of types to enforce the scoping of values. Suppose we have an object of type Action<T>, representing an action we can run to produce a result of type T, such as a future or callback.

T runAction<T>(Action<T>)

runAction :: forall a. Action a -> a

Now, suppose that we also have an Action that can allocate Resource<T> objects:

Action<Resource<T>> newResource<T>(T)

newResource :: forall a. a -> Action (Resource a)

We want to enforce that those resources are only used inside the Action where they were created, and not shared between different actions or different runs of the same action, so that actions are deterministic and repeatable.

We can use higher-ranked types to accomplish this by adding a parameter S to the Resource and Action types, which is totally abstract—it represents the “scope” of the Action. Now our signatures are:

T run<T>(<S> Action<S, T>)
Action<S, Resource<S, T>> newResource<T>(T)

runAction :: forall a. (forall s. Action s a) -> a
newResource :: forall s a. a -> Action s (Resource s a)

Now when we give runAction an Action<S, T>, we are assured that because the “scope” parameter S is fully polymorphic, it cannot escape the body of runAction—so any value of a type that uses S such as Resource<S, int> likewise cannot escape!

(In Haskell, this is known as the ST monad, where runAction is called runST, Resource is called STRef, and newResource is called newSTRef.)

Related Solutions

Is return-type-(only)-polymorphism in Haskell a good thing

I actually think that return type polymorphism is one of the best features of type classes. After having used it for a while, it is sometimes hard for me to go back to OOP style modeling where I don't have it.

Consider the encoding of algebra. In Haskell we have a type class Monoid (ignoring mconcat)

class Monoid a where
   mempty :: a
   mappend :: a -> a -> a

How could we encode this as an interface in an OO language? The short answer is we can't. That's because the type of mempty is (Monoid a) => a aka, return type polymorphism. Having the ability to model algebra is incredibly useful IMO.*

You start your post with the complaint about "Referential Transparency." This raises an important point: Haskell is a value oriented language. So expressions like read 3 don't have to be understood as things that compute values, they can also be understood as values. What this means is that the real issue is not return type polymorphism: it is values with polymorphic type ([] and Nothing). If the language should have these, then it really has to have polymorphic return types for consistency.

Should we be able to say [] is of type forall a. [a]? I think so. These features are very useful, and they make the language much simpler.

If Haskell had subtype polymorphism [] could be a subtype for all [a]. The problem is, that I don't know of a way of encoding that without having the type of the empty list be polymorphic. Consider how it would be done in Scala (it is shorter than doing it in the canonical statically typed OOP language, Java)

abstract class List[A]
case class Nil[A] extends List[A]
case class Cons[A](h: A. t: List[A]) extends List[A]

Even here, Nil() is an object of type Nil[A] **

Another advantage of return type polymorphism is that it makes the Curry-Howard embedding much simpler.

Consider the following logical theorems:

 t1 = forall P. forall Q. P -> P or Q
 t2 = forall P. forall Q. P -> Q or P

We can trivially capture these as theorems in Haskell:

data Either a b = Left a | Right b
t1 :: a -> Either a b
t1 = Left
t2 :: a -> Either b a
t2 = Right

To sum up: I like return type polymorphism, and only think it breaks referential transparency if you have a limited notion of values (although this is less compelling in the ad hoc type class case). On the other hand, I do find your points about MR and type defaulting compelling.

*. In the comments ysdx points out this isn't strictly true: we could re-implement type classes by modeling the algebra as another type. Like the java:

abstract class Monoid<M>{
   abstract M empty();
   abstract M append(M m1, M m2);
}

You then have to pass objects of this type around with you. Scala has a notion of implicit parameters which avoids some, but in my experience not all, of the overhead of explicitly managing these things. Putting your utility methods (factory methods, binary methods, etc) on a separate F-bounded type turns out to be an incredibly nice way of managing things in an OO language that has support for generics. That said, I'm not sure I would have groked this pattern if I didn't have experience modeling things with typeclasses, and I'm not sure other people will.

It also has limitations, out of the box there is no way to get an object that implements the typeclass for an arbitrary type. You have to either pass the values explicitly, use something like Scala's implicits, or use some form of dependency injection technology. Life gets ugly. On the other hand, it is nice that you can have multiple implementations for the same type. Something can be a Monoid in multiple ways. Also, carrying around these structures separately has IMO a more mathematically modern, constructive, feel to it. So, although I still generally prefer the Haskell way of doing this, I probably overstated my case.

Typeclasses with return type polymorphism makes this kind of thing easy to handle. That doesn't meen it is the best way to do it.

**. Jörg W Mittag points out this isn't really the canonical way of doing this in Scala. Instead, we would follow the standard library with something more like:

abstract class List[+A] ...  
case class Cons[A](head: A, tail: List[A]) extends List[A] ...
case object Nil extends List[Nothing] ...

This takes advantage of Scala's support for bottom types, as well as covariant type paramaters. So, Nil is of type Nil not Nil[A]. At this point we are pretty far from Haskell, but it is interesting to note how Haskell represents the bottom type

undefined :: forall a. a

That is, it isn't the subtype of all types, it is polymorphically(sp) a member of all types.
Yet more return type polymorphism.

Does groovy call partial application ‘currying’

Groovy's implementation of curry does not actually curry at any point, even behind the scenes. It is essentially identical to partial application.

The curry, rcurry and ncurry methods return a CurriedClosure object that holds the bound arguments. It also has a method getUncurriedArguments (misnamed—you curry functions, not arguments) which returns the composition of the arguments passed to it with the bound arguments.

When a closure gets called, it ultimately calls the invokeMethod method of MetaClassImpl, which explicitly checks to see if the calling object is an instance of CurriedClosure. If so, it uses the aforementioned getUncurriedArguments to compose the full array of arguments to apply:

if (objectClass == CurriedClosure.class) {
    // ...
    final Object[] curriedArguments = cc.getUncurriedArguments(arguments);
    // [Ed: Yes, you read that right, curried = uncurried. :) ]
    // ...
    return ownerMetaClass.invokeMethod(owner, methodName, curriedArguments);
}

Based on the confusing and somewhat inconsistent nomenclature above, I suspect that whoever wrote this has a good conceptual understanding, but was perhaps a little rushed and—like many smart people—conflated currying with partial application. This is understandable (see Paul King's answer), if a little unfortunate; it will be difficult to correct this without breaking backwards compatibility.

One solution I've suggested is to overload the curry method such that when no arguments are passed it does real currying, and deprecate calling the method with arguments in favour of a new partial function. This might seem a little strange, but it would maximise backwards compatibility—since there's no reason to use partial application with zero arguments—while avoiding the (IMHO) uglier situation of having a new, differently-named function for proper currying while the function actually named curry does something different and confusingly similar.

It goes without saying that the result of calling curry is completely different from actual currying. If it really curried the function, you would be able to write:

def add = { x, y -> x + y }
def addCurried = add.curry()   // should work like { x -> { y -> x + y } }
def add1 = addCurried(1)       // should work like { y -> 1 + y }
assert add1(1) == 2

…and it would work, because addCurried should work like { x -> { y -> x + y } }. Instead it throws a runtime exception and you die a little inside.

Best Answer

Related Solutions

Is return-type-(only)-polymorphism in Haskell a good thing

Does groovy call partial application ‘currying’

Related Topic