Clojure和Python中的懒惰无限序列

Question

以下是我在Clojure和Python中为懒惰无限序列的Fibonacci数找到的最佳实现:

Clojure的:

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

样品用量:

 (take 5 fib-seq)

蟒蛇:

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

我同意帕维尔的看法,直觉是主观的.因为我(慢慢地)开始讨厌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个Fibonacci数的函数.不完全是我们在Python或Clojure中所拥有的,所以让我们解决这个问题:

fibs = map fib [0..]

这使得fibsFibonacci数字无限列表.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我们列表中的函数,它返回从第2个元素开始的列表(有点像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 : ...

我们这里有一个递归列表定义.随着我们fibs使用我们的zipWith (+) fibs (tail fibs)位添加更多元素,我们可以在添加元素时使用更多元素.请注意,默认情况下Haskell是懒惰的,所以只创建一个这样的无限列表不会崩溃任何东西(只是不要尝试打印它).

因此,尽管理论上这可能与之前的数学定义相同,但它将结果保存在我们的fibs列表中(类似于自动记忆),我们很少遇到可能在天真解决方案中遇到的问题.为了完整性,让我们fib根据新fibs列表定义我们的功能:

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))- 假设在Haskell中rest做了同样的事情tail,我们只是将我们的列表与它自己组合在一个较低的偏移量,然后将这两个列表与+运算符/函数组合起来.

在通过你的头脑几次,并探索其他一些例子后,这种生成斐波纳契系列的方法至少变得半直观.它至少足够直观,让我用一种我不知道的语言来发现它.

Answer 2

我喜欢:

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

这似乎与python/generator版本有一些相似之处.

Answer 3

如果您不知道任何命令式语言,这对您来说是否直观？

a = a + 5

WTF？a 显然是不一样的a + 5.

如果a = a + 5,是a + 5 = a吗？

为什么这不起作用？

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

除非你在其他地方看过它并理解它的目的,否则有很多事情都不清楚.很长一段时间我都不知道yield关键字,实际上我无法弄清楚它做了什么.

您认为必要的方法更易读,因为您习惯了它.

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东西？这就是我们所有人开始的地方.直觉是你到目前为止所学到的功能.非直观的代码是您不熟悉的代码.从"我知道这个"到"它本身就更直观"的推断是错误的.

Answer 5

在维基有一个深入的治疗Clojure中的各种斐波纳契实现,如果你还没有看到它已经可能令您感兴趣的.