python - Clojure 和 Python 中的惰性无限序列

Question

以下是我能在 Clojure 和 Python 中找到的惰性无限斐波那契数列的最佳实现:

Clojure:

(def fib-seq (lazy-cat [0 1]
 (map + fib-seq (rest fib-seq))))

示例用法:

 (take 5 fib-seq)

python :

def fib():
 a = b = 1
 while True:
  yield a
  a,b = b,a+b

示例用法:

for i in fib():
  if i > 100:
    break
  else:
    print i

显然 Python 代码更直观。

我的问题是:在 Clojure 中是否有更好(更直观和简单)的实现？

编辑

我正在打开后续问题 Clojure Prime Numbers

Answer 1

我同意 Pavel 的观点，直觉是主观的。因为我(慢慢地)开始理解 Haskell，所以我可以说出 Clojure 代码的作用，即使我一生中从未写过一行 Clojure。所以我会认为 Clojure 系列相当直观，因为我以前见过它并且我正在适应更函数式的思维方式。

让我们考虑一下数学定义，好吗？

       { 0                   if x = 0 }
F(x) = { 1                   if x = 1 }
       { F(x - 1) + F(x - 2) if x > 1 }

这不太理想，格式明智 - 排成一行的三个括号应该是一个巨大的括号 - 但谁在数呢？对于大多数具有数学背景的人来说，这是斐波那契数列的一个非常清晰的定义。让我们看看 Haskell 中的同一件事，因为我比 Clojure 更了解它:

fib 0 = 0
fib 1 = 1
fib n = fibs (n - 1) + fibs (n - 2)

这是一个函数，fib，它返回第 n 个斐波那契数。不完全是我们在 Python 或 Clojure 中所拥有的，所以让我们解决这个问题:

fibs = map fib [0..]

这使得 fibs 成为斐波那契数列的无限列表。 小谎! 1 是 1，小谎! 2 是 1，小谎! 10 为 55，依此类推。然而，这可能是非常低效的，即使在像 Haskell 这样依赖高度优化的递归的语言中也是如此。让我们看看 Haskell 中的 Clojure 定义:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

前几个字符非常简单:0 : 1 : 构成一个包含元素 0 和 1 的列表，然后是更多元素。但是剩下的是什么呢？嗯，fibs 是我们已经得到的列表，而 tail fibs 调用了我们目前列表上的 tail 函数，它返回列表从第二个元素开始(有点像 Python 中的 fibs[1:])。所以我们采用这两个列表 - fibs 和 tail fibs - 我们用 + 函数(运算符)将它们压缩在一起 - 也就是说，我们添加每个的匹配元素。让我们看看:

fibs       = 0 : 1 : ...
tail fibs  = 1 : ...
zip result = 1 : ...

所以我们的下一个元素是 1!但随后我们将其添加回我们的 fibs 列表，看看我们得到了什么:

fibs       = 0 : 1 : 1 : ...
tail fibs  = 1 : 1 : ...
zip result = 1 : 2 : ...

我们这里有一个递归列表定义。当我们使用 zipWith (+) fibs (tail fibs) 位向 fibs 末尾添加更多元素时，我们在添加元素时可以使用更多元素。请注意，默认情况下，Haskell 是惰性的，因此仅创建一个这样的无限列表不会导致任何崩溃(只是不要尝试打印它)。

因此，虽然这在理论上可能与我们之前的数学定义相同，但它将结果保存在我们的 fibs 列表中(一种自动内存)，我们很少遇到可能遇到的问题在一个天真的解决方案中。为了完整起见，让我们根据新的 fibs 列表定义我们的 fib 函数:

fib n = fibs !! n

如果我还没有失去你，那很好，因为这意味着你了解 Clojure 代码。看:

(def fib-seq (lazy-cat [0 1]
 (map + fib-seq (rest fib-seq))))

我们制作一个列表，fib-seq。它以两个元素开始，[0 1]，就像我们的 Haskell 示例一样。我们使用 (map + fib-seq (rest fib-seq)) 对这两个初始元素进行惰性连接 - 假设 rest 做与 tail 相同的事情 在 Haskell 中确实如此，我们只是将我们的列表与其自身以较低的偏移量结合起来，然后将这两个列表与 + 运算符/函数结合起来。

在头脑中思考了几次并探索了一些其他示例之后，这种生成斐波那契数列的方法至少变得半直观了。它至少足够直观，让我可以用我不懂的语言来识别它。