Contents

Top

Haskell Types Part 2

Type classes—function overloading

How Haskell overloads function names like ==, <=, + for various types, and how you can extend them to your own types, and how you can declare your own overloadable function names.

Two aspects:

A “type class” links the two aspects:

Using == and /= for example, the class is called “Eq” in the standard library:

The definition of Eq goes like: 

class Eq a where
    (==), (/=) :: a -> a -> Bool

    -- default implementation for (==)
    x == y = not (x /= y)

    -- default implementation for (/=)
    x /= y = not (x == y)

    -- default implementations deliberately circular so an instance just has to
    -- override one of them to break the cycle

“For a type a to be an instance, it must support those functions (of those types)”.

General syntax: 

class ClassName typeVar where
  methodName :: type sig containing typeVar
  ...

  -- Optional: default implementations

Bool is an instance, it goes like: 

instance Eq Bool where
    -- So a=Bool in this context, i.e.,
    -- (==), (/=) :: Bool -> Bool -> Bool
    False == False    = True
    True == True      = True
    _ == _            = False

    -- default implementation for (/=) takes hold

WARNING:

Method types outside classes look like this: 

(==) :: Eq a => a -> a -> Bool

The additional “Eq a =>” is marker for: polymorphic but user's choice of a must be an instance of Eq. This marker also appears when you write polymorphic functions using the methods, e.g., 

-- Determine whether the 3 arguments are mutually equal.  Needs the user-chosen
-- type to be an instance of Eq (supports "==") but otherwise polymorphic.
eq3 :: Eq a => a -> a -> a -> Bool
eq3 x y z = x==y && y==z
in HaskellTypes2.hs

Another example: The “Ord” class groups together <=, <, etc.: 

class Eq a => Ord a where
    compare :: a -> a -> Ordering    -- data Ordering = LT | EQ | GT
    (<), (<=), (>), (>=) :: a -> a -> Bool
    max, min :: a -> a -> a

    -- there are default implementations; an instance just has to provide
    -- compare or <=

This “Eq a =>” is a bit different. It means: An instance of Ord is also an instance of Eq. Best understood from two angles:

We say “Ord is a subclass of Eq”, but beware that this is unrelated to OOP subclasses. 

-- Sorting algorithms just need Ord but otherwise polymorphic.
insertionSort :: Ord a => [a] -> [a]
insertionSort [] = []
insertionSort (x:xt) = insert x (insertionSort xt)
  where
    insert e [] = [e]
    insert e xs@(x:xt)
        | e <= x = e : xs
        | otherwise = x : insert e xt

-- De-duplicating sorting uses both (==) and (<).  Type sig just needs Ord.
uniqInsertionSort :: Ord a => [a] -> [a]
uniqInsertionSort [] = []
uniqInsertionSort (x:xt) = insert x (uniqInsertionSort xt)
  where
    insert e [] = [e]
    insert e xs@(x:xt)
        | e < x = e : xs
        | e == x = xs
        | otherwise = x : insert e xt
in HaskellTypes2.hs

Recall we defined our own list types: 

data MyIntegerList = INil | ICons Integer MyIntegerList
    deriving Show
data MyList a = Nil | Cons a (MyList a)
    deriving Show
in HaskellTypes2.hs

Let's make them instances of Eq so we can use == on them too: 

instance Eq MyIntegerList where
    INil == INil              = True
    ICons x xs == ICons y ys  = x==y && xs==ys
    _ == _                    = False

instance Eq a => Eq (MyList a) where
-- The "Eq a =>" there means I need to use (==) on type a.
-- Try omitting it to see what happens.
    Nil == Nil              = True
    Cons x xs == Cons y ys  = x==y && xs==ys
                              -- "x==y" is when we need to assume Eq a.
    _ == _                  = False
in HaskellTypes2.hs

Check out these other type classes: Bounded, Enum (its methods are behind the [1..n] notation), Show, Read.

Reference: Haskell 2010 Section 6.3: Standard Haskell Classes

