Instantly share code, notes, and snippets.

# vijayanant/HigherRankedTypes.hs

Last active August 12, 2024 11:33
Show Gist options
• Save vijayanant/9b75d1b276dc4e933eb314c804ddc312 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

# 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 ()
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 :)

### rebornwwp commented Aug 12, 2024

thanks. It helps me a lot!