## In praise of 'reduce'

1st June 2020

The sequence functions are a powerful feature of Common Lisp; in conjunction with their **:test** and **:key** parameters you can often achieve in a single statement what would otherwise take a program of several lines to achieve. For example, suppose we have the English word data I used in my previous post:

(defvar *data* '((3 . "one") (3 . "two") (5 . "three") (4 . "four") (4 . "five") (3 . "six") (5 . "seven") (5 . "eight") (4 . "nine") (3 . "ten")))

you could find the first word with an even score with:

> (find-if #'evenp *data* :key #'car) (4 . "four")

### Reduce

One of my favourite sequence functions is **reduce**, which does what's often called a **fold** in functional programming languages such as Haskell ^{[1]}. It appeals to me because it often proves useful in unexpected places. However, it behaves slightly differently from the other sequence functions. For example, I recently wanted to use **reduce** to find the item with the largest key in a list like the one above, and tried:

> (reduce #'max *data* :key #'car) 5

and I was puzzled about why **reduce** returned **5** and not **(5 . "three")** which is what I wanted.

I realised that the answer is that **reduce** combines items a pair at a time with a binary function, such as **#'+**, and the result is not usually the key of one of the items. The **max** (and **min**) functions are unusual in that they do return one of their arguments.

Does this mean that you couldn't use **reduce** in this application? One solution would be to do:

> (reduce #'(lambda (x y) (if (>= (car x) (car y)) x y)) *data*) (5 . "three")

### Using reduce to pick a random item from a weighted collection

Another nice use of **reduce** is to pick an item at random from a list of items with a weight for each item. Here's a classic example; the initial bag of scrabble tiles with the number of each tile in the bag:

(defparameter *scrabble* '((9 . #\A) (2 . #\B) (2 . #\C) (4 . #\D) (12 . #\E)

(2 . #\F) (3 . #\G) (2 . #\H) (9 . #\I) (1 . #\J) (1 . #\K) (4 . #\L) (2 . #\M)

(6 . #\N) (8 . #\O) (2 . #\P) (1 . #\Q) (6 . #\R) (4 . #\S) (6 . #\T) (4 . #\U)

(2 . #\V) (2 . #\W) (1 . #\X) (2 . #\Y) (1 . #\Z) (2 . #\space)))

The bag contains a total of 100 tiles, with 9 tiles marked 'A' through to 1 tile marked 'Z'. We want to pick one tile at random from the bag.

It's not immediately obvious that you could use **reduce** to solve this in a single statement, but here's the solution. First define **pick**:

(defun pick (a b) (let ((total (+ (car a) (car b)))) (if (< (random total) (car a)) (cons total (cdr a)) (cons total (cdr b)))))

The function **pick** takes two items with weights; for example:

> (pick '(9 . #\A) '(2 . #\B)) (11 . #\A)

It returns a pair consisting of the sum of the weights, **total**, and the first or second item chosen at random according to their respective weights.

The solution to the original problem is then:

(defun random-tile () (cdr (reduce #'pick *scrabble*)))

For each element in the list **reduce** chooses the latest **(weight . item)** pair in preference to the current **(total . item)** pair with probability **weight/total**, which is exactly what we want.

- ^ Fold (higher-order function) on Wikipedia.

blog comments powered by Disqus