Unit 4: List comprehensions

Introduction

List comprehensions are a convenient way of defining lists in Haskell. List comprehensions used to be called ZF-expressions. The following is an example of such an expression:

[ x * x | x <- [1, 2, 7, 12], even x ]

This list comprehension is the list of all those things of the form x * x such that x is drawn from the list [1, 2, 7, 12] and x is even. Thus, the above evaluates to [4, 144]. The general form of a list comprehension is:

[ EXP | QUAL, ..., QUAL ]

where QUAL is either a Boolean-valued expression or a generator. A generator has one of two forms: either VARIABLE <- LIST or PATTERN <- LIST.

Alternative notation

The list comprehension displayed above can also be written using the do-notation. To use this you need to load the Control.Monad module:

ghci> import Control.Monad
ghci> do { x <- [1,2,7,12] ; guard (even x) ; return (x * x) }
[4,144]

This works because lists constitute a monad. The do-notation is usually written without using curly brackets and semicolons like this:

do x <- [1,2,7,12] 
   guard (even x) 
   return (x * x)

Reduction rules for list comprehensions

The behaviour of list comprehension is completely determined by the following five reduction rules:

(ZF1)	`[ e \| v <- [], q ]` reduces to `[]`, where `q` is a sequence of zero or more qualifiers.
(ZF2)	`[ e \| v <- f:fs, q ]` reduces to `[ e \| q ] [ v := f ] ++ [ e \| v <- fs, q ]`, where `h [ v := f ]` represents `h` with all occurrences of `v` in it replaced by `f`.
(ZF3)	`[ e \| False, q ]` reduces to `[]`.
(ZF4)	`[ e \| True, q ]` reduces to `[ e \| q ]`.
(ZF5)	`[ e \| ]` reduces to `[ e ]`.

Quicksort

Hoare's Quicksort algorithm can be expressed very concisely by using a couple of list comprehensions:

quick :: Ord a => [a] -> [a]
quick []     = []
quick [x]    = [x]
quick (x:xs) = quick [ u | u <- xs, u < x ]
               ++ [x] ++
               quick [ u | u <- xs, u >= x ]