Rank N Types in Haskell

HigherRankedTypes.hs

{-# LANGUAGE RankNTypes #-}

module RankN where

-- Rank 0: 
-- add1 is momomorphic
add1 :: Int -> Int
add1 x = x + 1

-- Rank 1
-- id1 is polymorphic
id1 :: a -> a
id1 x = x

-- Rank 1
-- `foo` is Rank 1 polymorphic, f is monomorphic 
foo :: Num a => (a -> a) -> a
foo f = f 1
fooval = foo negate

-- Rank 2
-- someInt is Rank 2 polymorphic, f is Rank 1 polymorphic
someInt :: (forall a. a -> a) -> b -> b
someInt f x = f x

-- Rank 1 (explicit forall)
type IdFunc = forall a. a -> a

-- Rank 2
someInt1 :: IdFunc -> b -> b
someInt1 f x = f x

-- Rank 1
add ::Num a => a -> a -> a
add = (+)

-- Rank 2
myadd :: (forall a. Num a => a -> a -> a) -> String
myadd f = show (f 1 2)

-- Rank 0
myadd1 :: (Int -> Int -> Int) -> String
myadd1 f = show (f 1 2)


-- Rank 3
-- r3 is Rank 3 polymorphic, since f is Rank 2 polymorphic
r3 ::forall b. Show b => b -> ((forall a. Num a => a -> a -> a) -> String ) -> String
r3 x f =  show x ++ " " ++ f add ++ " " ++ f add

-- Example usage
myint  = someInt id 10
total  = myadd add
total1 = myadd1 add
total2 = r3 [1,2,3] myadd

HigherRankedTypes.md

Higher Ranked Types

Let's get started with a monomorphic function -

incr :: Int -> Int
incr = (+1)

The function incr works on values of type Int and nothing else. We can make our function polymorphic by using type parameters in place concrete types -

incr' :: Num a => a -> a
incr' = (+1)

The modified function incr' can work with any type that has a Num instance. Now let us move on and look at a simple higher order function -

foo :: (a -> a) -> a -> a
foo g x = g x

intval = foo (+1) 1       -- 2
listval = foo (++[]) [1]  -- [1]

The first argument to foo is a function of type a -> a. Is the function g polymorphic here? The answer is No! The a type is being used polymorphically here, however, a is bound to whatever is the type of x when g is applied to x i.e., g is monomorphic!

You don't believe me? Try this

bad-foo :: (Show a) => (a -> a) -> String
bad-foo g = (show (g 1000)) ++ (g "? what!")

Or this function -

bad-bar :: Show a => (a -> a) -> IO ()
bad-bar g = do
    print $ g 100
    print $ g "why?"

The compiler will not be happy with this code. If g were polymorphic, we could apply it to both numeric and string values!

Rank

We make our functions polymorphic by using type parameters instead of fixing the types. When the function is called, the parameters are bound to actual types. We say functions are instantiated with the given types). The actual types are the parameters that are passed while instantiating. This is called Rank-1 polymorphism. And since monomorphic functions have no parameters, they are considered Rank-0 types.

Coming back to bad-foo function, the type of the function says - it takes a value of type (a -> a) and gives a value of type String. The type for type variable a in (a -> a) is bound when the function is applied to a value (when we call g 1 in the function body). This means, for the reminder of this function body, g is monomorphic.

What we wanted, though, is for g to be polymorphic. We want the value for type (a -> a) to be bound when user calls bad-foo - not when g is used. Well, that is the description of a polymorphic function we saw above. That means we need to parameterise the parameters! This is called Rank 2 polymorphism. A rank-2 polymorphic function takes as an argument a rank-1 polymorphic function.

If a function takes as argument a rank (n-1) function, then it is said to be Rank-N polymorphic function.

RankNTypes GHC Extension

Haskell is based on the Hindley-Milner type system - and while it allows us to write polymorphic functions, it doesn't allow us to write functions which take polymorphic functions as arguments.

Higher Ranked Types are provided in GHC as a language extension. It can be enabled via the RankNTypes extension. Practically speaking, enabling higher-ranked types lets us introduce new variable scopes inside of type signatures. Here's the implementation we want:

{-# LANGUAGE RankNTypes #-}
good-foo :: (forall a. Show a => a -> a) -> String
good-foo g = (show (g 1)) ++ (g "what!")

In essence, Higher Ranked Types make polymorphic functions first class.

I think the function body of bad and good foo use “f” where as the function name is really “g”. So probably a typo.

Overall really great explanation!!!

Thanks :)