CS 3723  Programming Languages
mapcar and apply

[Don't miss the Cool Formula at the end of this discussion.]

Lisp has special types of functions that transform and expand the meaning of other functions. The most common of these is mapcar. Consider

(mapcar 'f 'list1 'list2 ... 'listn)

where f is a function and list1, list2, ..., listn are lists. The result of this is to make up a new list that looks like:

( (f (car   'list1) (car   'list2) ... (car   'listn) )
  (f (cadr  'list1) (cadr  'list2) ... (cadr  'listn) )
  (f (caddr 'list1) (caddr 'list2) ... (caddr 'listn) )
  ...
  (f (last  'list1) (last  'list2) ... (last  'listn) )  )

Here is the same thing in the notation we haven't been using, namely first = car, second = cadr, third = cadddr, ....

( (f (first   'list1) (first   'list2) ... (first   'listn) )
  (f (second  'list1) (second  'list2) ... (second  'listn) )
  (f (third   'list1) (third   'list2) ... (third   'listn) )
  ...
  (f (last    'list1) (last    'list2) ... (last    'listn) )  )

Thus

> (mapcar '1+ '(1 3 5 7))
(2 4 6 8)
> (mapcar '+ '(2 4 6 8) '(10 30 50 70))
(12 34 56 78)
> mapcar 'equal '(3 "egg" (a b) 47  (b (d)) 'neal 3.14)
                '(4 "egg" (a c) 47  (b (d)) 'neal 3.14159))
(NIL T NIL T T T NIL)
;;;;;; which is:(NIL T    NIL   T   T        T    NIL)

Similarly, (apply 'f '(s1 s2 ... sn)) becomes (f 's1 's2 ... 'sn) so that one has:

> (apply '+ '(2 4 6 8))
20
> (apply '* '(1 2 3 4 5))
120
> (apply 'list '(a b c d))
(A B C D)

Check out the following transpose function for matrices. This code shows some of the real power of Lisp and of functional programming. A transpose function in a traditional language is much more complicated.

First define some matrices in Lisp:

> (setq mat0 '((a b) (c d)))
((A B) (C D))

> (setq mat '((a b c) (d e f) (g h i)))
((A B C) (D E F) (G H I))

> (setq mat2 '((a11 a12 a13 a14) (a21 a22 a23 a24)
             (a31 a32 a33 a34) (a41 a42 a43 a44)))
((A11 A12 A13 A14) (A21 A22 A23 A24) (A31 A32 A33 A34) (A41 A42 A43 A44))
> (setq mat3 '((b11 b12) (b21 b22)
             (b31 b32) (b41 b42) (b51 b52)))
((B11 B12) (B21 B22) (B31 B32) (B41 B42) (B51 B52))

Here is how one might define a transpose in a traditional way:

(defun make-car-list (l)
   (cond ((null l) nil)
         (t (cons (caar l) (make-car-list (cdr l)))) ))

(defun drop-cars (l)
   (cond ((null l) nil)
         (t (cons (cdar l) (drop-cars (cdr l)))) ))

(defun transpose (l)
   (cond ((null (car l)) nil)
         (t (cons (make-car-list l) (transpose (drop-cars l)))) ))

However, the two "helper" functions can be defined in a simpler way using mapcar:

(defun make-car-list (l)
    (mapcar 'car l))

(defun drop-cars (l)
    (mapcar 'cdr l))

Substituting these into the definition for transpose produces the following elegant version:

> (defun transpose (l)
   (cond ((null (car l)) nil)
         (t (cons (mapcar 'car l) (transpose (mapcar 'cdr l)))) ))
TRANSPOSE
> (transpose '((a b c) (d e f) (g h i))) ;; 3-by-3
((A D G) (B E H) (C F I))
> (transpose '((A D G) (B E H) (C F I)))
((A B C) (D E F) (G H I))
> (transpose (transpose '((a b c) (d e f) (g h i))))
((A B C) (D E F) (G H I))
> (transpose '((b11 b12) (b21 b22) (b31 b32) (b41 b42) (b51 b52))) ;; 5-by-2
((B11 B21 B31 B41 B51) (B12 B22 B32 B42 B52))
> (transpose '((b11 b21 b31 b41 b51) (b12 b22 b32 b42 b52))) ;; 2-by-5
((B11 B12) (B21 B22) (B31 B32) (B41 B42) (B51 B52))
> (transpose (transpose '((b11 b12) (b21 b22) (b31 b32) (b41 b42) (b51 b52))))
((B11 B12) (B21 B22) (B31 B32) (B41 B42) (B51 B52))

> (transpose mat0)
((A C) (B D))
> (transpose mat)
((A D G) (B E H) (C F I))
> (transpose mat2)
((A11 A21 A31 A41) (A12 A22 A32 A42) (A13 A23 A33 A43) (A14 A24 A34 A44))
> (transpose (transpose mat))
((A B C) (D E F) (G H I))
> (transpose (transpose mat2))
((A11 A12 A13 A14) (A21 A22 A23 A24) (A31 A32 A33 A34) (A41 A42 A43 A44))
> (transpose mat3)
((B11 B21 B31 B41 B51) (B12 B22 B32 B42 B52))
> (transpose (transpose mat3))
((B11 B12) (B21 B22) (B31 B32) (B41 B42) (B51 B52))
> (transpose '((a) (b)))
((A B))

A "functional programming style" refers to the use of mathematical functions for programming, without assignments and explicit iteration. Partly, one is trying to deal with objects as a unit.

Consider the Lisp code for a transpose constrasted with a Java implementation of transpose.

Transpose in Lisp
(defun transpose (l) (cond ((null (car l)) nil) (t (cons (mapcar 'car l) (transpose (mapcar 'cdr l)))) ))
Transpose in Java
// transpose: obvious algorithm int[][] transpose(int[][] x) { int[][] r = new int[x[0].length][x.length]; for (int i = 0; i < x.length; i++) for (int j = 0; j < x[i].length; j++) r[j][i] = x[i][j]; return r; }

A complete Java program illustrating the Java transpose is here: Transpose.

The important thing to notice is that the Lisp program works on the matix as a whole. It does not refer to the dimensions; it does not have any indexes through matrix elements; it does not reference individual matrix elements.

Mr. J. Hong (a student in our class) showed me a much simpler way to implement a transpose in Lisp. He said that mapcar itself sort of arranges things like a transpose, and in fact, you can use mapcar of list to make lists of the rows of the transposed matrix:

(mapcar 'list 'row1 'row2 ... 'lastrow)

or more specifically:

> (setq mat '((a b c) (d e f) (g h i)))
((A B C) (D E F) (G H I))
> (mapcar 'list '(A B C) '(D E F) '(G H I))
((A D G) (B E H) (C F I))

One can achieve the inner part of this with cons:

> (cons 'list mat)
(LIST (A B C) (D E F) (G H I))

Then tack mapcar on the front with apply:

> (apply 'mapcar (cons 'list mat))
((A D G) (B E H) (C F I))

Finally make this into a function:

> (defun transpose(m)
   (apply 'mapcar (cons 'list m)))
TRANSPOSE
> (transpose mat)
((A D G) (B E H) (C F I))

Pretty cool!