Type Classes

We have seen that types are sets values that bear similarities. Similarly, type classes are sets of types that bear similarities. In particular, every type in a particular class defines a common set of members with particular type signatures.

Defining Type Classes

Consider the Eq type class from the Prelude. There are two parts to the definition. First, a list of members and type signatures that must be implemented by any type a to be added to the Eq type class. Second, a list of default implementations for members that are not provided explicitly.

class Eq a where
  -- type signatures for required members
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool

  -- default implementations (for those that are not overriden)
  x == y = not (x /= y)
  x /= y = not (x == y)

In this class, notice how (==) and (/=) are defined mutually recursively. As long as one of the operations is defined for a particularly type (overriding the default definition), the definition of the other "comes for free."

In addition to the definition itself, there are two additional components that are described informally, in comments or in the documentation. First, because of the default implementations, the minimal complete definition is either (==) or (/=); no need to provide both.

The second additional component is a set of (unchecked) laws that each implementation is assumed to satisfy. For each type a in Eq, the law is:

forall x :: a, y :: a. (x == y) == not (x /= y)

Notice that this law is respected by the default implementations, but can be broken by an explicit instance definition.

Defining Type Class Instances

Adding a type t to a class C requires an instance declaration that implements the members of C, with types specialized to t.

As a simple example, consider a hard-coded integer list type:

data IntList
  = Nil
  | Cons Int IntList

We can add IntList to the Eq class as follows:

instance Eq IntList where
 -- (==) :: IntList -> IntList -> IntList
    Nil       == Nil        = True
    Cons x xs == Cons y ys  = x == y && xs == ys
    _         == _          = False

This function first checks that the data constructors match and, if so, then recursively checks that the corresponding components are equal. Notice that the call to (==) in x == y refers to the implementation (provided by Haskell) for Ints and the call to (==) in xs == ys refers to the implementation in the IntList instance (that is, the function currently being defined recursively).

We have seen how deriving clauses can be used to automatically generate instance declarations for certain classes. If had defined IntList with the clause deriving (Eq), the implementation above is essentially what will get generated automatically. In situations where the default implementation is not what we want, we can manually declare the instance.

There can be at most one instance declaration for a given type and class. This design decision restricts some potentially useful programming patterns in exchange for automatically knowing where to find the implementation of any call to a type class member based on the types of its arguments.

Try adding a second Eq IntList instance declaration (either explicitly or by adding a deriving (Eq) clause).

Consider a polymorphic list definition.

data List a
    = Nil
    | Cons a (List a)

instance Eq a => Eq (List a) where
 -- (==) :: List a -> List a -> List a
    Nil       == Nil        = True
    Cons x xs == Cons y ys  = x == y && xs == ys
    _         == _          = False

Note that our instance declaration requires a type class constraint, to ensure that the underlying type a is also part of Eq. The call to (==) in xs == ys refers to the implementation from the Eq a instance. This implementation can also be automatically derived via deriving (Eq).

Show and Read

class Show a where
  show :: a 
  ...

> :t show

Automatically derived Show instance for List a:

> Cons 1 (Cons 2 (Cons 3 Nil))
Cons 1 (Cons 2 (Cons 3 Nil))

We can make them look more like built-in lists.

instance Show a => Show (List a) where
 -- show             :: List a -> String
    show Nil         =  "[]"
    show (Cons x xs) =  "(" ++ show x ++ " : " ++ show xs ++ ")"

> Cons 1 (Cons 2 (Cons 3 Nil))
(1 : (2 : (3 : [])))

The read function is used to parse Strings into values of some type.

> :t read
read :: Read a => String -> a

Notice how the type variable a is referred to only in the output. Therefore, we can tell that the function will crash (rather than return an error via Maybe) when the there is no meaningful a value to return for the given input String. Furthermore, Haskell needs information from the context in which read is called to figure out which instance declaration to use.

> read "1"
*** Exception: Prelude.read: no parse
*List> read "1" :: Int
1
*List> read "1" :: Integer
1
*List> read "1" :: Float
1.0
*List> read "1" :: Bool
*** Exception: Prelude.read: no parse

