Polymorphism within higher-order functions?

Question

I have an algebraic data type with some constructors that hold comparable values, and some constructors that don't. I wrote some comparison functions that work like the standard (==) and (/=) operators, but return Nothing for comparisons that don't make sense:

data Variant = IntValue Int
             | FloatValue Float
             | NoValue

equal :: Variant -> Variant -> Maybe Bool
equal (IntValue a) (IntValue b) = Just (a == b)
equal (FloatValue a) (FloatValue b) = Just (a == b)
equal _ _ = Nothing

unequal :: Variant -> Variant -> Maybe Bool
unequal (IntValue a) (IntValue b) = Just (a /= b)
unequal (FloatValue a) (FloatValue b) = Just (a /= b)
unequal _ _ = Nothing

That works, but the repetition is unwieldy — especially since I actually have more Variant constructors and more comparison functions.

I thought I could factor out the repetition into a helper function that's parameterized on the comparison function:

helper :: (Eq a) => (a -> a -> Bool) -> Variant -> Variant -> Maybe Bool
helper f (IntValue a) (IntValue b) = Just (f a b)
helper f (FloatValue a) (FloatValue b) = Just (f a b)
helper _ _ _ = Nothing

equal' :: Variant -> Variant -> Maybe Bool
equal' = helper (==)

unequal' :: Variant -> Variant -> Maybe Bool
unequal' = helper (/=)

but that doesn't work because the type variable a apparently can't bind to both Int and Float at the same time in the definition of helper; GHC binds it to Float and then complains about a type mismatch on the line that handles IntValue.

A function like (==) is polymorphic when used directly; is there a way to pass it to another function and have it remain polymorphic?

C. A. McCann C. A. McCann · Accepted Answer · 2011-08-15T04:02:50

Yes, this is possible, but only with language extensions:

{-# LANGUAGE Rank2Types #-}

helper :: (forall a. (Eq a) => (a -> a -> Bool))
       -> Variant -> Variant -> Maybe Bool
helper f (IntValue a) (IntValue b) = Just (f a b)
helper f (FloatValue a) (FloatValue b) = Just (f a b)
helper _ _ _ = Nothing

The forall a. does about what it sounds like; the a is universally quantified within the parentheses, and out of scope outside them. This means that the f argument is required to be polymorphic over all types a that are instances of Eq, which is exactly what you want.

The extension here is called "rank 2" because it allows the regular style of polymorphism at the outermost scope, plus polymorphic arguments as in the example here. To nest things further, you need the extension RankNTypes, which is fairly self-descriptive.

As an aside, regarding higher-rank polymorphic types--keep in mind that the forall is what actually binds the variable to a type; you can think of them as behaving a lot like a lambda, in fact. When you apply such a function to something with a concrete type, the type of the argument is implicitly bound by the forall for that use. This comes up, for instance, if you try to use a value whose type was bound by an inner forall outside that function; the value's type has gone out of scope, which makes it difficult to do anything sensible (as you can probably imagine).

Polymorphism within higher-order functions?

1 Answers