Higher-Order Operations

Searching lists: find

Basics - The simplest case is just (find Entry List), usually used as a predicate: "is Entry in List?". If it succeeds in finding the element in question, it returns the first matching element instead of just "t".

(if (find 3 '(1 2 3 4)) 'Yes 'No) ==> YES
(find 4 '(1 2 3 4 5)) ==> 4

:test - Tells Lisp what predicate to use to when comparing the entry you supplied to each element of the list (default is "eql"). Thus
(find Entry List :test Predicate) means "is there an element of List such that Entry and that element are related by Predicate? If so, return the first such element". For instance
(find 3 '(2 4 6 8) :test #'<)
means "is there an element of (2 4 6 8) such that (< 3 element) returns true? If so, return the first one", and would return 4. Remember that lists and strings are not comparable by "eql", so you need to use a :test of #'equal if you want to look for lists or strings embedded in another list.

(find '(A B)'((A B) (C D) (E F)) ==> NIL
(find '(A B)'((A B) (C D) (E F) :test #'equal)
  ==> (A B)
(defun Almost-Equal (Num1 Num2)
  (<= (abs (- Num1 Num2)) 0.1))
(find pi '(2.9 3.0 3.1 3.2 3.3) 
      :test #'Almost-Equal) ==> 3.1

:key - Tells Lisp what part of each element of the list to compare to the supplied entry. Thus (find Entry List :key Function) means "is there an element of List such that Entry is eql to (Function element)? If so, return the first such element." For instance,
(find 2 '((1 2) (2 3) (3 4)) :key #'second) means "find an element of ((1 2) (2 3) (3 4)) such that 2 is eql to second of that element", and would return (1 2). :test may be combined with :key.

(find A '((A B) (C D E) (F G H I))
        :key #'first) ==> (A B)
(find 3 '((A B) (C D E) (F G H I)) 
      :key #'length) ==> (C D E)
(find '(D E) '((A B) (C D E) (F G H I))
      :key #'rest :test #'equal) ==> (C D E)

find-if/find-if-not

The "find-if" function is used to find an element of list that satisfies some predicate. It takes a :key arg, but not :test since the test is now a required argument.

(find-if #'evenp '(1 2 3 4)) ==> 2
(find-if #'oddp '((0 1) (1 2) (2 3))
         :key #'first) ==> (1 2)

The "find-if-not" function finds the first element of the list that fails a given predicate.

Alternatives to find: assoc/member

The "assoc" function is like "find" with a built-in :key of #'first. The "member" function is like "find" except that, if a match is found, it returns the entire target list starting at the match, rather than just the match itself. There are also analogous "assoc-if" and "member-if" functions.

(assoc 'B '((A B) (B C) (C D)) ==> (B C)
(member 2 '((0 1) (1 2) (2 3)) :key #'second)
  ==> ((1 2) (2 3))

Filtering lists: remove/remove-if

The "remove" function returns a new list that is like the input list, except with all occurrences of the supplied entry removed. It takes :test and :key options in a manner similar to "find".

(remove 1 '((0 1) (1 2) (2 3)) :key #'first)
  ==> ((0 1) (2 3))

The "remove-if" function returns a new list that was like the old list except that all elements satisfying a given predicate are removed. Like "find-if", it takes a :key option, but not :test. There is an analogous "remove-if-not".

(remove-if #'evenp '(1 2 3 4 5)) ==> (1 3 5)
(remove-if-not #'evenp '(1 2 3 4 5)) ==> (2 4)

Transforming lists: mapcar

The basic case of "mapcar" is that it takes a function of one argument and a list. It applies the function to each element of the list, collects the results, and returns them.

(mapcar #'sqrt '(1 4 9 16 25)) ==> (1 2 3 4 5)
(mapcar #'first '((A B) (C) (D E))) ==> (A C D)

The slightly more complicated case of "mapcar" is that it takes an N-ary function (a function that expects N arguments) and N lists. It applies the function to the first elements of each of the lists, then the second, and so forth, collecting the results. Technically, it stops when the shortest list ends, but it is normally considered poor style to supply lists of differing lengths.

(mapcar #'+ '(1 2 3 4)
            '(5 6 7 8)) ==> (6 8 10 12)
(mapcar #'list '(A B C D)
               '(E F G H)) 
  ==> ((A E) (B F) (C G) (D H))

Calling functions explicitly: funcall/apply

The function "funcall" takes a function and individual arguments, and calls the function with the specified arguments. It is usually used when the particular function to be called is not known in advance, but is passed in (e.g. to implement the :test and :key arguments).

(funcall #'+ 1 2 3) ==> 6
(funcall #'append '(A B) '(C D) '(E F G))
  ==> (A B C D E F G)

The "apply" function is similar to "funcall", but it expects the arguments to come in a list, rather than individually. It is normally used when you have an indeterminate number of arguments.

(apply #'+ '(1 2 3)) ==> 6
(apply #'append '((A B) (C D) (E F G)))
  ==> (A B C D E F G)

If "apply" gets passed more than just a list of arguments, the extra values are attached to the front of the list.

(apply #'+ 5 '(1 2 3)) == (apply #'+ '(5 1 2 3))
  ==> 11

Since it seems to be more common to want to keep all elements that satisfy a given predicate than to remove all elements that satisfy a predicate, sometimes people define "Keep-If" as a renamed version of "remove-if-not":

(defun Keep-If (Pred Lst &rest Specifiers)
  (apply #'remove-if-not Pred Lst Specifiers))

Searching lists: find
find-if/find-if-not
Alternatives to find: assoc/member
Filtering lists: remove/remove-if
Transforming lists: mapcar
Calling functions explicitly: funcall/apply