Unit 4: ZF-expressions
ZF-expressions 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 ZF-expression is the list of all those things of the form
x * x such that
x is drawn from the list
[1, 2, 7, 12]
x is even.
Thus, the above ZF-expression evaluates to
The general form of a ZF-expression is:
[ EXP | QUAL, ..., QUAL ]
is either a Boolean-valued expression or a generator.
A generator has one of two forms: either
VARIABLE <- LIST or
PATTERN <- LIST.
Reduction rules for ZF-expressions
The behaviour of ZF-expressions is completely determined by the following five reduction rules:
Hoare's Quicksort algorithm can be expressed very concisely by using a couple of ZF-expressions:
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)