13

编辑：我在写这篇文章的过程中发现了我自己问题的部分答案，但我认为它可以很容易地改进，所以无论如何我都会发布它。也许那里有更好的解决方案？

我正在寻找一种简单的方法来以一种let形式定义递归函数，而无需借助letfn. 这可能是一个不合理的要求，但我正在寻找这种技术的原因是因为我混合了数据和递归函数，这些函数在某种程度上需要大量的嵌套let和letfn语句。

我想编写生成这样的惰性序列的递归函数（以斐波那契序列为例）：

(let [fibs (lazy-cat [0 1] (map + fibs (rest fibs)))]
  (take 10 fibs))

但是在clojure中似乎fibs不能在绑定期间使用它自己的符号。解决它的明显方法是使用letfn

(letfn [(fibo [] (lazy-cat [0 1] (map + (fibo) (rest (fibo)))))]
  (take 10 (fibo)))

但是正如我之前所说，这会导致很多麻烦的嵌套和交替letand letfn.

为了在不letfn使用和使用 just的情况下做到这一点let，我首先编写了一些使用我认为是 U-combinator 的东西（今天刚刚听说过这个概念）：

(let [fibs (fn [fi] (lazy-cat [0 1] (map + (fi fi) (rest (fi fi)))))]
  (take 10 (fibs fibs)))

但是如何摆脱冗余(fi fi)呢？

正是在这一点上，经过一个小时的挣扎并逐渐向组合子 Q 添加位，我找到了自己问题的答案。

(let [Q (fn [r] ((fn [f] (f f)) (fn [y] (r (fn [] (y y))))))
      fibs (Q (fn [fi] (lazy-cat [0 1] (map + (fi) (rest (fi))))))]
  (take 10 fibs))

Q我用来定义递归序列的这个组合器叫什么？它看起来像没有参数的 Y 组合器x。是一样的吗？

(defn Y [r] 
  ((fn [f] (f f)) 
   (fn [y] (r (fn [x] ((y y) x))))))

clojure.core 或 clojure.contrib 中是否有另一个函数提供 Y 或 Q 的功能？我无法想象我刚才所做的是惯用的......

4

2 回答 2

11

莱特雷克

我letrec最近为 Clojure 编写了一个宏，这是它的要点。它的作用类似于 Scheme 的letrec（如果你碰巧知道的话），这意味着它是和之间的交叉let：letfn你可以将一组名称绑定到相互递归的值，而无需将这些值作为函数（惰性序列也可以），只要有可能在不参考其他项目的情况下评估每个项目的头部（这是 Haskell - 或者可能是类型理论 - 用语；这里的“头部”可能代表惰性序列对象本身，具有 - 关键! -- 不涉及强制）。

你可以用它来写东西，比如

(letrec [fibs (lazy-cat [0 1] (map + fibs (rest fibs)))]
  fibs)

这通常只能在顶层实现。有关更多示例，请参见要点。

正如问题文本中指出的那样，以上内容可以替换为

(letfn [(fibs [] (lazy-cat [0 1] (map + (fibs) (rest (fibs)))))]
  (fibs))

在指数时间内获得相同的结果；该letrec版本具有线性复杂性（顶级(def fibs (lazy-cat [0 1] (map + fibs (rest fibs))))形式也是如此）。

迭代

自递归序列通常可以用iterate——即当固定范围的后视足以计算任何给定元素时构建。有关clojure.contrib.lazy-seqs如何计算的示例，fibs请参阅iterate。

clojure.contrib.seq

c.c.seqrec-seq提供了一个有趣的函数，叫做

(take 10 (cseq/rec-seq fibs (map + fibs (rest fibs))))

它的限制是只允许一个人构建一个自递归序列，但它可能会从它的源头中提取一些实现想法，从而实现更多样化的场景。如果您所追求的是未在顶层定义的单个自递归序列，那么这必须是惯用的解决方案。

组合器

至于问题文本中显示的组合子，重要的是要注意它们受到 JVM 上缺乏 TCO（尾调用优化）的阻碍（因此在 Clojure 中，它选择直接使用 JVM 的调用约定）最高性能）。

顶层

还可以选择将相互递归的“事物”放在顶层，可能在它们自己的命名空间中。如果需要以某种方式对这些“事物”进行参数化，这并没有那么好用，但是如果需要，可以动态创建命名空间（参见clojure.contrib.with-ns实现思路）。

最后的评论

我会欣然承认，这letrec与惯用的 Clojure 相去甚远，如果有其他办法，我会避免在生产代码中使用它（而且因为总是有顶级选项......）。然而，它（IMO！）很好玩，而且它似乎工作得很好。我个人有兴趣找出没有宏可以完成多少letrec以及在多大程度上letrec使事情变得更容易/更清洁......我还没有对此形成意见。所以，就在这里。再一次，对于单个自递归 seq 情况，iterate或 contrib 可能是最好的方法。

于 2010-07-30T19:01:27.077 回答
8

fn接受一个可选的名称参数，该名称绑定到其主体中的函数。使用这个特性，你可以写成fibs：

(def fibs ((fn generator [a b] (lazy-seq (cons a (generator b (+ a b))))) 0 1))
于 2010-08-01T01:53:38.767 回答