如何创建Clojure中一个懒惰-SEQ生成的，匿名的递归函数？ [英] How to create a lazy-seq generating, anonymous recursive function in Clojure?

问题描述

修改：我发现了部分答案在写这篇的过程中我自己的问题，但我认为它可以很容易地在提高，所以我无论如何都会张贴。也许有更好的解决办法了吗？

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?

我要寻找一个简单的方法来定义在让形式递归函数，而不诉诸 letfn 。这可能是一个不合理的要求，但我期待该技术的原因是因为我有数据，而且在某种程度上依赖于彼此递归函数的组合需要大量的嵌套的让和 letfn 语句。

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.

我想写产生这样的懒人序列（使用Fibonacci序列为例）的递归函数：

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

但似乎Clojure中的小谎不能绑定过程中使用它自己的象征。围绕它最显而易见的方法是使用 letfn

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

不过，正如我刚才所说这导致了很多繁琐的嵌套和交替让和 letfn 的。

要做到这一点，而不 letfn 键，只用让，我开始写东西，使用什么样的，我认为是U型组合子（刚听到这个概念的今天）：

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

但如何摆脱的冗余的（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))

这是什么问：组合子叫我使用来定义一个递推数列是什么？它看起来像Y组合不带参数 X 。是不是一样的吗？

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

有没有clojure.core或clojure.contrib另一个功能是提供Y或Q的功能？我无法想象我刚才所做的就是地道的...

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...

推荐答案

我已经写了一个的Clojure letrec 宏最近，这里的它的一个要点。它就像方案的 letrec （如果你碰巧知道），这意味着它的之间的交叉让和 letfn ：可以绑定一组名称来相互递归的值，而不需要这些值是函数（懒惰序列是确定太），只要它是能够评价每个项目不参照别人的头（这是哈斯克尔 - 或许型 - 理论 - 的说法，头在这里可以站在如懒惰序列对象本身，与 - 关键 - 不强迫参与！）。

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

您可以用它来写东西像

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

对于相同的结果的在指数时间的;在 letrec 版本有线性复杂（如做一个顶级（DEF小谎（懒惰的猫[0 1]（地图+小谎（休息避免信口开河））））形式）。

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

自递归seqs可以经常与迭代构造 - 即当的样子，身后一个固定的范围足以计算任何给定的元素。参见 clojure.contrib.lazy-seqs 对于如何计算小谎与迭代的例子。

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.

c.c.seq 提供称为一个有趣的功能， REC-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.

至于组合子如那些在问题文本显示，需要注意的是它们是由缺乏的TCO（尾调用优化）在JVM（并因此在Clojure的，其中选择使用JVM的主叫阻碍是重要约定直接顶级性能）。

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

有也把相互递归的东西在最高层，有可能在自己的命名空间的选项。这不工作，所以巨大的，如果那些东西，需要以某种方式参数化，但命名空间可以动态如果需要的话（见 clojure.contrib.with-NS 的创建实现的想法）。

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

我会欣然承认，在 letrec 的事情还远远没有惯用的Clojure，我会避免使用它在生产中code。如果别的会做（和因为总是有顶层选项...）。但是，它是（IMO！）不错玩，它似乎工作不够好。我在找出多少可以不 letrec 来实现到什么程度 letrec 宏观使事情亲自感兴趣更容易/清洁...我还没有形成上发表意见呢。所以，在这里它是。再次，为单自递归序列的情况下，迭代或的contrib可能是最好的一段路要走。

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中一个懒惰-SEQ生成的，匿名的递归函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！