Week 7: Notes

There was no lecture or tutorial this week.

Our topics for this week include

To learn these features, please read the following sections of Learn You a Haskell:

    2. Starting Out: Texas ranges, I'm a list comprehension

    4. Syntax in Functions: Guards, guards!, Where!?, Case expressions

Here are some additional notes.

Standard library functions

You should start to become familiar with the functions in Haskell's standard library, especially the many functions that operate on lists. Our Haskell Library Quick Reference lists various useful functions (and I will add more as the course proceeds). Notice that the top of the quick reference page lists various type classes. Most built-in Haskell types implement Eq, Ord, Show and Read, so the functions in those type classes are available for all those types. After that, the reference lists functions that are defined on specific types such as Bool, Char, String and lists.

Combinatorial problems

List comprehensions and recursion are useful for solving various combinatorial problems. Let's look at a couple of examples.

Suppose that we want to generate lists representing all subsets of a given list's elements:

> subsets [1, 2, 3]

[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]

Here is one possible solution:

subsets :: [a] -> [[a]]

subsets [] = [[]]

subsets (x : l) = (subsets l) ++ [ x : m | m <- subsets l ]

The function's type is [a] -> [[a]] because it maps a list of elements to a list of lists of elements.

We must take some care in writing the base case. How many subsets does the empty set have? There is one – the empty set. If we wrote "subsets [] = []", that would be saying that the empty set has no subsets, and the function would not work.

The recursive case works as follows. If we are given a list (x : l), then every subset of l is a subset of the original list. Also, we can take any subset of l and prepend x to make another subset.

Arguably this function is not as efficient as it could be, because it makes two recursive calls to subsets. Here is an alternate implementation:

subsets [] = [[]]

subsets (x : l) = concat [ [m, x : m] | m <- subsets l ]

This implementation makes only one recursive call to subsets. For each list m that comes back, we generate two lists in the output: m and (x : m).

Notice the important call to concat above. concat will flatten a list of lists:

> concat [[2, 5], [6, 1, 8]]
[2,5,6,1,8]

The call is necessary because in the expression

[ [m, x : m] | m <- subsets l ]

m and (x : m) are sublists, so [m, x : m] is a pair (i.e. a 2-element list) of sublists, so the entire comprehension generates a list of pairs of sublists. But we want only a list of sublists, not grouped into pairs. This illustrates a typical trick that we use in list comprehensions: if you want to generate multiple values from each iteration of the comprehension, put those values in a list (e.g. [m, x : m]), then call concat to combine all the lists at the end.

Let's look at another example: generating all compositions of an integer. A composition of a positive integer N is a set of positive integers whose sum is N, where order matters: 1 + 3 and 3 + 1 are distinct compositions of N = 4. We would like our function to behave like this:

> compositions 4
[[1,1,1,1],[1,1,2],[1,2,1],[1,3],[2,1,1],[2,2],[3,1],[4]]

Here is an implementation in Haskell:

compositions :: Int -> [[Int]]

compositions 0 = [[]]

compositions n = [ k : m | k <- [1 .. n], m <- compositions (n - k) ]

Again, notice that in the base case we return [[]] because there is a single composition of 0: the empty set.

The recursive case works as follows. We choose some integer k (1 ≤ k ≤ n) to be the first integer in the composition. We then recursively generate all compositions of (n - k), and prepend k to each of those compositions.

Note that this list comprehension contains two instances of the <- operator. That is something like a double loop in an imperative language. Order matters: the leftmost instance is like an outer loop.