=========
== gty ==
=========
You gotta go away to come back.

Common Lisp 中的 'map'

lisp

In many programming languages, map is the name of a higher-order function that applies a given function to each element of a list, returning a list of results in the same order. It is often called apply-to-all when considered in functional form. The concept of a map is not limited to lists: it works for sequential containers, tree-like containers, or even abstract containers such as futures and promises. —— Wikipedia1

Scheme 中的 map

map 在 Lisp 语言中是一个经典的操作符。在包括《计算机程序的构造与解释》的诸多教材里,map 都作为一个使用高阶函数的经典范例。我们首先考察,在“短小精悍”的 Scheme 语言中,map 的“签名”与使用方法如下:

;;; procedure: (map procedure list1 list2 ...)
;;; returns: list of results
(map abs '(1 -2 3 -4 5 -6)) ;; => (1 2 3 4 5 6)
(map + '(1 2 3) '(3 2 1)) ;; => (4 4 4)

map 的作用在此很明了:对于列表中的每个元素应用一遍绝对值函数abs,然后返回一个由结果组成的列表。那么这个返回的列表和作为参数的列表之间有没有关系呢?

(define lst-1 (list 1 -2 3 -4 5 -6))
(define lst-2 (map abs lst-1))
lst-2 ;; => (1 2 3 4 5 6)
(eq? lst-1 lst-2) ;; => #f
(set-car! lst-1 -1000)
lst-1 ;; => (-1000 -2 3 -4 5 -6)
lst-2 ;; => (1 2 3 4 5 6)

可以看到,map 并不会带来所谓的“副作用”;也就是说,map 不会肆意造成任何 mutationmap 所映射出来的列表完全是一个新的列表。事实上,map 完全可以由下面几行代码所实现2

;;; am example implementation of `map` in Scheme
(define map
  (lambda (f ls . more)
    (if (null? more)
        (let map1 ([ls ls])
          (if (null? ls)
              '()
              (cons (f (car ls))
                    (map1 (cdr ls)))))
        (let map-more ([ls ls] [more more])
          (if (null? ls)
              '()
              (cons
               (apply f (car ls) (map car more))
               (map-more (cdr ls) (map cdr more))))))))

也许有人会说,map 这种没有“副作用”的机制是否也会随之带来较大的开销。这种担忧的确是值得考量的。**在我的理解中,函数式编程的代价即在于此:在效率上的牺牲并不代表我们要鼓吹“消除副作用”、“消除 mutation”;函数式的真正意义在于帮助程序员更好的带来我们想要的“副作用”、“mutation”,哪怕牺牲一些性能。**如果一个程序在运行之后什么也没有改变,那还有什么意义呢?

在这个问题上,“麻雀虽小五脏俱全”的 Scheme 提供了一个 for-each 函数:

;;; procedure: (for-each procedure list1 list2 ...)
;;; returns: unspecified
(for-each display '(1 2 3)) ;; => (屏幕上输出)123

for-each 的实现3较之 map 则显得更简洁一些:

;;; am example implementation of `for-each` in Scheme
(define for-each
  (lambda (f ls . more)
    (do ([ls ls (cdr ls)] [more more (map cdr more)])
        ((null? ls))
      (apply f (car ls) (map car more)))))

Common Lisp 中的 map

Common Lisp 虽然在设计方面受到 Scheme 的诸多影响,但是作为一门野心勃勃的、试图涵盖与统一所有 Lisp 方言的语言,Common Lisp 中和 map 有关的函数多达 9 个4

  1. map
  2. map-into
  3. mapcar
  4. mapc
  5. maplist
  6. mapl
  7. mapcan
  8. mapcon
  9. maphash

接下来,我们按照上面列出的顺序逐个考察。首先给出其语法和示例用法,接着作出比较与讨论。

map

;;; Function MAP
;;; Syntax:
;;; map result-type function &rest sequences+ => result
(map 'list #'abs '(1 -2 3 -4 5 -6)) ;; => (1 2 3 4 5 6)
(map 'vector #'abs '(1 -2 3 -4 5 -6)) ;; => #(1 2 3 4 5 6)
(map 'vector #'char-code "abcdefg") ;; => #(97 98 99 100 101 102 103)
(map 'string #'code-char #(97 98 99 100 101 102 103)) ;; => "abcdefg"

这个 map 和 Scheme 中的 map 颇为相似。但是,第一个参数在此为返回类型,并且这个类型必须是序列(Sequence)的子类型;第二个参数才是映射函数,并且其参数的个数与接下来所提供的序列的个数应当一致。也就是说,这个 map 既可以用来映射列表,也可以用来映射数组。Common Lisp 语言本身在设计上的正交性在此也有所体现了。

值得注意的是,当第一个参数为 nil 的时候,map 便可以“模拟” Scheme 中 for-each 的行为:

;;; map returns nil if result-type is nil,
;;; which means no result sequence is to be produced;
;;; in this case the function is invoked only for effect.
(map nil #'prin1 '(1 2 3)) ;; => 屏幕上输出 123,返回 NIL

最后要指出的是,在这里,各序列的长度不一定要完全一致,map 会以长度最短的序列为基准。我们姑且称之为“最短法则”。也就是说,如果参数中第一个序列长度为 10,第二个为 8,那么 map 在映射到各序列中第八个元素后就停止工作了:

;;; when length of sequences is not the same ...
(map 'vector #'* '(1 2 3 4 5 6 7 8 9 10)
                 #(1 2 3 4 5 6 7 8))
;; => #(1 4 9 16 25 36 49 64)

更多信息请阅读 CLtL2 以及 HyperSpec 中的相关内容。

map-into

;;; Function MAP-INTO
;;; Syntax:
;;; map-into result-sequence function &rest sequences => result-sequence
(defvar *lst* (list 1 -2 3 -4 5 -6))
(map-into *lst* #'abs *lst*) ;; => (1 2 3 4 5 6)
*lst* ;; => (1 2 3 4 5 6)
(map-into *lst* #'* *lst* *lst*) ;; => (1 4 9 16 25 36)
*lst* ;; => (1 4 9 16 25 36)

map-intomap 很类似,并且都是可以在任意序列对象上操作的函数。但其区别在于,map-into 永远都会改变一个现有序列的状态,而不是像 map 一样会生成一个新的序列。HyperSpec 上有一小段代码可以作为 map-into 的实现方式:

;;; an example implementation of map-into
(defun map-into (result-sequence function &rest sequences)
  (loop for index below (apply #'min
                               (length result-sequence)
                               (mapcar #'length sequences))
     do (setf (elt result-sequence index)
              (apply function
                     (mapcar #'(lambda (seq) (elt seq index))
                             sequences))))
     result-sequence)

由此可见,

  • 使用 map-into 的目的主要就在于其带来的“副作用”;
  • map-into 的“迭代”次数取决于 result-sequence 和所有 sequences 中长度最小的,也就是说,如果最小长度是 n,那么在映射完第 n 次之后,map-into 就会停止工作。

另外要注意的是,如果 result-sequence 是一个拥有填充指针(Fill Pointer)的向量(Vector),那么 map-into 在工作时并不会考虑这个填充指针的大小;而在映射完成后,这个填充指针会被重新设置成映射函数被调用的次数:

;;; CLtL2:
;;; If result-sequence is a vector with a fill pointer,
;;; the fill pointer is ignored when deciding how many iterations to perform,
;;; and afterwards the fill pointer is set to the number of times function was applied.
(defvar *vector* (make-array 5 :initial-element 0 :fill-pointer 2))
*vector* ;; => #(0 0)
(length *vector*) ;; => 2
(array-total-size *vector*) ;; => 5
(fill-pointer *vector*) ;; => 2
(map-into *vector* #'* '(1 2 3 4) #(1 2 3 4 5)) ;; => #(1 4 9 16)
(fill-pointer *vector*) ;; => 4

在这里也许有人就会发现了,*vector* 在初始化长度明明是 2,按照“最短法则”,map-into不应该迭代两次就停止工作了吗?让我们再来看一下语言标准 CLtL2 中的原文:

If result-sequence and the other argument sequences are not all the same length, the iteration terminates when the shortest sequence is exhausted. – Section 14.2, CLtL2.

所以,虽然 *vector* 的长度一开始为 2,但是在映射完第二个元素后,*vector* 并没有 exhausted5。上文中,HyperSpec 所给出的实现并未能很好体现这一点,故在此特别指明。更多信息请阅读 HyperSpecCltL2 中的相关内容。

mapcar

;;; Function MAPCAR
;;; Syntax:
;;; mapcar function &rest lists+ => result-list
(mapcar #'abs '(1 -2 3 -4 5 -6)) ;; => (1 2 3 4 5 6)
(mapcar #'* '(1 2 3) '(1 2 3)) ;; => (1 4 9)
(mapcar #'* '(1 2 3 4 5) '(1 2 3)) ;; => (1 4 9)

mapcar 只能操作于列表之上,所以它的行为和 Scheme 中的 map 完全类似。更多信息请阅读 HyperSpecCltL2 中的相关内容。

mapc

;;; Function MAPC
;;; Syntax:
;;; mapc function &rest lists+ => list-1
(mapc #'prin1 '(1 2 3)) ;; => 屏幕上输出 123,返回 (1 2 3)
(mapc #'+ '(1 2 3) '(3 2 1)) ;; => (1 2 3)

mapc 只能操作于列表之上,且其行为几乎和 Scheme 的 for-each 一致,于是也和第一个参数为 nil 时的 map 类似。但不同的是,mapc 永远都会返回第一个列表的值,这也意味着 mapc 至少要接受三个参数。更多信息请阅读 HyperSpecCLtL2 中的相关内容。

maplist

;;; Function MAPLIST
;;; Syntax:
;;; maplist function &rest lists+ => result-list
(maplist #'append '(1 2 3 4) '(1 2 3) '(1 2))
;; => ((1 2 3 4 1 2 3 1 2) (2 3 4 2 3 2))

maplist 只能操作于列表,理解它的关键在于,每一次映射函数得到的参数先是列表(们)本身,接着是列表(们)的 cdr,再接着是列表(们) cdrcdr,直至在列表(们)碰到第一个 nilmaplist 停止工作。在此,我们不妨拥 Scheme 来做一个演示:

;;; an example implementation of maplist in Scheme(define maplist(lambda (f lst . more)(if (null? more)(let map1 ([lst lst])(if (null? lst)'()(cons (f lst)(map1 (cdr lst)))))(let map-more ([lst lst][more more])(if (null? lst)'()(if (member '() more)'()(cons (apply f lst more)(map-more (cdr lst) (map cdr more)))))))))

更多信息请阅读 HyperSpecCLtL2 中的相关内容。

mapl

;;; Function MAPL
;;; Syntax:
;;; mapl function &rest lists+ => list-1
(defvar *lst* nil)
(mapl #'(lambda (x) (push x *lst*)) '(1 2 3 4)) ;; => (1 2 3 4)
*lst* ;; => ((4) (3 4) (2 3 4) (1 2 3 4))

mapl 只能操作于列表之上,其行为和 maplist 类似,但是 mapl 并不会把每次的映射结果收集到一个新列表里,反而只会返回参数 lists 中的第一个列表。可以猜到的是,这个函数是为“副作用”而准备的。更多信息请阅读 HyperSpecCLtL2 中的相关内容。

mapcan

;;; Function MAPCAN
;;; Syntax:
;;; mapcan function &rest lists+ => concatenated-results
(mapcan #'(lambda (x) (and (numberp x) (list x)))
        '(a 1 b c 3 4 d 5))
;;; => (1 3 4 5)
(mapcar #'(lambda (x) (and (numberp x) (list x)))
        '(a 1 b c 3 4 d 5))
;;; => (NIL (1) NIL NIL (3) (4) NIL (5))
(apply #'nconc '(NIL (1) NIL NIL (3) (4) NIL (5))) ;; => (1 3 4 5)

mapcan 只能操作于列表之上。简单来说,mapcan 是把 mapcar 的结果应用于 nconc 后的返回值:

(defun mapcan (function list &rest more-lists)
  (apply #'nconc
         (apply #'mapcar function list more-lists)))

由于使用了 nconc 函数,mapcan 也随之带来了副作用。更多信息请阅读 HyperSpecCLtL2 中的相关内容。

mapcon

;;; Function MAPCON
;;; Syntax:
;;; mapcon function &rest lists+ => concatenated-results
(mapcon #'list (list 1 2 3 4))
;; => ((1 2 3 4) (2 3 4) (3 4) (4))

mapcon 同样也只能操作于列表之上,类似的,mapcan 是把 maplist 的结果应用于 nconc 后的返回值:

(defun mapcon (function list &rest more-lists)
  (apply #'nconc
         (apply #'maplist list more-lists)))

同样的,由于使用了 nconc 函数,mapcon 也随之带来了副作用。更多信息请阅读 HyperSpecCLtL2 中的相关内容。

maphash

;;; Function MAPHASH
;;; Syntax:
;;; maphash function hash-table => nil
(defvar *lst* '(a b c d e f g))
(defvar *table* (make-hash-table))
(dolist (sym *lst*)
  (setf (gethash sym *table*) (symbol-name sym)))
(maphash #'(lambda (k v) (format t "~A => ~S~%" k v))
         *table*)
;;; 屏幕输出:
;;; A => "A"
;;; B => "B"
;;; C => "C"
;;; D => "D"
;;; E => "E"
;;; F => "F"
;;; G => "G"
;;; 返回: NIL

maphash 是专门用来操作哈希表的函数。其第一个参数必定为一个双参函数,在每一次映射中,这个函数接受一对键值,并完成一次映射。对于这个映射函数所带来的潜在的副作用,语言规范中特别强调:

If entries are added to or deleted from the hash table while a maphash is in progress, the results are unpredictable, with one exception: if the function calls remhash to remove the entry currently being processed by the function, or performs a setf of gethash on that entry to change the associated value, then those operations will have the intended effect. For example: ;;; Alter every entry in MY-HASH-TABLE, replacing the value with ;;; its square root. Entries with negative values are removed. (maphash #'(lambda (key val) (if (minusp val) (remhash key my-hash-table) (setf (gethash key my-hash-table) (sqrt val)))) my-hash-table) – Section 16.1, CLtL2

也就是说,移除一对键值,或者修改当前键所对应的值是可以的,而其他的行为则就是未规范的了。值得一提的是,其实对于哈希表的迭代,Common Lisp 提供了更通用的 with-hash-table-iterator,以至于 maphash 其实可以基于它来实现:

;;; Macro WITH-HASH-TABLE-ITERATOR
;;; Syntax:
;;; with-hash-table-iterator (name hash-table) declaration* form* => result*
(defun maphash (function hash-table)
  (with-hash-table-iterator (next-entry hash-table)
    (loop (multiple-value-bind (more key value) (next-entry)
            (unless more (return nil))
            (funcall function key value)))))

更多相关信息请阅读 HyperSpecCLtL2 中的相关内容。

总结

下面,我们从两个维度来观察这 9 个函数,并以此收结束本文。

操作对象

操作对象函数名
哈希表maphash
列表mapcar, maplist, mapc, mapl, mapcan, mapcon
序列map, map-into

请注意,“列表”是“序列”的子类型,因此 mapmap-into 具有更高的通用性(General)。

副作用

**首先需要说明,这里的“副作用”指的是这个函数到底是为了得到返回值,还是为了带来“副作用”。**换句话说,映射函数 function 可以尽管带来 mutation,但那极有可能是一种不良的编码风格;可在使用例如 mapc 的函数时,如果映射函数不带有任何“副作用”,那么它只会返回一个和参数一模一样的列表,这样的意义何在呢?

函数名注解
map当第一个参数为 nil 时,可以认为目的是带来“副作用”
map-into总是会修改一个现有序列的状态,有副作用
mapcar无副作用
mapc类似 Scheme 中的 for-each,有副作用
maplist无副作用
mapl原因类似 mapc,有副作用
mapcan可视为 mapcar 的延展,我们更想得到返回值,故认为无副作用6
mapcon可视为 maplist 的延展,我们更想得到返回值,故认为无副作用
maphash语言标准中只规范了两种可行的副作用,在此不特地做区分

所以,我的个人结论是:

区分函数名
为了带来副作用的函数mapc, mapl, map-into, 以及第一个参数为 nil 的 map
无副作用的函数mapcar, maplist, mapcan, mapcon, 以及第一个参数不为 nil 的 map
只能带来特定的副作用maphash

之所以要以“目的”来对“副作用”的含义进行说明,是希望在此能帮助读者更好的理解这些 map 操作符,理解语言设计者的用意。虽说“仁者见仁,智者见智”,但是我们还是希望在 Common Lisp 的编码风格上有着一定的规范,尤其是建议不要乱用、滥用这些操作符到不恰当的地方。


  1. 参见 Wikipedia, https://en.wikipedia.org/wiki/Map_(higher-order_function) ↩︎

  2. 参见 Section 5.5 Mapping and Folding, The Scheme Programming Language 4th Edition, R. Kent Dybvig. ↩︎

  3. 同样参见 Section 5.5 Mapping and Folding, The Scheme Programming Language 4th Edition, R. Kent Dybvig. ↩︎

  4. 这样的说法不算很严谨。毕竟,Scheme 中的 map 只能操作列表,而这里列出的这9个则能操作包括列表、数组,甚至哈希表。所以,这里“有关”的含义仅仅是名字里或者概念上和 map “有关”。 ↩︎

  5. 尽管如此,关于什么才是 exhausted,CLtL2 并没有做出定义。想在这个问题上探个究竟的朋友请参考 SBCL 中的相关代码,此处不做展开了。 ↩︎

  6. 基于上文对“副作用”的界定,这样的区分是有道理的。但是仍需注意的是,mapcan 以及接下来的 mapcon 都使用了破坏性函数 nconc,所以 mapcanmapcon 也是有破坏性的。引用 CLtL2 中的话来说就是:“Remember that nconc is a destructive operation, and therefore so are mapcan and mapcon; the lists returned by the function are altered in order to concatenate them.” ↩︎