cyfdecyf’s blog

看 Why functional programming matters 时看到它给出的 reduce 与 common lisp 中提供的 reduce 不同。

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

(cons e (cons e (cons e ( ... (cons e nil)))))

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

(add e (add e (add e ( ... (add e 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 不实现成这样？一番搜索之后发现了这个操作通常称为 fold，Wikipedia 上 fold 条目 对这个操作有详细的解释。

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

在 Common Lisp 中可以这样实现 right fold：

(defun foldr (func nil-value list)
  (if (null list)
      nil-value
      (funcall
       func
       (car list)
       (foldr func nil-value (cdr list)))))

当然还有其他一些区别限制了实际使用中是应该选择 left fold 还是 right fold，但是我想 Common Lisp 的 reduce 实现成 left fold 的一点原因是 reduce 不光作用在 list 上，它还可以作用在 vector 上，而 vector 没有 list 末尾的 nil，如果要实现作用在 vector 上的 right fold 则算法需要做出调整，而且很难做到对 vector 和 list，reduce 的行为完全一致。这只是我的猜想。