Overloading in Haskell

:t (*) (*) :: Num a => a -> a -> a square x = x * x
:t square square :: Num a => a -> a
The new function "inherits" the overloading of the operator…
The ‹square› function will work on any type in the �
```
Num�
```
class, even types that haven't been defined yet!
As a more illustrative example, consider
- ```
sort :: Ord a => [a] -> [a]
```
that "inherts" the overloading of the ‹<=› operator…>

Type classes and instances

A type class declares a set of methods, i.e. a set of related overloaded functions and operators.

Here is the definition of the predefined �

Num�

class:

class Num a where
   (+), (*), (-) :: a -> a -> a
   negate, abs, signum :: a -> a
   fromInteger :: Integer -> a

An instance declaration provides implementations of methods for a specific type:

instance Num Int     where -- ...
instance Num Integer where -- ...
instance Num Double  where -- ...
instance Num Float   where -- ...

Note: in spite of the similar terminology, type classes in Haskell are for overloading, not for objects, like in object oriented languages.

The Eq class

class Eq a where
  (==), (/=) :: a -> a -> Bool
  
  a/=b = not (a==b) -- default implementation
  a==b = not (a/=b) -- default implementation

instance Eq Int    where -- ...
instance Eq Double where -- ...
instance Eq Char   where -- ...
-- There are instances for almost all predefined types

Quiz: which types do not support equality tests?

Defining your own instances

Example of how to define an instance of class �
```
Eq�
```
‹(==)› ‹Red› ‹Yellow› ‹Green›
‹Red› ‹True› ‹False› ‹False›
‹Yellow› ‹False› ‹True› ‹False›
‹Green› ‹False› ‹False› ‹True›

‹(==)›	‹Red›	‹Yellow›	‹Green›
‹Red›	‹True›	‹False›	‹False›
‹Yellow›	‹False›	‹True›	‹False›
‹Green›	‹False›	‹False›	‹True›

data TrafficLight = Red | Yellow | Green

instance Eq TrafficLight where
  Red    == Red    = True
  Yellow == Yellow = True
  Green  == Green  = True
  _      == _      = False

(the above instance is what you get when you use deriving Eq)

Equality instance for pairs

instance (Eq a,Eq b) => Eq (a,b) where
  (x1,y1) == (x2,y2) = x1==x2 && y1==y2

Pairs can be tested for equality if both parts can be tested for equality.
- Similarly for larger tuples.
- Note: this definition is not recursive.

Equality instance for lists

instance Eq a => Eq [a] where
  []   == []   = True
  x:xs == y:ys = x==y && xs==ys
  _    == _    = False

List can be tested for equality if the elements can be tested for equality
Note: this definition is recursive.

Infinitely many instances

Take another look at these instance declarations

instance (Eq a,Eq b) => Eq (a,b) where -- ...
instance Eq a => Eq [a] where -- ...

They are rules that can be applied repeatedly, to generate instances for arbitrarily complex types.
- Base cases: �
```
Eq Int�
```
  , �
```
Eq Bool�
```
  , �
```
Eq Char�
```
  , …
- Applying the rules:
  - �
    Eq String�
    , �
    Eq [Int]�
    , �
    Eq [[Int]]�
    , �
    Eq [[[Int]]]�
    , …
  - �
    Eq (Int,Bool)�
    , �
    Eq [(Int,Bool)]�
    , �
    Eq ([Int],[Bool])�
    , …
  - �
    �
    …
- Type classes can be seen as a simple automatic programming system: the programmer picks the type, the instances generate the code.

The Ord class

class Eq a => Ord a where
  (<), (<=), (>), (>=) :: a -> a -> Bool
  compare              :: a -> a -> Ordering
  max, min             :: a -> a -> a

data Ordering = LT | EQ | GT

There are instances for almost all predefined types.
�
```
Ord�
```
is a subclass of �
```
Eq�
```
.
- All types that are in the �
```
Ord�
```
  class are also in the �
```
Eq�
```
  class.
- It is expected that when ‹x==y› returns ‹True›, then ‹compare x y› returns ‹EQ›.

The Enum class

class Enum a where
  pred, succ     :: a -> a
  toEnum         :: Int -> a
  fromEnum       :: a -> Int
  enumFrom       :: a -> [a]
  enumFromTo     :: a -> a -> [a]
  -- ...

