Week 9: Notes

the $ operator
as patterns
folds
type synonyms
algebraic datatypes
recursive data structures
derived instances

You can read about these subjects in Learn You A Haskell, chapters 4, 6, and 8.

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]