代码之家 › 专栏 › 技术社区 › Wang

减少,还是显式递归?

lisp coding-style

Wang · 技术社区 · 15 年前

最近我和一个朋友开始读保罗·格雷厄姆的关于Lisp的文章,我们意识到我们对reduce有着非常不同的看法:我认为reduce非常清楚和简洁地表达了某种递归形式;他更喜欢非常明确地写出递归。

我怀疑我们在某些情况下是对的,在另一种情况下是错的,但我们不知道这条线在哪里。你什么时候选择一种形式而不是另一种形式,当你做出选择时你会怎么想?

为了清楚我所说的reduce与explicit递归的含义,这里有两次实现的相同函数:

(defun my-remove-if (pred lst)
    (fold (lambda (left right)
                  (if (funcall pred left) 
                      right 
                      (cons left right)))
          lst :from-end t))

(defun my-remove-if (pred lst)
    (if lst
        (if (funcall pred (car lst))
            (my-remove-if pred (cdr lst))
            (cons (car lst) (my-remove-if pred (cdr lst))))
        '()))

恐怕我开始是个阴谋家(现在我们是敲诈勒索者?)所以请告诉我,我是否搞错了常见的Lisp语法。希望即使代码不正确,这一点也会很清楚。

3 回复 | 直到 15 年前

Ira Baxter 15 年前

如果你有选择,你应该用最抽象的术语表达你的计算意图。这使读者更容易理解您的意图,并且使编译器更容易优化您的代码。在您的示例中,当编译器轻而易举地知道您通过命名它来执行折叠操作时,它也轻而易举地知道它可能并行于叶操作。当编写极低级别的操作时,编译器很难弄清楚这一点。

Rainer Joswig mmmmmm 15 年前

通常,与递归相比,Lisp更倾向于使用高阶函数进行数据结构遍历、筛选和其他相关操作。这也可以从许多提供的函数中看到,比如reduce、remove-if、map和其他函数。

tail递归是a)不受标准支持,b)可能使用不同的cl编译器以不同的方式调用,c)使用tail递归可能会对生成的周围代码的机器代码产生副作用。

通常,对于某些数据结构,上面的许多操作是通过循环或迭代实现的,并作为高阶函数提供。对于迭代代码,人们倾向于使用新的语言扩展(如循环和迭代),而不是使用递归进行迭代。

(defun my-remove-if (pred list)
   (loop for item in list
         unless (funcall pred item)
         collect item))

这里还有一个使用公共lisp函数reduce的版本:

(defun my-remove-if (pred list)
  (reduce (lambda (left right)
            (if (funcall pred left) 
                right 
              (cons left right)))
          list
          :from-end t
          :initial-value nil))

Ken 15 年前

我将回答一个稍微有点主观的问题,并给出一个高度主观的答案,因为爱尔兰共和军已经给出了一个非常实用和合乎逻辑的问题。-)

我知道,在某些圈子里,明确地写东西是很有价值的(Python的人把它作为“禅”的一部分),但即使是在我写Python的时候,我也从来没有理解过它。我想一直以最高的水平写作。当我想明确地写出东西时,我使用汇编语言。使用电脑(和HLL)的目的是让它为我做这些事情!

为了你 my-remove-if 例如,reduce对我来说很好(除了 fold 和 lst -)我熟悉reduce的概念,所以我只需要了解 f(x,y) -> z . 对于显式的变体,我必须考虑一下:我必须自己解决这个循环。递归不是最难的概念,但我认为它比“两个参数的函数”更难。

我也不喜欢整条线被重复-- (my-remove-if pred (cdr lst)) . 我觉得我喜欢口齿不清,部分原因是我绝对喜欢口齿不清。 无情的 在Dry,Lisp允许我在其他语言无法做到的轴上保持干燥。(你可以换一个 LET 在顶部是为了避免这种情况,但之后会变得更长和更复杂,我认为这是另一个更倾向于减少的原因,尽管在这一点上,我可能只是在合理化。)

我认为,在这种情况下,至少Python的人不喜欢隐式功能是:

当没有人能预料到这种行为(比如 frobnicate("hello, world", True) --真的是什么意思?),或:
当隐性行为改变是合理的时候(比如 True 因为在大多数动态语言中没有编译时错误,所以参数会被移动、删除或替换为其他内容)

但是 reduce 在Lisp中,这两个标准都失败了:这是一个众所周知的抽象,而且不会改变,至少在我关心的任何时间尺度上都不会改变。

现在,我完全相信是在某些情况下,我更容易阅读一个显式函数调用,但我认为您必须非常有创意才能想出它们。我现在想不出什么,因为 减少 和 mapcar 朋友们 真的很好 抽象。