It's enough to define ‹fromEnum› and ‹toEnum›, the other methods have default implementations.

Instances: �

Bool�

, �

Int�

, �

Integer�

, �

Float�

, �

Double�

, …

The enumeration syntax

Enumerations can be used for any type in the �

Enum�

class, e.g.:

‹[1..5] == [1,2,3,4,5]›
‹[1..] == [1,2,3,4,5,…]›
‹['a'..'g'] == "abcdefg"›
‹[0.5 .. 3] == [0.5,1.5,2.5,3.5]› -- watch out for rounding errors…
This is syntactic sugar for the methods of the �
```
Enum�
```
class:
- ‹[x..y] == enumFromTo x y›
- ‹[x..] == enumFrom x›

The Bounded class

class Bounded a where
  minBound, maxBound :: a

Instances: �
```
Bool�
```
, �
```
Char�
```
, �
```
Int�
```
, tuples
Not bounded: �
```
Integer�
```
Example:

enumAll :: (Bounded a, Enum a) => [a]
enumAll = [minBound .. maxBound]

The Show and Read classes

class Show a where
  show :: a -> String
  -- some more functions...

class Read a where
  read :: String -> a
  -- some more functions...

There are instances for almost all predefined types.
Note that for ‹read›, which instance is used depends not on the type of the argument, but on how the result is used.
- Overloading is resolved by the type checker.

Derived instances

For many predefined classes, in particular �
```
Eq�
```
, �
```
Ord�
```
, �
```
Show�
```
, �
```
Read�
```
, �
```
Enum�
```
and �
```
Bounded�
```
, there is a standard way to define instances.
The Haskell compiler knows how to define these instances.

So, when you define a new data type, you can get instances for free!

data Suit = Spades | Hearts | Diamonds | Clubs
            deriving (Eq,Ord,Show,Read,Enum,Bounded)

Defining your own Show instance 1

data Suit = Spades | Hearts | Diamonds | Clubs
            deriving (Eq,Ord,Enum,Bounded)

instance Show Suit where
  show Spades   = "♠"
  show Hearts   = "♥"
  show Diamonds = "♦"
  show Clubs    = "♣"

Defining your own Show instance 2

data Rank = Numeric Int | Jack | Queen | King | Ace
            deriving (Eq,Ord)

instance Show Rank where
  show (Numeric n) = show n
  show Jack        = "J"
  show Queen       = "Q"
  show King        = "K"
  show Ace         = "A"

Defining your own Show instance 3

data Card = Card {rank::Rank, suit::Suit}

instance Show Card where
  show (Card r s) = show r++show s

Quiz: is this a recursive definition?

Defining your own Show instance 4

data Hand = Empty | Add Card Hand

instance Show Hand where
  show Empty = "."
  show (Add c h) = show c ++" "++show h

Quiz: is this a recursive definition?

Before and after

With deriving Show:
- example_hand_2 Add (Card {rank = Ace, suit = Spades}) (Add (Card {rank = King, suit = Clubs}) Empty)
With the hand-written �
```
Show�
```
instances:
- example_hand_2 A♠ K♣

More type classes 1

class Functor f where
  fmap :: (a->b) -> f a -> f b

f <$> d = fmap f d

A generalisation of �

map�

to other types with one parameter.

map  ::              (a->b) -> [a] -> [b]
fmap :: Functor f => (a->b) -> f a -> f b

