如何在Clojure中创建一个lazy-seq生成,匿名递归函数？

Question

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

我正在寻找一种简单的方法来定义let表单中的递归函数而不诉诸letfn.这可能是一个不合理的请求,但我寻找这种技术的原因是因为我混合了数据和递归函数,这些函数在某种程度上相互依赖需要大量的嵌套let和letfn语句.

我想编写生成这样的惰性序列的递归函数(以Fibonacci序列为例):

(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)))

但正如我刚才所说,这导致了很多繁琐的嵌套和交替的let和letfn.

为了在没有letfn和使用的情况下做到这一点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功能的函数？我无法想象我刚才所做的是惯用的......

Answer 1

letrec

我letrec最近为Clojure 写了一个宏,这里有一个要点.它就像Scheme一样letrec(如果你碰巧知道的话),这意味着它是let和之间的交叉letfn:你可以将一组名称绑定到相互递归的值,而不需要将这些值作为函数(惰性序列也可以),只要有可能在不参考其他项目的情况下评估每个项目的头部(那是Haskell - 或者也许是类型理论 - 用语;这里的"head"可能代表懒惰的序列对象本身,至关重要! - 没有强制参与).

你可以用它来写东西

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

这通常只能在顶级.有关更多示例,请参阅Gist.

正如问题文本中所指出的,上面的内容可以替换为

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

在指数时间内得到相同的结果; 该letrec版本具有线性复杂性(顶级(def fibs (lazy-cat [0 1] (map + fibs (rest fibs))))表单也是如此).

重复

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

clojure.contrib.seq

c.c.seq提供了一个称为一个有趣的功能rec-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可能是最好的方法.

Answer 2

fn获取一个可选的name参数,该名称参数绑定到其正文中的函数.使用此功能,您可以写fibs为:

(def fibs ((fn generator [a b] (lazy-seq (cons a (generator b (+ a b))))) 0 1))