在 Lisp 中对树使用 reduce

Question

要在 Lisp 中折叠平面列表，可以使用reduce：

* (reduce #'+ '(1 2 3 4 5))
15

但是，如果我有一个任意复杂的树，并且我想对每个元素应用一个函数，该怎么办？那么折叠'(1 (2) (3 (4) 5))仍然会给出15？我尝试使用reduce，但我必须提供一个自定义函数，这有点违背了目的：

(defun tree+ (a b)
  (cond ((null b) 0)
        ((atom b) (+ a b))
        (t (+ (tree+ a (car b))
              (tree+ 0 (cdr b))))))

(reduce #'tree+ '(1 (2) (3 (4) 5)) :initial-value 0) ; returns 15

当然，我可以先展平列表，但这reduce是一个通用函数，有时您必须保留原始序列的结构和顺序。例如，map和filter可以用 来实现reduce。如果我想my-map基于编写 的实现reduce，那么：

(my-map '1+ '(1 (2 (3) 4) 5)) ; outputs '(2 (3 (4) 5) 6)

如何使用reduce树形结构？在树上应用二元函数的最通用方法是什么？

Answer 1

我在Counting elements of a list and sublists中提供了一个treeduce函数的实现，虽然它是针对Scheme的，但同样的原则也适用于这里。维基百科在Fold （高阶函数）中说：

\n\n

\n

在函数式编程中，折叠 \xe2\x80\x93 也称为缩减、\n 累积、聚合、压缩或注入 \xe2\x80\x93 是指分析递归数据结构的一系列高阶函数并通过使用给定的组合操作重新组合递归处理其组成部分的结果，构建返回值。通常，折叠带有组合函数、数据结构的顶部节点以及在某些条件下可能使用的一些默认值。然后，折叠继续以系统的方式使用该函数来组合数据结构层次结构的元素。

\n

\n\n

列表数据结构可以描述为代数数据类型：

\n\n

List ::= Cons(Object, List)\n       | Nil\n

\n\n

当我们用一个列表函数调用reduce时，我们本质上是把每次使用都变成Cons了该函数的一个应用程序，并且每次使用都Nil带有一些常量值。也就是说，我们将列表

\n\n

Cons(x,Cons(y,Cons(z,Nil)))\n

\n\n

并将其变成

\n\n

Fn(x,Fn(y,Fn(z,init)))\n

\n\n

或者，您可以将Nil和init作为零参数函数，在这种情况下，列表将变成

\n\n

Fn(x,Fn(y,Fn(z,init())))\n

\n\n

对于树，我们可以做同样的事情，但是稍微复杂一些。对于树，代数数据类型是：

\n\n

Tree ::= Node(Tree,Tree)\n       | Leaf(Object)\n

\n\n

为了对一棵树进行归约，我们需要两个函数：一个用于替换Node，一个用于替换Leaf。不过，定义非常简单：

\n\n

TreeReduce(nodeFn,leafFn,tree) =\n  case tree of \n    Node(left,right) => nodeFn(TreeReduce(nodeFn,leafFn,left),TreeReduce(nodeFn,leafFn,right)\n    Leaf(object) => leafFn(object)\n

\n\n

在 Common Lisp 中，这很简单：

\n\n

(defun tree-reduce (node-fn leaf-fn tree)\n  (if (consp tree)\n      (funcall node-fn \n               (tree-reduce node-fn leaf-fn (car tree))\n               (tree-reduce node-fn leaf-fn (cdr tree)))\n      (funcall leaf-fn \n               tree)))\n

\n\n\n\n

(tree-reduce \'cons\n             (lambda (x) \n               (if (numberp x) (1+ x) x))\n             \'(1 (2 3) (4 5 6)))\n;=> (2 (3 4) (5 6 7))\n

\n\n

我们可以使用tree-reduce来计算您询问的总和：

\n\n

(tree-reduce \'+\n             (lambda (x)\n               (if (null x) 0 x))\n             \'(1 (2) (3 (4) 5)))\n;=> 15\n

\n\n

我们需要所有这些null保护的原因是，当我们将基于 cons 的结构视为树时，nil并不是什么特别的。也就是说，我们可以考虑树 (1 (2 . 3) 4 . 5) 以及 (1 (2 3) 4 (5)) （与 (1 (2 3 . nil) 4 (5) 相同） .nil).nil)，当然）。

\n