在 Lisp 中对树使用 reduce [英] Using reduce over a tree in Lisp

问题描述

要在 Lisp 中折叠平面列表，请使用 reduce:

To fold a flat list in Lisp you use reduce:

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

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

But what if I have an arbitrarily complex tree, and I want to apply a function over each of the element? So that fold over '(1 (2) (3 (4) 5)) would still give 15? I tried to use reduce, but I had to provide a custom function, which kinda defeats the purpose:

(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 的实现，那么:

Of course I could flatten the list first, but reduce is a general function, sometimes you must preserve the structure and order of the original sequence. For example, map and filter can be implemented with reduce. What if I wanted to write an implementation of my-map, based on reduce, so that:

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

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

How to use reduce over a tree structure? What is the most generic way to apply a binary function over a tree?

推荐答案

我在 计算列表和子列表的元素，虽然是针对 Scheme，但同样的原则也适用于此.维基百科在 折叠(高阶函数) 中说:

I've provided an implementation of a treeduce function in Counting elements of a list and sublists, and although it's for Scheme, the same principles apply here. Wikipedia, in the Fold (higher-order function), says:

在函数式编程中，折叠 – 也称为减少，累积、聚合、压缩或注入——指的是分析递归数据结构的高阶函数和通过使用给定的组合操作重新组合递归处理其组成部分，建立一个回报价值.通常，折叠具有组合功能，顶部数据结构的节点，可能还有一些要使用的默认值在一定条件下.然后折叠继续组合元素数据结构的层次结构，系统地使用函数方式.

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.

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

The list data structure can be described as an algebraic datatype:

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

当我们用一个列表函数调用reduce时，我们实质上是将Cons的每次使用转化为该函数的一个应用，而Nil的每次使用都带有一些恒定值.也就是我们取列表

When we call reduce with a function a list, we're essentially turning each use of Cons into an application of the function, and each use of Nil with some constant value. That is, we take the list

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

然后把它变成

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

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

Alternatively, you can imagine Nil and init as as a zero-argument functions, in which case the list is turned into

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

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

For trees, we can do the same thing, but it's a little bit more complex. For a tree, the algebraic datatype is:

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

为了对一棵树进行reduce，我们需要两个函数:一个替换Node，一个替换Leaf.不过，定义非常简单:

To do a reduce for a tree, then, we need two functions: one to replace Node and one to replace Leaf. The definition is pretty straightforward, though:

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 中，这很简单:

In Common Lisp, that's simply:

(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 来计算您询问的总和:

We can use tree-reduce to compute the sum that you asked about:

(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).nil) .nil)，当然).

The reason that we need all of these null guards is that when we're viewing a cons-based structure as a tree, nil isn't really anything special. That is, we could consider the tree (1 (2 . 3) 4 . 5) as well as (1 (2 3) 4 (5)) (which is the same as (1 (2 3 . nil) 4 (5 . nil) . nil), of course).

这篇关于在 Lisp 中对树使用 reduce的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！