Unit 4: List comprehensions
Introduction
List comprehensions are a convenient way of defining lists in Haskell. List comprehensions used to be called ZFexpressions. 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 Booleanvalued 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 ]
© Antoni Diller (17 September 2021)