1

我试图在 Clojure 中编写一个简洁、懒惰的帕斯卡三角形，旋转使得行/列跟随三角形的对角线。也就是说，我想生成以下惰性序列的惰性序列：

((1 1 1 1 ...)
 (1 2 3 4 ...)
 (1 3 6 10 ...)
 ...
 )

我写的代码是：

(def pascal
  (cons (repeat 1)
        (lazy-seq
          (map #(map + %1 %2)
               (map #(cons 0 %) (rest pascal)))
               pascal
          )))

这样每一行都是通过将自身的右移版本添加到前一行来形成的。问题是它永远不会超过第一行，因为那时(map #(cons 0 %) (rest pascal)))是空的。

=> (take 5 (map #(take 5 %) pascal))
((1 1 1 1 1))

解决这个问题的明智方法是什么？我对使用 Clojure 进行编程非常陌生，并且对其中涉及的问题的思考方式非常不同，因此我非常感谢任何对此更有经验的人的建议。

4

2 回答 2

6

简洁而慵懒

(def pascal (iterate (partial reductions +') (repeat 1)))

(map (partial take 5) (take 5 pascal))
;=> ((1 1 1 1 1) 
;    (1 2 3 4 5) 
;    (1 3 6 10 15) 
;    (1 4 10 20 35) 
;    (1 5 15 35 70))

但是太懒了？

(take 5 (nth pascal 10000))
;=> StackOverflowError

再试一次

(take 5 (nth pascal 10000))
;=> (0)

哦，重新开始，然后再试一次

(def pascal (iterate (partial reductions +') (repeat 1)))
(count (flatten (map (partial take 5) (take 100000 pascal))))
;=> 500000

现在这些都在你的堆里

(take 5 (nth pascal 100000))
;=> (1 100001 5000150001 166676666850001 4167083347916875001)
于 2013-03-09T13:30:46.723 回答
2

pascal 不应该是一个 var，而是一个生成无限序列的函数。

查看此问题以了解有关惰性序列的用法

顺便说一句，试试这个：

(defn gennext [s sum]
  (let [newsum (+ (first s) sum)]
    (cons newsum
          (lazy-seq (gennext (rest s) newsum)))))

(defn pascal [s]
  (cons s
        (lazy-seq (pascal (gennext s 0)))))

在此处输入图像描述

(pascal (repeat 1)) 给你整数溢出异常，但这确实意味着它会产生无限的序列。您可以使用 +' 来使用大整数。

于 2013-03-09T15:53:04.133 回答