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))))))