Iteration and Mapping

<-Previous | ^UP^ | Next->

Common Lisp provides a number of iteration and mapping macros and functions which enable us to process the contents of lists, the most commonly used being

  • Iteration - the macros dolist and dotimes
  • Mapping - the functions mapcar, mapcan and mapc
Common Lisp also defines 2 powerful and more general iteration macros, do/do* and loop, but they are outside the scope of this tutorial

Iteration Macros

  • dolist - takes a list of a variable and an expression which returns a list, followed by a body of expressions. Optionally dolist can take a third element for its list, which is an expression which will be evaluated and its value returned from the dolist expression once the dolist iteration has completed. The body of expressions is evaluated with the variable bound to successive elements in the list.
    The example on the right first sets a return variable res to nil. It then iterates through the list a, multiplying each value by 5 and pushing the result onto res. Finally res is returned from the dolist and set to b.
    If you wanted to return the resultant list values in the same order as they occur in the input list, you would need to wrap the dolist return value res in a call to the function reverse. But because res is locally bound and will never be used after b has been evaluated, you could use the destructive function nreverse, which is slightly more efficient than reverse
    • GDL-USER> (setq a (list 1 2 3 4 5 6))
    1 2 3 4 5 6)GDL-USER>  (setq b (let ((res nil))(dolist (var a res)(push (* var 5) res))))(30 25 20 15 10 5)GDL-USER>  (setq b (let ((res nil))(dolist (var a (nreverse res))(push (* var 5) res))))(5 10 15 20 25 30)

    It is also possible to use dolist without any return value argument, in which case you'd be relying on side-effecting within the body. The two examples shown are different ways of returning the length of a list

    GDL-USER>  (setq c (let ((len 0))(dolist (var a)(setf len (+ len 1)))len))6GDL-USER>  (setq c (let ((len 0))(dolist (var a)(incf len)len))6
  • dotimes - takes two required inputs, a variable and an integer, followed by a body of expressions. As with dolist, the list at the start of dotimes's argument list can optionally dotimes have a third element, an expression which will be evaluated and the resulting value returned once the dotimes has completed. The body of expressions are evaluated with the variable bound to successive integers between 0 and integer minus 1

    In contrast to dolist which is generally used to iterate through a single list, using dotimes with the function nth permits iteration on multiple lists

    The first example shows dotimes being used to splice together 2 lists. The second example is the first dolist example converted to a dotimes implementation

    • GDL-USER> (setq a (list 1 2 3 4 5))
    (1 2 3 4 5)
    GDL-USER> (setq b (list "a" "b" "c" "d" "e"))
    ("a" "b" "c" "d" "e")GDL-USER>  (let ((res nil))(dotimes (n (length a) (nreverse res))(push (nth n a) res)(push (nth n b) res)))(1 "a" 2 "b" 3 "c" 4 "d" 5 "e")GDL-USER>  (setq b (let ((res nil))(dotimes (n (length a) (nreverse res))(push (* (nth n a) 5) res))))))(5 10 15 20 25)

Mapping Functions

  • mapcar - one of the most heavily used mapping functions, it takes a function and one or more lists and calls the function on successive elements of the lists
    • GDL-USER>  (defun plus2(i)(+ i 2))PLUS2
    GDL-USER> (mapcar #'plus2 (list 1 2 3))
    (3 4 5)GDL-USER>  (defun list-product (a b)(* a b))LIST-PRODUCT
    GDL-USER> (mapcar #'list-product (list 1 2 3) (list 4 5 6))
    (4 10 18)

    mapcar is very commonly used with a lambda or anonymous function. This effectively allows functions to be defined on the fly and they can be used to map across multiple lists. The first example is an alternative to the dotimes example for splicing 2 lists together. Successive elements from the 2 input lists are bound to the lambda vailables x and y and the return value from the lambda expression appended to the return list. The second example replaces the LIST-PRODUCT function with a lambda function to achieve the same result

    mapcar can often be used to accomplish the same thing as dolist and may be less verbose. However, when the list processing becomes more complex dolist may have some advantage in clarity and debugging

    GDL-USER>  (flatten(mapcar#'(lambda(x y) (list x y))(list 1 2 3 4 5)(list "a" "b" "c" "d" "e")))(1 "a" 2 "b" 3 "c" 4 "d" 5 "e")
    GDL-USER> mapcar #'(lambda(x y) (* x y) (list 1 2 3) (list 4 5 6))
    (4 10 18)
  • mapcan - takes a function and one or more lists like mapcar but splices together the values returned by the function
    • GDL-USER> (mapcan #'list (list 1 2 3 4 5) (list "a" "b" "c" "d" "e"))
    (1 "a" 2 "b" 3 "c" 4 "d" 5 "e")
  • mapc is like mapcar but it doesn't accumulate any data to return so the only reason to use it is for side-effecting. mapc always returns is second argument (the first list provided). When only side-effecting is required mapc may be a better option than dolist because is can traverse multiple lists in parallel
    • GDL-USER>  (let ((x 0))(mapc #'(lambda(a) (setf x (+ x a))) (list 1 2 3))x)6GDL-USER>  (let ((x 0))(mapc #'(lambda(a b c) (setf x (+ x a b c)))(list 1 2 3) (list 4 5 6)(list 7 8 9))x)45