编辑 : 我在写这篇文章的过程中发现了我自己问题的部分答案,但我认为它可以很容易地改进,所以我还是会发布它。也许那里有更好的解决方案?
我正在寻找一种在 let
中定义递归函数的简单方法。形式不诉诸letfn
.这可能是一个不合理的要求,但我正在寻找这种技术的原因是因为我混合了数据和递归函数,这些函数在某种程度上相互依赖,需要大量嵌套 let
和 letfn
陈述。
我想编写生成这样的惰性序列的递归函数(以斐波那契序列为例):
(let [fibs (lazy-cat [0 1] (map + fibs (rest fibs)))]
(take 10 fibs))
但在 clojure 中似乎
fibs
在绑定(bind)期间不能使用它自己的符号。明显的解决方法是使用 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 的功能?我无法想象我刚才所做的是惯用的......
最佳答案
莱特雷克
我写了一个letrec
Clojure 最近的宏,这里是 a Gist of it .它的作用类似于 Scheme 的 letrec
(如果你碰巧知道的话),这意味着它是 let
之间的交叉。和 letfn
:您可以将一组名称绑定(bind)到相互递归的值,而无需将这些值作为函数(惰性序列也可以),只要可以在不引用其他项目的情况下评估每个项目的头部(那就是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.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 可能是最好的方法。
关于binding - 如何在 Clojure 中创建一个生成惰性序列的匿名递归函数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3373157/