Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 38 ยท Lists and Data Structures

List Functions

Process lists the Lisp way with mapcar, remove-if, find-if, reduce, every, some, sort, remove-duplicates and the set operations union and intersection.

Lisp programmers rarely write loops to process lists. Instead they use a toolkit of higher-order functions: functions that take other functions as arguments. This lesson tours that toolkit: mapping, filtering, searching, folding, sorting and set operations, with notes on the keyword arguments (:key, :test) that make them flexible.

Mapping: apply a function to every element

mapcar applies a function to each element and collects the results:

LISP
(mapcar #'1+ '(1 2 3))                  ; => (2 3 4)
(mapcar (lambda (x) (* x x)) '(1 2 3))  ; => (1 4 9)
(mapcar #'+ '(1 2 3) '(10 20 30))       ; => (11 22 33)   several lists in step
(mapcar #'list '(a b) '(1 2))           ; => ((A 1) (B 2))

#'name is shorthand for (function name): it fetches the function object. You will use it constantly; see Lambda and Higher-Order Functions.

Related mapping functions:

Function What it does
mapcar Apply to each element, collect results
mapc Same, for side effects only; returns the first list
mapcan Collect results by nconc-ing them (flatten one level)
maplist Apply to each successive tail
map 'list Generic map over any sequences, output type chosen
LISP
(mapc #'print '(1 2 3))                ; prints 1 2 3 (each on a new line)
(mapcan (lambda (x) (list x x)) '(1 2)) ; => (1 1 2 2)
(maplist #'identity '(a b c))          ; => ((A B C) (B C) (C))
(map 'vector #'1+ '(1 2 3))            ; => #(2 3 4)

Filtering

LISP
(remove-if #'evenp '(1 2 3 4 5 6))        ; => (1 3 5)    drop matches
(remove-if-not #'evenp '(1 2 3 4 5 6))    ; => (2 4 6)    keep matches
(remove 3 '(1 3 2 3))                     ; => (1 2)      drop equal items (eql)
(remove-duplicates '(1 2 1 3 2))          ; => (1 3 2)    keeps the LAST of each
(remove-duplicates '(1 2 1 3 2) :from-end t) ; => (1 2 3) keeps the FIRST
(delete-if #'evenp (list 1 2 3 4))        ; destructive version

remove-if-not is common; SBCL also supports remove-if (complement #'evenp).

Searching

LISP
(find 3 '(1 2 3 4))                       ; => 3
(find-if #'evenp '(1 3 4 5))              ; => 4        first match
(position 3 '(1 2 3 4))                   ; => 2        index
(position-if #'evenp '(1 3 4 5))          ; => 2
(member 3 '(1 2 3 4))                     ; => (3 4)    the TAIL starting at the match
(count-if #'oddp '(1 2 3 4 5))            ; => 3
(find "b" '("a" "b") :test #'string=)     ; => "b"
(find 2 '((1 . a) (2 . b)) :key #'car)    ; => (2 . B)

:key says what to look at in each element before comparing; :test says how to compare. These two keywords appear in nearly every sequence function. member returns the tail, which is always a true value (even when the element you looked for is NIL, because the tail (NIL) is a non-empty list).

Testing: every, some, notany

LISP
(every #'numberp '(1 2 3))         ; => T
(every #'evenp '(2 4 5))           ; => NIL
(some #'evenp '(1 3 4))            ; => T      (returns the predicate's value)
(notany #'minusp '(1 2 3))         ; => T
(every #'< '(1 2 3) '(2 3 4))      ; => T      two lists compared in step

Mapping and filtering on the Mini-Lisp (a JavaScript stand-in interpreter, not SBCL):

JS Mini-Lisp: mapcar, remove-if, reduce

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The Mini-Lisp's mapcar accepts one list only; real Common Lisp maps over several lists in step, as shown in the read-only examples above.

Folding: reduce

reduce combines all elements with a two-argument function:

LISP
(reduce #'+ '(1 2 3 4 5))                  ; => 15
(reduce #'max '(3 9 2))                    ; => 9
(reduce #'+ '(1 2 3) :initial-value 100)   ; => 106
(reduce #'list '(1 2 3 4))                 ; => (((1 2) 3) 4)   left-associative
(reduce #'list '(1 2 3 4) :from-end t)     ; => (1 (2 (3 4)))
(reduce #'+ '())                           ; => 0   (+ with no args)
(reduce #'+ '(5))                          ; => 5

Supplying :initial-value is wise when the list may be empty and the function has no sensible zero-argument result.

Sorting

LISP
(sort (list 3 1 2) #'<)                    ; => (1 2 3)
(sort (list "pear" "fig") #'string<)       ; => ("fig" "pear")
(sort (list '(b 2) '(a 9)) #'< :key #'second) ; => ((B 2) (A 9))
(stable-sort (list '(b 1) '(a 1) '(c 0)) #'< :key #'second) ; => ((C 0) (B 1) (A 1)) equal keys keep their order

sort is destructive. It may rearrange the cells of its argument, so the original variable can end up pointing into the middle of the result. Always use the return value, and sort a copy if you need the original:

LISP
(defparameter *data* (list 3 1 2))
(sort (copy-list *data*) #'<)     ; => (1 2 3), *data* intact

Never sort a quoted literal: (sort '(3 1 2) #'<) modifies a constant.

Set operations

Lists can act as sets (unordered, no duplicates), with tests via :test:

LISP
(union '(1 2 3) '(3 4 5))              ; => some order of (1 2 3 4 5)
(intersection '(1 2 3) '(2 3 4))       ; => some order of (2 3)
(set-difference '(1 2 3) '(2))         ; => some order of (1 3)
(subsetp '(1 2) '(1 2 3))              ; => T
(adjoin 4 '(1 2 3))                    ; => (4 1 2 3)  add only if missing
(adjoin 2 '(1 2 3))                    ; => (1 2 3)

The order of results is unspecified by the standard, so sort them or compare with subsetp in both directions instead of relying on order. For big sets use a hash table (see Hash Tables).

A stand-in for union and set difference

This JavaScript stand-in follows the same semantics (with eql-style :test), just to make the behavior visible. It is not Lisp.

JS Stand-in: sets, :key and :test

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Putting it together

LISP
(defun average (numbers)
  (/ (reduce #'+ numbers) (length numbers)))

(average '(1 2 3 4))     ; => 5/2

(defun longest-word (words)
  (reduce (lambda (a b) (if (>= (length a) (length b)) a b)) words))

(longest-word '("fig" "banana" "plum"))   ; => "banana"

(defun squares-of-evens (numbers)
  (mapcar (lambda (x) (* x x))
          (remove-if-not #'evenp numbers)))

(squares-of-evens '(1 2 3 4 5 6))    ; => (4 16 36)

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does (remove-if-not #'evenp '(1 2 3 4)) return?

    remove-if-not keeps the elements for which the predicate is true.
  2. 2. What does (member 3 '(1 2 3 4)) return?

    member returns the tail of the list starting at the match.
  3. 3. Why should you write (sort (copy-list xs) #'<) instead of (sort xs #'<) if you still need xs?

    sort may reuse cells, so the original variable might no longer hold the whole list.
  4. 4. What does (reduce #'+ '(1 2 3) :initial-value 100) return?

    The initial value starts the fold: 100 + 1 + 2 + 3.
  5. 5. What is the role of :key in (find 2 pairs :key #'car)?

    :key transforms each element before the comparison.

Summary

  • mapcar transforms; mapc is for effects; mapcan flattens; map can produce any sequence type.
  • remove-if, remove-if-not, remove-duplicates filter; find, position, member, count-if search.
  • every, some, notany test predicates; reduce folds (use :initial-value).
  • sort is destructive: copy first and use its return value.
  • :key and :test customize what is compared and how; set functions return unspecified order.

Next: Association Lists and Property Lists