如何在 Clojure 中创建惰性序列生成、匿名递归函数？
编辑：我在写这篇文章的过程中发现了我自己问题的部分答案，但我认为它可以很容易地改进，所以我无论如何都会发布它。也许有更好的解决方案？
我正在寻找一种简单的方法来以 let 形式定义递归函数，而无需求助于 letfn。这可能是一个不合理的请求，但我寻找这种技术的原因是因为我混合了数据和递归函数，它们在某种程度上相互依赖，需要大量嵌套的 let 和 < code>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)))
但正如我之前所说，这会导致大量麻烦的嵌套以及交替 let 和 letfn。
为了在不使用 letfn 并仅使用 let 的情况下完成此操作，我首先编写了一些使用我认为是 U 组合器的东西（今天刚刚听说这个概念）
(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 组合器叫什么？它看起来像没有参数 x 的 Y 组合器。是一样的吗？
(defn Y [r]
((fn [f] (f f))
(fn [y] (r (fn [x] ((y y) x))))))
clojure.core 或 clojure.contrib 中是否还有另一个函数提供 Y 或 Q 的功能？我无法想象我刚才所做的事情是惯用的......
Edit: I discovered a partial answer to my own question in the process of writing this, but I think it can easily be improved upon so I will post it anyway. Maybe there's a better solution out there?
I am looking for an easy way to define recursive functions in a let form without resorting to letfn. This is probably an unreasonable request, but the reason I am looking for this technique is because I have a mix of data and recursive functions that depend on each other in a way requires a lot of nested let and letfn statements.
I wanted to write the recursive functions that generate lazy sequences like this (using the Fibonacci sequence as an example):
(let [fibs (lazy-cat [0 1] (map + fibs (rest fibs)))]
(take 10 fibs))
But it seems in clojure that fibs cannot use it's own symbol during binding. The obvious way around it is using letfn
(letfn [(fibo [] (lazy-cat [0 1] (map + (fibo) (rest (fibo)))))]
(take 10 (fibo)))
But as I said earlier this leads to a lot of cumbersome nesting and alternating let and letfn.
To do this without letfn and using just let, I started by writing something that uses what I think is the U-combinator (just heard of the concept today):
(let [fibs (fn [fi] (lazy-cat [0 1] (map + (fi fi) (rest (fi fi)))))]
(take 10 (fibs fibs)))
But how to get rid of the redundance of (fi fi)?
It was at this point when I discovered the answer to my own question after an hour of struggling and incrementally adding bits to the combinator 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))
What is this Q combinator called that I am using to define a recursive sequence? It looks like the Y combinator with no arguments x. Is it the same?
(defn Y [r]
((fn [f] (f f))
(fn [y] (r (fn [x] ((y y) x))))))
Is there another function in clojure.core or clojure.contrib that provides the functionality of Y or Q? I can't imagine what I just did was idiomatic...
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
letrec
我最近为 Clojure 编写了一个
letrec宏，这里是它的要点 。它的作用类似于Scheme的letrec（如果你碰巧知道的话），这意味着它是let和letfn之间的交叉：你可以绑定一个集合名称到相互递归值，不需要这些值是函数（惰性序列也可以），只要可以评估每个项目的头部而不引用其他项目（这就是 Haskell ——或者可能是类型-理论上——用语；这里的“头”可能代表惰性序列对象本身，关键是不涉及强制）。您可以使用它来编写
通常只能在顶层才能实现的内容。有关更多示例，请参阅要点。
正如问题文本中所指出的，上面的内容可以替换
为相同的结果在指数时间内；
letrec版本具有线性复杂度（顶级(def fibs (lazy-cat [0 1] (map + fibs (rest fibs))))形式也是如此）。迭代
自递归序列通常可以用迭代来构造——即当固定范围的后视足以计算任何给定元素时。有关如何使用
iterate计算fibs的示例，请参阅clojure.contrib.lazy-seqs。clojure.contrib.seq
ccseq提供了一个有趣的函数，称为rec-seq，可以实现类似的功能。它有一个限制，即只允许构造单个自递归序列，但是或许可以从它的源头提取一些实现想法，从而实现更多样化的场景。如果您想要的是未在顶层定义的单个自递归序列，那么这必须是惯用的解决方案。
至于组合器
，例如问题文本中显示的组合器，需要注意的是，它们受到 JVM 上缺乏 TCO（尾部调用优化）的阻碍（因此在 Clojure 中，它选择直接使用 JVM 的调用约定）以获得最佳性能）。
顶层
还可以选择将相互递归的“事物”放在顶层，可能在它们自己的命名空间中。如果这些“东西”需要以某种方式参数化，那么这就不那么有效了，但是如果需要的话可以动态创建命名空间（有关实现思路，请参阅 clojure.contrib.with-ns ）。
最后的评论
我很容易承认
letrec的东西与惯用的 Clojure 相去甚远，如果有其他办法的话，我会避免在生产代码中使用它（而且因为总是有顶级选项...... ）。然而，它（IMO！）很好玩，而且看起来工作得很好。我个人感兴趣的是找出没有letrec可以完成多少工作，以及letrec宏在多大程度上使事情变得更容易/更干净......我还没有形成一个对此尚未发表意见。所以，就在这里。再说一遍，对于单个自递归 seq 情况，迭代或 contrib 可能是最好的方法。letrec
I have written a
letrecmacro for Clojure recently, here's a Gist of it. It acts like Scheme'sletrec(if you happen to know that), meaning that it's a cross betweenletandletfn: you can bind a set of names to mutually recursive values, without the need for those values to be functions (lazy sequences are ok too), as long as it is possible to evaluate the head of each item without referring to the others (that's Haskell -- or perhaps type-theoretic -- parlance; "head" here might stand e.g. for the lazy sequence object itself, with -- crucially! -- no forcing involved).You can use it to write things like
which is normally only possible at top level. See the Gist for more examples.
As pointed out in the question text, the above could be replaced with
for the same result in exponential time; the
letrecversion has linear complexity (as does a top-level(def fibs (lazy-cat [0 1] (map + fibs (rest fibs))))form).iterate
Self-recursive seqs can often be constructed with
iterate-- namely when a fixed range of look-behind suffices to compute any given element. Seeclojure.contrib.lazy-seqsfor an example of how to computefibswithiterate.clojure.contrib.seq
c.c.seqprovides an interesting function calledrec-seq, enabling things likeIt has the limitation of only allowing one to construct a single self-recursive sequence, but it might be possible to lift from it's source some implementation ideas enabling more diverse scenarios. If a single self-recursive sequence not defined at top level is what you're after, this has to be the idiomatic solution.
combinators
As for combinators such as those displayed in the question text, it is important to note that they are hampered by the lack of TCO (tail call optimisation) on the JVM (and thus in Clojure, which elects to use the JVM's calling conventions directly for top performance).
top level
There's also the option of putting the mutually recursive "things" at top level, possibly in their own namespace. This doesn't work so great if those "things" need to be parameterised somehow, but namespaces can be created dynamically if need be (see
clojure.contrib.with-nsfor implementation ideas).final comments
I'll readily admit that the
letrecthing is far from idiomatic Clojure and I'd avoid using it in production code if anything else would do (and since there's always the top level option...). However, it is (IMO!) nice to play with and it appears to work well enough. I'm personally interested in finding out how much can be accomplished withoutletrecand to what degree aletrecmacro makes things easier / cleaner... I haven't formed an opinion on that yet. So, here it is. Once again, for the single self-recursive seq case,iterateor contrib might be the best way to go.fn接受一个可选的名称参数，该名称绑定到其主体中的函数。使用此功能，您可以将fibs编写为：fntakes an optional name argument with that name bound to the function in its body. Using this feature, you could writefibsas: