# 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)