Instances: �
```
[]�
```
, �
```
Maybe�
```
, �
```
IO�
```
, …
deriving Functor is supported as an extension in GHC.
- Put {-# LANGUAGE DeriveFunctor #-} in the beginning of your module to enable this extension.

More type classes 2

class Foldable t where
  foldr :: (a->b->b) -> b -> t a -> b
  -- ...

A generalisation of �
```
foldr�
```
from lists to other types with one parameter.
Instances: �
```
[]�
```
, �
```
Maybe�
```
, …
This class is included in the Prelude in recent versions of GHC, but not in the official Haskell language definition.
deriving Foldable is supported as an extension in GHC.
- Put {-# LANGUAGE DeriveFoldable #-} in the beginning of your module to enable this extension

Defining your own class 1

A class to enumerate all the values of "small" types.
- ```
class Small a where
  values :: [a]
```

Some instances:

instance Small Bool where
  values = [False,True]

instance Small Suit where
  values = [maxBound .. minBound]

instance Small Rank where
  values = (...)

instance Small Card where
  values = [Card r s | s<-values, r<-values]

SmallCheck

Testing if a property holds for all values

smallCheck :: Small a => (a->Bool) -> Bool
smallCheck p = and [p x | x<-values]

Exhaustive testing!
- Better than random testing!
- Unfortunately it's only practical when the argument types are sufficiently small…
As defined above, ‹smallCheck› can only test properties with one argument. What if we want it to work for an arbitrary number of arguments, like ‹quickCheck›?

Defining your own class 2

Exhaustive Testing

class SmallCheck prop where
  smallCheck :: prop -> Bool

instance SmallCheck Bool where
  smallCheck b = b

instance (Small a,SmallCheck prop) => SmallCheck (a->prop) where
  smallCheck f = and [smallCheck (f x)|x<-values]

Ambiguity

Consider

f :: String -> String
f s = show (read s)

Will this work? Compare with

square :: Num a => a -> a
square x = x * x

Numeric literals, monomorphism and defaulting

Definitions without arguments and without type signatures are not allowed to be overloaded. This is called the monomorphism restriction.
- ```
answer = 6*7
```
Numeric literals are overloaded, so you would expect ‹answer :: Num a => a›, but one specific type will be chosen depending on how you use ‹answer›.
If nothing else determines which type answer should have, defaulting rules specific for the �
```
Num�
```
class kick in, and you get ‹answer :: Integer›.
For code entered directly GHCi, the monomorphism restriction is not used, and there are extended defaulting rules to avoid ambiguities.

A few notes on type classes

Haskell has a lot in common with preceding functional languages, notably Miranda, Standard ML and Lazy ML.
Type classes was the main novel feature in Haskell.
Type classes were primarily intended as an improvement over how Standard ML handled equality and numeric operators.
Then type classes got extended (with constructor classes, multi-parameter classes, functional depdendencies, …) and are now used for a lot more things than anyone anticipated.
But David Turner (creator of Miranda) thinks type classes were a mistake :-)

Overloading in Standard ML

Standard ML has one built-in type class for equality
- ```
(==) :: ''a -> ''a -> Bool
```

Predefined numeric operators are overloaded,

(*) :: Int -> Int -> Int
(*) :: Double -> Double -> Double

but user-defined numeric functions have to choose one specific type.

Overloading and type classes in Haskell

How to make ad-hoc polymorphism less ad hoc ^(*)

Overloading

Overloading in Haskell

Type classes and instances

The Eq class

Defining your own instances

Equality instance for pairs

Equality instance for lists

Infinitely many instances

The Ord class

The Enum class

The enumeration syntax

Enumerations can be used for any type in the �
Enum�
class, e.g.:

The Bounded class

The Show and Read classes

Derived instances

Defining your own Show instance 1

Defining your own Show instance 2

Defining your own Show instance 3

Defining your own Show instance 4

Before and after

More type classes 1

More type classes 2

Defining your own class 1

SmallCheck

Defining your own class 2

Exhaustive Testing

Ambiguity

Numeric literals, monomorphism and defaulting

A few notes on type classes

Overloading in Standard ML

Type classes in Haskell vs OO languages

Overloading and type classes in Haskell

How to make ad-hoc polymorphism less ad hoc (*)

Overloading

Overloading in Haskell

Type classes and instances

The Eq class

Defining your own instances

Equality instance for pairs

Equality instance for lists

Infinitely many instances

The Ord class

The Enum class

The enumeration syntax

Enumerations can be used for any type in the �Enum�class, e.g.:

The Bounded class

The Show and Read classes

Derived instances

Defining your own Show instance 1

Defining your own Show instance 2

Defining your own Show instance 3

Defining your own Show instance 4

Before and after

More type classes 1

More type classes 2

Defining your own class 1

SmallCheck

Defining your own class 2

Exhaustive Testing

Ambiguity

Numeric literals, monomorphism and defaulting

A few notes on type classes

Overloading in Standard ML

Type classes in Haskell vs OO languages

How to make ad-hoc polymorphism less ad hoc ^(*)

Enumerations can be used for any type in the �
Enum�
class, e.g.: