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中的素数

Answer 1

如果你对命令式编程语言一点都不了解，这样的内容对你来说会容易理解吗？

a = a + 5

这是什么鬼？a 明显和 a + 5 不是一回事。

如果 a = a + 5，那 a + 5 = a 吗？

为什么这样不行？？？

if (a = 5) { // should be == in most programming languages
    // do something
}

有很多事情如果你没有在别的地方见过，也不明白它的用途，就会很模糊。我很长一段时间都不知道 yield 这个关键词，所以我根本搞不懂它是干嘛的。

你觉得命令式的写法更容易理解，因为你已经习惯了。

Answer 2

我同意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成为一个无限的斐波那契数列。fibs !! 1是1，fibs !! 2也是1，fibs !! 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的功能和Haskell中的tail一样，我们只是把列表和自己在一个较低的偏移量上结合，然后用+运算符/函数把这两个列表结合起来。

经过几次思考和探索其他示例后，这种生成斐波那契数列的方法变得至少半直观。对我来说，至少足够直观，可以在我不熟悉的语言中识别出来。

Answer 3

我喜欢：

(def fibs 
  (map first 
       (iterate 
           (fn [[ a, b       ]]  
                [ b, (+ a b) ]) 
           [0, 1])))     

这看起来和Python里的生成器版本有些相似。