Often it is straightforward but boring to write instances for these classes, so the computer offers to auto-gen for you. Restrictions apply. You request it at the definition of your algebraic data type like this: 

data MyType = ... deriving (Eq, Ord, Bounded, Enum, Show, Read)

For example the computer would write the same == algorithms above for MyIntegerList and MyList.

Reference: Haskell 2010 Chapter 11: Specification of Derived Instances

Number types and classes

Standard library has Int, Integer, Rational, Float (single-precision floating point), Double (double-precision floating point), Complex a (a is Double or Float usually).

Number operations are grouped into several type classes, e.g.,

Num:
some methods: +, -, *, abs
instances: all number types

Integral:
some methods: div, mod
instances: Int, Integer

Fractional:
some methods: /, recip
instances: Rational, Float, Double, Complex Float, Complex Double

Floating:
some methods: log, exp, sqrt, pi, trig functions
instances: Float, Double, Complex Float, Complex Double

You can add your own number type by making it an instance of the relevant classes. (E.g., you could have written your own Rational and Complex.)

Reference: Haskell 2010 Section 6.4: Numbers

Exercise: Why is this a type error? 

let xs :: [Double]
    xs = [1, 2, 3]
in sum xs / length xs

Answer:
sum xs :: Double
length xs :: Int
(/) wants the two operands to be of the same type.

How to fix: sum xs / fromIntegral (length xs)
or use realToFrac 

fromIntegral :: (Integral a, Num b) => a -> b
realToFrac :: (Real a, Fractional b) => a -> b

Example: Machine epsilon.

https://gist.github.com/AndrewBarfield/2557034 is forced to write two copies of the same code for two number types because C# is a stupid language.

This is criminal in this the 21st Century.

(But see https://twitter.com/mosheroperandi/status/856946180810354688 for even worse!)

A satisfactory language allows you to hand in just one copy: 

epsilon :: (Ord a, Fractional a) => a
epsilon = let
    -- [1, 0.5, 0.25, ...]
    halves = iterate (/ 2) 1
    -- But only those that satisfy 1+e > 1.
    notTooSmall = takeWhile (\e -> 1 + e > 1) halves
    -- The last such e is the machine epsilon.
    in last notTooSmall

epsilonDouble :: Double
epsilonDouble = epsilon

epsilonFloat :: Float
epsilonFloat = epsilon
in HaskellTypes2.hs

What other statically-typed languages do

C++

Before C++20: Template function prototype does not say which overloaded functions/operators it uses: 

template<typename T> List<T> insertionSort(List<T> xs)
{
   ... just go ahead use <= on T values ...
}

But template is like macro. At use site, compiler has access to the insertionSort template code (to expand it right there), can see it uses <=, can check the user-chosen type supports it.

Works, but tight coupling and all its problems: defeats separate compilation, poor error messages.

Since C++20: That, plus concepts, similar to Haskell classes and can do other things.

Java, Scala, Rust, etc.

Type signature states that the type variable has to extend an interface: 

<T extends Comparable<T>> List<T> insertionSort(List<T>)

Learned from Haskell type classes but adapted to OOP. (In fact, Java generics came from Phil Wadler who brought it from Haskell parametric polymorphism.)

Good de-coupling and all its benefits (Haskell type classes too):

SML, Caml, OCaml

A module can take other modules as parameters. Real Template Methods.

Put insertionSort into a module—call it Sorter—but it takes as parameter another module that specifies element type and comparator. 

(* Example in OCaml *)
module Sorter(Cmp : sig
                      type t
                      val leq : (t,t) -> bool
                    end)
= struct
    let rec insertionSort xs = ...
      (* insertion sort code; use Cmp.leq to compare *)
end

To use Sorter for ints, write a module that contains int comparison operators, use it to instantiate Sorter. 

(* Example in OCaml *)
module IntCmp = struct
    type t = int
    let leq (x,y) = x<=y
end

module IntSorter = Sorter(IntCmp)
(* Now can use IntSorter.insertionSort for [int] *)

Similarly for other element types, even alternative orders.