在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是常规功能，有时您必须保留原始序列的结构和顺序.例如，可以使用reduce来实现map和filter.如果我想基于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?

推荐答案

我在折叠(高阶函数)中说:

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:

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

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)

要对树进行归约，我们需要两个函数:一个替换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屋！