Unit 4: ZF-expressions

Introduction

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] and x is even. Thus, the above ZF-expression evaluates to [4, 144]. The general form of a ZF-expression 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.

Reduction rules for ZF-expressions

The behaviour of ZF-expressions 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 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)