tree - 在 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 来实现。如果我想基于 reduce 编写 my-map 的实现，那么:

(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 (higher-order function) , 说:

In functional programming, fold – also known variously as reduce, accumulate, aggregate, compress, or inject – refers to a family of higher-order functions that analyze a recursive data structure and recombine through use of a given combining operation the results of recursively processing its constituent parts, building up a return value. Typically, a fold is presented with a combining function, a top node of a data structure, and possibly some default values to be used under certain conditions. The fold then proceeds to combine elements of the data structure's hierarchy, using the function in a systematic way.

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

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

当我们用一个函数调用 reduce 一个列表时，我们实质上是将 Cons 的每次使用都变成了函数的应用，而每次使用 Nil 都带有一些常数值。也就是我们取列表

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

然后把它变成

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

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

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

对于树，我们可以做同样的事情，但它有点复杂。对于树，代数数据类型是:

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

然后，要对一棵树进行归约，我们需要两个函数:一个替换Node，一个替换Leaf。不过，定义非常简单:

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

在 Common Lisp 中，这很简单:

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

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

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

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

我们需要所有这些 null 守卫的原因是，当我们将基于 cons 的结构视为一棵树时，nil 并不是什么特别的东西.也就是说，我们可以考虑树 (1 (2 . 3) 4 . 5) 以及 (1 (2 3) 4 (5))(与 (1 (2 3 . nil) 4 (5 . 无) . 无)，当然)。