Part 4: Parametric Polymorphism and Overloading

In this part of the course, we discuss the type system features that enable code reuse in more detail. We start with a discussion of parametric polymorphism, and continue looking more closely at overloading, and provide an overview of the most commonly used Haskell type classes.

Accompanying materials

4–1 Parametric Polymorphism

We discuss what it means for a type to be the “most general type”. We explain that Haskell erases type information at run-time and that this means that types that are represented by unconstrained type variables are really totally unknown at runtime.

We conduct a thought experiment as to how the step-by-step generalisation of a type signature drastically limits the amount of functions we can write, and therefore how polymorphism provides us with implementation guidance.

Self Test

  • Which of the following types is the most general?

    [a] -> [b] -> [(a,b)]
[a] -> [a] -> [(a,a)]

  • Which of the following types is the most general?

    a -> Int -> (a, Int)
Int -> a -> (Int, a)

  • Which of the following types is the most general?

    a -> [b]
a -> b
a

  • How many different total functions are there of type (Bool, Bool) -> (Bool, Bool)?

  • How many different total functions are there of type (Bool, a) -> (a, Bool)?

4–2 Parametricity: The map Function as an Example

We take a look at the type of map on lists and discuss what we can learn from the parametric polymorphism occurring in its type signature about the behaviour of the function.

Self Test

  • Without knowing anything about the implementation of the function, if we have a function f :: [a] -> Int and consider the calls f [1,2,3] and f "foo", what can we say about the results?
    1. Both will yield Ints, of course, but we do not know which numbers the calls return.
    2. Both will yield the same Int, but we do not know which one.
    3. Both calls will yield the number 3.
  • Without knowing anything about the implementation of the function, what can you say about a function with type a -> a -> Bool? How many different total functions of this type are there?

4–3 Union Types

We show how parametric polymorphism is not the answer if a function wants to have a choice between different types of values to return. We discuss how union types such as Either can be used instead, and how this approach is also often taken by Haskell libraries that are embedding dynamically typed languages into Haskell, such as the aeson packages does for JSON.

Self Test

  • What does the datatype

    data Listy a = Plain a | ListOf [Listy a]

    allow you to express?

  • In the eval task from Assignments B, try to modify the datatype of expressions as follows

    data Expr =
    Lit Int
  | Add Expr Expr
  | Neg Expr
  | And Expr Expr
  | Not Expr
  | Eq Expr Expr
  | If Expr Expr Expr

    and let us define

    data Value =
  IntVal Int | BoolVal Bool | Error

    Now redefine eval :: Expr -> Value such that And represents (&&), Not represents not, Eq represents (==). The If construct should now expect a Boolean condition, Add and Neg should expect integer arguments, whereas And and Not should expect Bool arguments. If any conditions are violated, return Error.

4–4 Overloading

We introduce type classes at the example of the Eq class and discuss how one can manually define instances of type classes. We also discuss default methods, MINIMAL pragmas, and the InstanceSigs extension.

