Common lisp :KEY parameter use

Question

The :KEY parameter is included in some functions that ship with Common Lisp. All of the descriptions that I have found of them are unhelpful, and :KEY is difficult to search in a search engine because the ":" is usually ignored.

How would it be used, for example, in the member function which allows both :TEST and :KEY?

Stormy

The Common Lisp HyperSpec has an index page. You find :key on the index page Non-Alphabetic: lispworks.com/documentation/HyperSpec/Front/X_Mast_9.htm – Twocolor

Thanks for that. I now understand how :key works, but I award no thanks to the hyperspec's clarity. – Stormy

Keep in mind that the HyperSpec is 'just' a version of the official language specification - similar to the Scheme, ECMAscript, C++, or Java specifications. It's not a tutorial or introductory book. – Twocolor

Answer 1

Imagine that we have a list of cities:

(defparameter *cities*
   ; City       Population  Area km^2
  '((Paris      2265886     105.4)
    (Mislata    43756       2.06)
    (Macau      643100      30.3)
    (Kallithea  100050      4.75)
    (Nea-Smyrni 73090       3.52)
    (Howrah     1072161     51.74)))

Now we can compute the population density in people/km^2

(defun city-density (city)
  "the density is the population number divided by the area"
  (/ (second city) (third city)))

Now we want to compute a list of all cities which have a density less than 21000 people/km^2.

We remove all larger ones from the list and are providing a :test-not function. We need to provide an anonymous function which does the test and computes the density of the city to compare.

CL-USER 85 > (remove 21000 *cities*
                     :test-not (lambda (a b)
                                 (>= a (city-density b))))

((NEA-SMYRNI 73090 3.52) (HOWRAH 1072161 51.74))

We can write it simpler without the anonymous function by providing the numeric :test-not function >= and use the city-density function as the key to compute the value from each provided cities:

CL-USER 86 > (remove 21000 *cities* :test-not #'>= :key #'city-density)

((NEA-SMYRNI 73090 3.52) (HOWRAH 1072161 51.74))

So having both a test predicate and a key function makes it easier to provide the building blocks for sequence computations...

Now imagine that we use CLOS and a list of city CLOS objects:

(defclass city ()
  ((name :initarg :name :reader city-name)
   (population :initarg :population :reader city-population)
   (area :initarg :area :reader city-area)))

(defparameter *city-objects*
  (loop for (name population area) in *cities*
        collect (make-instance 'city
                               :name name
                               :population population
                               :area area)))

(defmethod density ((c city))
  (with-slots (population area)
      c
    (/ population area)))

Now we compute the list as above:

CL-USER 100 > (remove 21000 *city-objects* :test-not #'>= :key #'density)
(#<CITY 42D020DDFB> #<CITY 42D020DF23>)

CL-USER 101 > (mapcar #'city-name *)
(NEA-SMYRNI HOWRAH)

If we have the density as a slot with a getter, we can do this:

(defclass city ()
  ((name :initarg :name :reader city-name)
   (population :initarg :population :reader city-population)
   (area :initarg :area :reader city-area)
   (density :reader city-density)))

(defmethod initialize-instance :after ((c city) &key)
  (with-slots (density)
      c
    (setf density (density c))))

(defparameter *city-objects*
  (loop for (name population area) in *cities*
        collect (make-instance 'city
                               :name name
                               :population population
                               :area area)))

Now we compute the list as above, but the key is the getter of the density slot:

CL-USER 102 > (remove 21000 *city-objects* :test-not #'>= :key #'city-density)
(#<CITY 42D026D7EB> #<CITY 42D026D913>)

CL-USER 103 > (mapcar #'city-name *)
(NEA-SMYRNI HOWRAH)

Twocolor

Thank you for the in depth answer to my three year old question. – Stormy

Answer 2

The :key argument is documented, somewhat cryptically, in the introductory sections to the Sequences Library (Section 17) in the Common Lisp HyperSpec, under 17.2.1 Satisfying a Two-Argument Test as well as 17.2.2 Satisfying a One-Argument Test. This is because its behavior is consistent across the library.

Quite simply, :key specifies the function which is applied to the elements of the sequence or sequences being processed. The return value of the function is used in place of those elements. In the terminology of some functional languages, this is called a "projection". The elements are projected through the key function. You can imagine that the default key function is identity, if you don't supply this argument.

One important thing to understand is that in functions which accept some object argument and a sequence (for instance functions which search a sequence for the occurrence of an object), the key function is not applied to the input object; only to the elements of the sequence.

The second important thing is that :key doesn't substitute for the item, only for the value which is used to identify the item. For instance, a function which searches for an item in a sequence will retrieve the original item from a sequence, even if the items of the sequence are projected to alternative keys via :key. The value retrieved by the key function is only used for comparison.

E.g. if obj-list is a list of objects which have a name accessible via a function called obj-name, we might look for the object named "foo" using (find "foo" obj-list :key #'obj-name). The function obj-name is applied to each element, and its result is compared with the string "foo" (to which the function isn't applied). If at least one object by that name exists in obj-list, then the first such object is returned.

Viscoid

There's an exception to your rule "the key function is not applied to the input object; only to the elements of the sequence". It is the function SEARCH. Example: (search '(0 1) '(2 4 6 1 3 5) :key #'oddp) => 2 because it applies #'oddp to both sequences which is similar to (search '(nil t) '(nil nil nil t t t) => 2. It is the example given by spec: clhs.lisp.se/Body/f_search.htm – Amaryllidaceous

Answer 3

The :key argument is a function of one parameter; it is applied to each element of the sequence to generate the value used for testing. If omitted, the identity function is used.

Here's an example from the CLHS:

(member 2 '((1 . 2) (3 . 4)) :test-not #'= :key #'cdr) =>  ((3 . 4))

Eleneeleni