Lispology

About me

Feeds

Adding a key parameter

18th January 2016

The other day I wanted to find the longer of two lists or strings; the obvious way is:

(if (> (length a) (length b)) a b)

I thought that it would be nice if there was a variant of max which could take a :key parameter, like for example sort, so one could write:

(max* a b :key #'length)

For example, we could write:

CL-USER > (max* "short" "longer" :key #'length)
"longer"

We could easily define this as a Lisp function:

(defun max* (a b &key (key #'identity))
  (if (> (funcall key a) (funcall key b)) a b))

It does what we want:

CL-USER > (max* '(a b c) '(d e f g) :key #'length)
(D E F G)

Generalising adding a key parameter

My next thought was to generalise this by writing a function that adds a key parameter to any function that returns one of two values, such as min, or max.

Here's my first attempt:

(defun add-key1 (test)
  #'(lambda (a b &key (key #'identity))
      (if (funcall test (funcall key a) (funcall key b)) a b)))

This function add-key1 returns a function that applies the test function, using the specified key parameter. So for min we can write:

(funcall (add-key1 #'<) "tiny" "large" :key #'length)

We can associate the function returned by add-key1 with a function name using symbol-function:

(setf (symbol-function 'min*) (add-key1 #'<))

So now we can just write:

CL-USER > (min* "tiny" "large" :key #'length)
"tiny"

Mystery best function

One problem: the above approach requires us to know the comparison function associated with the function we want to redefine, such as > in the case of max and < in the case of min. What about functions where the comparison function isn't obvious?

To test this idea I devised a function best that returns the "best" of two numbers according to a secret criterion. Here are some examples:

CL-USER > (best 7 12)
12

CL-USER > (best 12 15)
15

CL-USER > (best 15 7)
7

As these examples show, it's a non-transitive relation. The best function could be used as the basis for a game between two players, in which they each try to win as many rounds as possible. Here's the definition of best:

(defun best (a b)
  (if (> (abs (- a b)) (min a b)) (min a b) (max a b)))

The larger number wins, unless it's more than twice as large as the other number, in which case the smaller number wins.

Can the add-key function be made to work with this too? What we want is a function that takes one parameter, the function to be modified, and it should return a function that accepts a key parameter, like this:

(funcall (add-key2 #'best) "tiny" "too large" :key #'length)

This should display "tiny".

At first I thought this was impossible, but eventually saw a way of doing it. Try solving this before looking at my suggested answer below.

General add-key function

Here's my solution:

(defun add-key2 (fun)
  #'(lambda (a b &key (key #'identity))
      (let ((afun (funcall key a))
            (bfun (funcall key b)))
        (if (eq (funcall fun afun bfun) afun) a b))))

This function add-key takes a function, and returns a new function with a key parameter added to its parameters. So now we can write:

(setf (symbol-function 'best*) (add-key1 #'best))

and use this as a new function:

CL-USER > (best* "tiny" "too large" :key #'length)
"tiny"

Next: Calculating a resistor network

Previous: Faro-encoding numbers

Most popular posts