函数局部、自引用、惰性斐波那契数列 [英] 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 [] (map first (iterate (fn [[ab]] [b (+ ab)]) [0 1])))，我对类似于规范 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 解决方案读起来像添加前两个元素以创建一个新元素"，而懒猫解决方案读起来像加入具有第一个滞后的流".如何在没有顶级命名空间中的序列的情况下加入第一个滞后的流"?

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)

产生序列的实际函数是匿名函数，它每次被调用时只产生下一个元素.没有堆栈或堆溢出的机会(除非您将封闭函数的返回值保存在某个地方的 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屋！