功能局部,自参照,惰性纤维蛋白顺序 [英] Function-local, self-referential, lazy fibonacci sequence
问题描述
我想创建一个函数,返回一个延迟的无限序列的斐波纳契数字。
I would like to create a function that returns a lazily extended infinite sequence of Fibonacci numbers.
现在,我可以使我的序列在顶层这样的命名空间:
Right now, I can make my sequence available in the top-level namespace like this:
(def fibonacci-numbers
(lazy-cat [0 1] (map + fibonacci-numbers (rest fibonacci-numbers))))
但是,这意味着如果我开始消耗很多
However, this means that if I start consuming a lot of them, I lose control over the garbage collection.
我想要做类似的操作:
(defn fibonacci-numbers-fn []
(lazy-cat [0 1] (map + (fibonacci-numbers-fn) (rest (fibonacci-numbers-fn)))))
这显然不会工作,因为我将最终创建O(2 ^ n)序列。我想我要问如何在函数局部命名空间中创建一个自引用延迟序列。我应该怎么办?
This clearly will not work because I will end up creating O(2^n) sequences. I think I am asking how to create a self-referential lazy sequence in a function-local namespace. What should I do?
编辑:虽然我喜欢amalloy发布的流行解决方案,并在互联网上找到 defn fibs [] (iterate(fn [[ab]] [b(+ ab)])))
,我对类似于规范Haskell方法的版本感兴趣:
Although I like the popular solution posted by amalloy and found all over the internet defn fibs [] (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))
, I'm interested in a version similar to the canonical Haskell way:
fibonaccis = 0 : 1 : zipWith (+) fibonaccis (tail fibonaccis)
这是我试图用我的原始函数完成。对我来说,map-iterate解决方案读取像添加前两个元素来创建新的元素,lazy-cat解决方案读为像加入其第一个滞后的流。
This is what I was trying to accomplish with my original function. To me, the map-iterate solution reads like "add the previous two elements to create a new one" and the lazy-cat solution reads like "join a stream with its first lag". How can I "join a stream with its first lag" without having the sequence in the top-level namespace?
推荐答案
如何定义函数定义的函数由 fn
表单可以递归,如果你在[]之前放一个可选的名称。 (在此示例中使用的名称为 this
)
Functions defined by the fn
form can be recursive if you put an optional name before the []. (in this example the name used is this
)
user> (defn fibonacci-numbers []
((fn this [a b] (lazy-seq (cons a (this b (+ a b))))) 0 1))
user> (take 10 (fibonacci-numbers))
(0 1 1 2 3 5 8 13 21 34)
$ b b
产生序列的实际函数是匿名函数,每次调用时只产生下一个元素。没有堆栈或堆溢出的机会(除非你在一个var中保存了封闭函数的返回值)
The actual function producing the sequence is the anonymous function which only produces the next element each time it is called. No chance of a stack or heap overflow (unless you hold the return value of the enclosing function in a var somewhere)
这篇关于功能局部,自参照,惰性纤维蛋白顺序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!