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