Self Test

  • What is the result of Left 3 == Right 3? Is it True, False, or a type error?

  • Try to write down the correct type of map (==) including all class constraints. Only check in GHCi when you’re done.

  • Does the type [[[Int]]] admit an equality test with (==)? And what about the type Maybe (Int -> Int)?

  • If you ask for info in on the class Semigroup, you’ll see that it has methods called (<>) and sconcat and stimes. Additionally, there is a MINIMAL pragma saying

    {-# MINIMAL (<>) #-}

    What does this pragma mean?

    1. When defining an instance of the Semigroup class, we do not have to provide any definitions.
    2. When defining an instance of the Semigroup class, we have to provide a definition for sconcat and stimes, but we can omit (<>).
    3. When defining an instance of the Semigroup class, we have to provide a definition for (<>), but we can omit sconcat and stimes.

4–5 Type Class Overview: Eq, Ord, Enum, Bounded

We provide an overview of the most important type classes, starting with the Eq, Ord, Enum and Bounded classes. We also discuss the concept of superclasses in the context of the Ord class, and we mention the notion of defaulting in the context of the Bounded class.

Self Test

  • Check in GHCi whether the class Monoid has any superclasses.

  • What is the result of compare (Just (-1)) Nothing?

  • What is minBound :: (Bool, Bool)? Check your answer in GHCi.

  • What is [minBound ..] :: [(Bool, Bool)]? Check your answer in GHCi.

  • What is [minBound ..] :: [Ordering]? Check your answer in GHCi.

  • There is no real problem in defining class instances for functions, even though the classes we have been discussing so far have no such instances by default. Here is a possible equality instance for a subset of functions:

    instance (Bounded a, Enum a, Eq b) => Eq (a -> b) where
  f1 == f2 =
    all (\ x -> f1 x == f2 x) [minBound ..]

    With this definition, try what you get for

    (||) == (||)
(||) == (&&)
not . not == id
(+) == (+)

    Explain how this instance works.

4–6 Type Class Overview: Show, Read

We continue our tour of the Haskell type classes by looking at Show and Read. We also discuss the notion of ambiguous types and the differences in defaulting behaviour between GHCi and GHC.

Self Test

  • What is the result of readMaybe "0" :: Maybe Bool? (You have to import Text.Read first.)

  • What is the result of readMaybe "[(1, True), (2, False)]" :: Maybe [(Int, Bool)]?

  • Is the function

    f :: Int -> Int
f x = read (show x)

    the identity function? If not, try to find a counterexample. If yes, try to argue why.

  • In the cases that the function

    g :: String -> String
g x = show (read x :: Int)

    does not crash, does it then always produce the same string as the input? If not, try to find a counterexample. If yes, try to argue why?

4–7 Deriving Type Classes

We explain how instances for all the classes discussed so far can be automatically derived by GHC as long as the datatypes we try this on satisfy certain restrictions.

Self Test

  • Which of the type classes we discussed can be derived for the datatype

    data ChoiceOfThree a b c = One a | Two b | Three c

  • Does it make sense to derive Eq and Ord for the datatype

    data IntegerWithInfinity = MinusInfinity | PlusInfinity | Finite Integer

    If not, what would need to be changed?

  • Can Bounded be derived for IntegerWithInfinity? Can a sensible manual definition of Bounded be given for IntegerWithInfinity?

4–8 Type Class Overview: Functor, Foldable

We continue our overview of important type classes by discussing two classes that define interfaces on type constructors (parameterised datatypes), namely Functor and Foldable. The Functor class generalises the concept of types that have a map function, and the Foldable class is for types which contain elements in a clear order, meaning in particular that their elements can be extracted as a list.

Self Test

  • What is the result of length [[1,2,3], [4,5,6]]? What is the result of sum [[1,2,3], [4,5,6]]. What is the result of fmap (+1) [[1,2,3], [4,5,6]] and what of fmap length [[1,2,3], [4,5,6]]? Verify your answers in GHCi.

  • Does

    newtype Matrix a = Matrix [[a]]
  deriving (Show, Functor, Foldable)

    work if you enable the language extensions for deriving Functor and Foldable? If so, what is the result of length (Matrix [[1,2,3], [4,5,6]]) and of sum (Matrix [[1,2,3], [4,5,6]])? What is the result of fmap (+1) (Matrix [[1,2,3], [4,5,6]]) and of fmap length (Matrix [[1,2,3],[4,5,6]])? Verify your answers in GHCi.

  • What is the result of product (Left 3) and of product (Right 3)? What is the result of elem 1 (1,2) and of elem 2 (1,2)?

4–9 Optional: Classes for Numbers

We take a look at the different classes Haskell provides to deal with numbers and operations on numbers, most prominently the Num class. We also look at Integral and Fractional and a few others.

4–10 Optional: The Monomorphism Restriction and Defaulting

We discuss one of the darker and more confusing corners of Haskell. The monomorphism restriction causes that in some situations, Haskell deliberately refuses to infer the most general type of a declaration. Defaulting is a mechanism that Haskell uses to resolve otherwise ambiguous overloading in some circumstances. The defaulting rules that GHCi applies are somewhat different from the ones being used in normal Haskell source code.

4–11 Assignments D

It’s time for the next block of assignments. You can find them here.

You can save this file to a local directory and then open it in your editor and GHCi. The file then contains further instructions and several skeletons of functions that you are supposed to complete, as well as a few other questions.

Note that in this public version of the course, there is no way to submit the assignments.

Continue this course

Next: Part 5: IO and Explicit Effects.