看 Why functional programming matters（非常推荐这篇论文。） 时看到它给出的 reduce 与 common lisp 中提供的 reduce 不同。

这篇论文里面的 reduce 作用是这样的，对一个 list

(cons e1 (cons e2 (cons e3 ( ... (cons en nil)))))

reduce 接受两个参数，一个是接受两个参数的函数，把这个函数去替换 list 中所有的 cons 函数；另一个参数则替换 nil。举例来说，如果这样调用 (reduce add 0 list)，则产生的效果是

(add e1 (add e2 (add e3 ( ... (add en 0)))))

也就是对 list 中的元素进行了求和。

这个 reduce 非常强大，可以用它方便的写出 append, map 等函数。(append a b) 即 (reduce cons b a)，(map func list) 即

(defun map (fun list)
  (foldr
   (lambda (a b)
     (cons (funcall fun a) b))
   nil
   list))

因为 Common Lisp 中没有函数组合操作符，所以这个 map 没有在论文使用的语言 Miranda 那么优雅。

Common Lisp 中的 reduce 与上面描述的不太一样，初值要通过 key 参数 :initial-value 指定，写成这样 (reduce #‘add list :initial-value 0)，而且它的默认行为也不太一样。一番搜索之后发现了这个操作通常称为 fold，Wikipedia 上 fold 条目 对这个操作有详细的解释，而且解释 fold 操作的两张图片也很直观。

fold 操作最方便的地方是使得一个原本只接受有限个参数的函数能够作用在元素个数不定的 list 上。

fold 操作分两种，上面说的那种被称为 right fold，而 Common Lisp 中的 reduce 默认是 left fold，C++ 中的 accumulate，Ruby 中的 inject 都是 left fold。Common Lisp 中的 reduce 加上 key 参数 :from-end t 以后其行为就跟 right fold 相同了。Paul Graham 的 Ansi Common Lisp 的 Appendix D 中对 reduce 的说明也很清楚，下面的例子就参考了他的说明。

对最开始的 list 例子用 left fold 操作以后的效果如下：

(add (add (add ( ... (add 0 e1) e2) e3) ... ) en)

简单来说，left fold 也接受两个参数，一个是接受两个参数的函数，另一个是初值。left fold 将初值和 list 中的第一个元素传给函数，然后将函数返回值和第二个 list 元素传给函数，一直这样下去直到 list 的最后一个元素 nil 之前。left fold 也可以轻易的实现求和等操作，当然对于不满足交换率的操作使用 left fold 和 right fold 得到的结果是不同的。但是要实现 append, map 这样的操作就无能为力了（可能也可以，但肯定很麻烦吧）。

Ansi Common Lisp 第 4 掌的第 2 条习题就是用 reduce 来实现 copy-list 和 reverse，只针对 list，不考虑 array。实现如下，

(defun copy-list (lst)
  (reduce #'cons  lst :from-end t :initial-value nil))

(defun reverse (lst)
  (reduce #'(lambda (a b) (cons b a)) lst :initial-value nil))

第一个用的是 right fold，非常直观，用 cons 替代原来 list 里面的 cons 就可以了，第二个用了 left fold，匿名函数只是交互了一下 cons 的两个参数而已，看下 right fold 的针对 add 的那个例子就很容易明白了。