Unit 4: ZFexpressions
Introduction
ZFexpressions are a convenient way of defining lists in Haskell. The following is an example of such an expression:
[ x * x  x < [1, 2, 7, 12], even x ]
This ZFexpression 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 ZFexpression evaluates to [4, 144]
.
The general form of a ZFexpression 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
.
Reduction rules for ZFexpressions
The behaviour of ZFexpressions 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 ZFexpressions:
quick [] = []
quick [x] = [x]
quick (x:xs) = quick [ u  u < xs, u < x ]
++ [x] ++
quick [ u  u < xs, u >= x ]
© Antoni Diller (30 May 2016)