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上开设了一个后续问题。

- Roskoto

---

显然，Python代码更加直观。这并不确切。它更倾向于"命令式编程"，对于很多人来说，命令式编程更明显，因为他们习惯了这种方式，但这是一个感性的问题，严格来说是主观的。 - Pavel Minaev

简单和直观是主观的。在我看来这不是一个真正的问题。 - Tadeusz A. Kadłubowski

@tkadlubo 斐波那契数列非常简单，我只是举个例子。但是在解决现实世界的问题时，超越简单和直观总是值得的。 - Roskoto

显然，Clojure 代码更直观。Python 是否有更好（更简洁、更清晰）的实现方式？ - Svante

我认为这里没有任何实质性的主观因素。在我大约10岁时，我就能够理解杂志上用BASIC编写的程序，尽管我从未见过真正的计算机。我相信我也会理解用Python编写的版本。直到我读完《计算机程序的构造和解释》（SICP）之前，我不会理解Clojure版本。我是一位函数式编程爱好者，我的首选语言是Clojure。我们应该停止试图说服人们，如果他们不“明白”，那是他们的错。函数式编程方式有其优点，但并非免费的。 - John Lawrence Aspden

显然，Python版本更直观，哈哈。我的第一反应是，“显然Clojure版本更优越”，因人而异。 - Alex Baranosky

Answer 1

我同意Pavel的观点，什么是直觉性是主观的。因为我（慢慢地）开始理解Haskell，所以即使我从未写过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执行相同的操作，我们只是将列表与其自身组合在较低的偏移处，然后使用+运算符/函数组合这两个列表。

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

- Chris Lutz

---

Chris，首先感谢您的详细解释，对于试图理解Clojure代码的人来说，它在某种程度上是有用的。但实际上，您证明了我的观点。Python代码不需要如此庞大的解释 :) - Roskoto

这段Python代码已经有了解释：约50年的命令式编程风格已经为你解释了它。如果我不会编程，我也不会对任何一种语言的代码了解很多。虽然在学习Haskell/Clojure这些语言时可能会让我的大脑更加困惑，但实际上你认为它们更可读/直观，是因为你习惯于命令式和过程式语言，就像大多数程序员一样。学习新的思维方式或范式需要很多解释。学习生成器需要多长时间？或者指针（如果你了解C的话）？ - Chris Lutz

yield 是一种命令式的语句，与堆栈无关。如果你发出命令（即“语句”——在 Python 中 yield 是一种语句），那么它就是命令式的。 - Pavel Minaev

感谢你，Pavel，提供了我应该提出的论点。尽管到这个时候，我想指出，既然我们已经就什么对我们来说是直观的进行了长时间的争论，并且由于我们在所发现的直观性上存在分歧，因此你（Roskoto）在做出X对所有程序员更具直观性的笼统假设时是错误的。 - Chris Lutz

在最坏的情况下，你可以自己在Clojure中实现生成器。例如，有些人已经为Common Lisp这样做了。如果我错了，请有人纠正我，但我认为yield并没有为语言增加任何功能；它只是语法糖。如果甚至老旧的Java都可以使用生成器，那么Clojure也可以。 - Brian Carper

Answer 2

我喜欢：

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

这似乎与Python/generator版本有一些相似之处。

- John Lawrence Aspden

---

这样好多了！看起来 OP 描述的版本还会在像 nth 这样的函数中将整个 seq 缓存到内存中，破坏了惰性序列的目的。 - FUD

Answer 3

如果您不了解任何命令式编程语言，这对您来说是否直观？

a = a + 5

什么鬼？a明显和a + 5不同。

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

为什么这不起作用？？？

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

除非你在其他地方看过并理解它的用途，否则有很多事情是不清楚的。长时间以来，我都不知道yield关键字的作用，因此我无法弄清楚它的功能。

你认为命令式方法更易读，是因为你习惯了它。

- Georg Schölly

Answer 4

对我来说，Clojure代码很直观（因为我了解Clojure）。如果你想要看起来更像你熟悉的东西，可以尝试这个高效但过于冗长的递归版本：

(use 'clojure.contrib.def)   ; SO's syntax-highlighting still sucks
(defn-memo fib [n]
  (cond (= n 0) 0
        (= n 1) 1
        :else   (+ (fib (- n 1))
                   (fib (- n 2)))))

(def natural-numbers (iterate inc 0))

(def all-fibs
  (for [n natural-numbers]
    (fib n)))

但对于不了解递归或记忆化的人来说，这也不会很直观。对于大多数程序员来说，“无限惰性序列”的概念可能都不是很直观。我猜不出你的想法，所以我不知道更加直观的Clojure函数对你来说会是什么样子，除了“看起来更像Python”。

对于不懂编程的人来说，所有这些东西都会看起来像胡言乱语。什么是循环？什么是函数？这个“yield”是什么东西？我们都是从这里开始的。直观性是你已经学到的东西的函数。非直观的代码是你还不熟悉的代码。从“我知道这个”推导到“它本质上更直观”是错误的。

- Brian Carper

---

对我而言，直观的意思更接近于数学定义。 - Roskoto

按照这种逻辑，Clojure版本比Python版本更清晰，因为Clojure版本是函数式的且更接近实际数学，而Python版本是过程式的。 - Chris Lutz

记忆化发生在哪里？是在contrib.def文件中吗？ - Ravi

Answer 5

如果您还没有看过的话，这个wiki页面详细介绍了Clojure中各种斐波那契数列实现的方法，这可能会引起您的兴趣。

- Timothy Pratley

Answer 6

这里有一个解决方案。

(defn fib-seq [a b]
  (cons (+ a b) (lazy-seq (fib-seq (+ a b) a))))

(def fibs (concat [1 1] (fib-seq 1 1)))

user=> (take 10 fibs)
(1 1 2 3 5 8 13 21 34 55)

- user206998

Answer 7

你应该总是使用适合问题的语言^*。 你的Python示例只是比Clojure示例更低级别--对于初学者来说更容易理解，但对于了解适合的更高级概念的人来说，编写和解析更加繁琐。

^* 顺便说一下，这也意味着拥有一个可以成长以适应的语言总是很好的。

- Svante

Answer 8

想一想，你会如何使用Clojure中的recur来编写lazy-cat。

- Tadeusz A. Kadłubowski

Answer 9

(take 5 fibs)

看起来这可能是最直观的了。我的意思是，这正是你要做的事情。你甚至不需要理解任何关于语言的知识，或者甚至不知道那是什么语言，就可以知道应该发生什么。

- nilamo