Talk:Haskell/Polymorphism

From Wikibooks, the open-content textbooks collection

[edit] Parked Text

[edit] Higher Rank types

Our example foo is said to have a rank-2 type. There are other ranks as well. Counting begins with ordinary polymorphic functions like

 id  :: forall a. a -> a
 map :: forall a. [a] -> [a]

which are said to have rank-1 types. Functions with rank-1 types as arguments have rank-2 types. Examples include

 f2  :: (forall a. a -> a -> a) -> Int -> Int
 g2  :: (forall a. Eq a => [a] -> a -> Bool) -> Int -> Int

A function like

 f3  :: ((forall a. a -> a -> a) -> Int) -> Bool -> Bool

with a rank-2 type on the left of the function arrow is said to have a rank-3 type and so on.

What rank does

 const :: forall a. a -> (forall b. b -> a)

have? It's the same as

 const :: forall a. forall b. a -> b -> a

and therefor a rank-1 type. In other words, a forall can be moved to the front when it's on the right of a function arrow, i.e. in the result position. Only quantifiers on the left of a function arrow, that is in the argument position, increase the rank and cannot be moved to the front.