Week 7: Notes

standard type classes
numeric type classes
type conversions
list comprehensions
case expressions

You can read about these subjects in Learn You a Haskell, chapters 2 - 4.

combinatorial recursion

List comprehensions are convenient for solving combinatorial recursive problems, i.e. finding subsets, combinations, permutations and so on. When we solve these problems we will generally use a bottom-up approach, i.e. we will write a function that produces a list of all possible solutions.

As an example, let's write a function to return a list of all subsets of a set given as a list of elements. Here's one way to view this problem: given a list, we know that in each subset either its first element x will either be present, or absent. So we can recursively generate all subsets of the remaining elements xs. Then for each such subset s, x : s is a subset of the original list (in which x is present), and s is also a subset (in which x is absent).

Here's one possible implementation of this idea:

subsets :: [a] -> [[a]]
subsets [] = [[]]
subsets (x : xs) = [ x : s | s <- subs]  ++ subs
  where subs = subsets xs

Alternatively, we could write the last equation like this:

subsets (x : xs) = [ t | s <- subsets xs, t <- [x : s, s]]

Or like this:

subsets (x : xs) = concat [ [x : s, s] | s <- subsets xs]

Maybe

For any type t, a value of type Maybe t is either Just x (where x has type t) or Nothing. For example, Just 4, Just 0 and Nothing are all possible values of type Maybe Int.

So the constant Nothing is something like null or None in other languages: it represents the absence of a value. When we write a function that might succeed or fail, we will often make its return type be Maybe t for some type t. Then the function will return a Just if it succeeds, otherwise Nothing.

For example, here's a function that will look up a key in an association list, i.e. a list of key-value pairs. If it finds the key, it will return the associated value; otherwise it returns Nothing.

lookup :: Eq a => a -> [(a, b)] -> Maybe b
lookup _ [] = Nothing
lookup x ((k, v) : rest)
    | x == k = Just v
    | otherwise = lookup x rest

Let's try it:

> d = [('x', 3), ('y', 5), ('z', 7)]
> lookup 'y' d
Just 5
> lookup 'q' d
Nothing

In fact this function is built into Haskell's standard library.

type defaulting

In Haskell, even numeric literals are polymorphic:

> :t 2
2 :: Num a => a
> :t 3.5
3.5 :: Fractional a => a

We see that 2 may have any type that's an instance of the Num type class (e.g. Int, Integer, Float, Double). Similarly, 3.5 may have any type that's an instance of Fractional (e.g. Float, Double). We may choose any compatible type that we like:

> 2 :: Integer
2
> 3.5 :: Float
3.5

Even when we combine literals using operators, the result may still be polymorphic:

> :t (2 + 2)
(2 + 2) :: Num a => a
> :t (2 + 3.5)
(2 + 3.5) :: Fractional a => a

However in some situations Haskell must choose a type. For example, suppose that we actually perform the addition:

> 2 + 2
4
> 2 + 3.5
5.5

What type did Haskell use in the calculation? Its rule is that if it must resolve an ambiguous numeric type, it will use the first of these types that is possible: Integer, Double. Thus, the first addition above was performed using values of type Integer, and the second used type Double.