Clojure 程式設計/示例/惰性斐波那契
< Clojure 程式設計 | 示例
一個惰性生成斐波那契數的函式
(def fib-seq
((fn rfib [a b]
(lazy-seq (cons a (rfib b (+ a b)))))
0 1))
user> (take 20 fib-seq)
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)
一個在資料上遞迴，而不是在函式上遞迴的版本。參見http://en.wikipedia.org/wiki/Corecursion
(def fib-seq
(lazy-cat [0 1] (map + (rest fib-seq) fib-seq)))
user> (take 20 fib-seq)
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)
另一個遞迴版本，使用了reductions 函式。... 這有效嗎？不。看起來是假的。參見討論。
(def fib-seq
(cons 1 (reductions + (first fib-seq) fib-seq)))
user> (take 20 fib-seq)
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)
前面的版本可能存在問題：它們建立的斐波那契惰性序列繫結到頂層變數。因此，它們不會被垃圾回收，如果用於計算非常長的序列，將會消耗大量堆記憶體。更智慧的做法是將 fib-seq 定義為一個無引數函式，它按需返回惰性序列。然後，呼叫者可以將惰性序列放置在適當的作用域中（希望不是頂層作用域）
(defn fib-seq []
((fn rfib [a b]
(cons a (lazy-seq (rfib b (+ a b)))))
0 1))
user> (take 20 (fib-seq))
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)
我們可以使用iterate 生成 [a b] 對，然後取每個對的第一個元素。
(defn fib-step [[a b]]
[b (+ a b)])
(defn fib-seq []
(map first (iterate fib-step [0 1])))
user> (take 20 (fib-seq))
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)
本示例還使用了解構。
;; note that your 'start' parameter must be a vector with at least two numbers (the two which are your starting points)
(defn fib [start range]
"Creates a vector of fibonnaci numbers"
(if (<= range 0)
start
(recur (let[subvector (subvec start (- (count start) 2))
x (nth subvector 0)
y (nth subvector 1)
z (+ x y)]
(conj start z))
(- range 1))))
透過將序列與其自身對映（偏移一個元素）來計算斐波那契序列。
(def fib (cons 0 (cons 1 (lazy-seq (map + fib (rest fib))))))