This read function is not defined inside the Read class, but is instead of a helper function defined in terms of a more general readsPrec function:

class Read a where
  readsPrec :: Int -> String -> [(a, String)]
  ...

We will see some example parsers in detail later on.

Num

> :info Num
> :info Int
> :info Floating
> :info Integral

Int andInteger have a common typeclass called Integral.

Ord

> :info Ord

Enum

> :info Enum

> [False .. True]
> [True .. False]

Bounded

> :info Bounded

> minBound :: Int
> maxBound :: Int
> minBound :: Integer

> :t minBound
> minBound + 0
> (minBound :: Int) + (minBound :: 1)
> (minBound :: Int) + 1
> (minBound :: Int) + 2
> minBound + (2 :: Int)

Foldable

Last week, we saw how the higher-order functions map and filter eliminate boilerplate code when writing recursive list functions. Today, we'll see an even more general function called fold (a.k.a. reduce, as in MapReduce).

List Fold-Right

This function generalizes the natural recursion pattern.

sum []         =  0
sum (x:xs)     =  x + sum xs

prod []        =  1
prod (x:xs)    =  x * prod xs

concat []      = []
concat (x:xs)  = x ++ concat xs

Don't Repeat Yourself! foldr

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f acc []      =  acc
foldr f acc (x:xs)  =  f x (foldr f acc xs)
                          -- let result = foldr f acc xs in
                          -- f x result

Notice the use of the variable acc. Writing helper functions with "accumulators" is a common trick in functional programming. Each recursive call updates the accumulator, and the base case returns the initial accumulator.

For a call of the form (foldr f init [x1, x2, x3]), the function f is applied to the rightmost element in the list first.

--     x1  :  (x2  :  (x3  :  []))
--     x1 `f` (x2 `f` (x3 `f` init))  -- rightmost first

Now, via foldr and eta-reduction:

sum  = foldr (+) 0
prod = foldr (*) 1
cat  = foldr (++) []

And another:

len = foldright addOne 0
  where addOne _ acc = 1 + acc

len = foldr (\_ acc -> 1 + acc) 0
len = foldr (\_ -> (1+)) 0         -- not necessarily better
len = foldr (+) 0 . map (const 1)  -- same here, and two passes

And another:

max []     = error "empty list!"
max (x:xs) = foldright foo x xs
  where foo a acc | a > acc   = a
                  | otherwise = acc

List Fold-Left

There's also a version of fold that applies the function from left-to-right:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc []      =  acc
foldl f acc (x:xs)  =  foldl f (f acc x) xs
                         -- let acc' = f acc x in
                         -- foldl f acc' xs

Notice the following cosmetic difference, that the order of arguments to f differs between foldr and foldl: for foldr, the function f takes a list element (of type a) first and the accumulating value (of type b) second, whereas for foldl this order is swapped.

Unlike foldr, for a call of the form (foldl f init [x1, x2, x3]), the function f is applied to the leftmost element first:

--            x1   :  (x2   :  (x3  :  []))
-- ((init `f` x1) `f`  x2) `f`  x3            -- leftmost first

Like with foldr, each recursive call updates the accumulator. This time, the base case returns the accumulator as the final result.

Trees

Lots of other data structures can be folded over, too.

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

Notice how the Foldable type t is used in the type t a above; it is a type that takes a type (in particular a) an argument. This is a different kind of type than those ranged over by a and b, which are not applied to any type arguments. Yep, there are different kinds of types... Stay tuned.

Minimum complete definition is foldr. Foldable has other members, which we will talk about much later.

Example:

data BinaryTree a
    = Empty
    | Node a (BinaryTree a) (BinaryTree a)
    deriving (Show)

instance Foldable BinaryTree where
 -- foldr :: (a -> b -> b) -> b -> BinaryTree a -> b
    foldr f acc Empty = acc
    foldr f acc (Node x left right) =
      foldr f (f x (foldr f acc right)) left

A useful helper function defined in terms of foldr:

> :t concat

Source Files

results matching ""

    No results matching ""