Week 10: Notes

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.

case expressions
higher-order functions
lambda expressions
operator sections
function composition

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