如何在Clojure中创建一个延迟序列生成，匿名递归函数？ [英] How to create a lazy-seq generating, anonymous recursive function in Clojure?

问题描述

编辑：在写这篇文章的过程中，我发现部分回答了我自己的问题，但我认为它可以很容易地改进，所以我会发布。

我正在寻找一种简单的方法来定义 let 中的递归函数。形式而不求助于 letfn 。这可能是一个不合理的请求，但我寻找这种技术的原因是因为我有一个混合的数据和递归函数依赖于彼此在一个方式需要大量的嵌套 let 和 letfn 语句。

我想编写生成如下延迟序列的递归函数（使用Fibonacci序列作为示例）：

 （let [fibs（lazy-cat [0 1]（map + fibs（rest fibs）））] 
（take 10 fibs））
  

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

 （letfn [ []（lazy-cat [0 1]（map +（fibo）（rest（fibo））））] 
（take 10（fibo）））
  / pre> 
 
 
但是正如我前面所说的，这会导致很多繁琐的嵌套和交替 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]（ff））（fn [y] ）））））
 fibs（Q（fn [fi]（lazy-cat [0 1] ））
  
这个 Q 我使用定义一个递归序列？它看起来像没有参数 x 的Y组合器。是否相同？
 （defn Y [r] 
（fn [f]（ff））
（fn [y]（r（fn [x]（yy）x）））））
  
 clojure.core或clojure.contrib中是否有另一个函数提供Y或Q的功能？我不能想象我刚刚做的是惯用的... 
解决方案
 
 letrec 
 
 
 
我最近为Clojure写了一个 letrec 宏，这里是它的精神。它的行为像Scheme  letrec （如果你恰好知道），意味着它是 let 和 letfn ：您可以将一组名称绑定到相互递归的值，而不需要这些值是函数（惰性序列也可以），只要可以评估每个项目的头部没有引用其他（这是Haskell  - 或者可能是类型 - 理论 -  parlance;head在这里可能例如对于惰性序列对象本身，具有 - 至关重要的 - 没有强制涉及）。 
 
 
 
您可以使用它来编写
  ] b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b $ b 
这通常只能在顶层。 
 
 
 
正如问题文本中指出的，上面可以替换为
 （letfn [（fibs []（lazy-cat [0 1]（map +（fibs）（rest（fibs））））
 b $ b  
以指数时间  letrec 版本具有线性复杂性（顶层（def fibs（lazy-cat [0 1] ）））） form）。
 
 
 
 iterate 
 
 
 
自递归seq通常用 iterate 构造 - 即当固定范围的查找足以计算任何给定元素时。有关如何使用 iterate计算 fibs 的示例，请参阅 clojure.contrib.lazy-seqs  。
 
 
 
 clojure.contrib.seq 
 
 
 
  cc 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可能是最好的方式。
 
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...
解决方案
letrec

I have written a letrec macro for Clojure recently, here's a Gist of it. It acts like Scheme's letrec (if you happen to know that), meaning that it's a cross between let and letfn: 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
(letrec [fibs (lazy-cat [0 1] (map + fibs (rest fibs)))]
  fibs)
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
(letfn [(fibs [] (lazy-cat [0 1] (map + (fibs) (rest (fibs)))))]
  (fibs))
for the same result in exponential time; the letrec version 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. See clojure.contrib.lazy-seqs for an example of how to compute fibs with iterate.

clojure.contrib.seq

c.c.seq provides an interesting function called rec-seq, enabling things like
(take 10 (cseq/rec-seq fibs (map + fibs (rest fibs))))
It 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-ns for implementation ideas).

final comments

I'll readily admit that the letrec thing 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 without letrec and to what degree a letrec macro 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, iterate or contrib might be the best way to go.

                        
这篇关于如何在Clojure中创建一个延迟序列生成，匿名递归函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！