如何用Clojure

定义一般递推功能我有一个想法，对于Clojure中递推关系的一般功能：如何用Clojure

(defn recurrence [f inits] 
    (let [answer (lazy-seq (recurrence f inits)) 
     windows (partition (count inits) 1 answer)] 
    (concat inits (lazy-seq (map f windows)))))

然后，例如，我们可以定义斐波那契序列

(def fibs (recurrence (partial apply +) [0 1N]))

此作品不够好，小的数字：

(take 10 fibs) 
;(0 1N 1N 2N 3N 5N 8N 13N 21N 34N)

但它吹堆栈，如果要求实现长序列：

(first (drop 10000 fibs)) 
;StackOverflowError ...

有没有什么办法可以克服呢？

来源

2014-10-18 Thumbnail

这里的问题在于，您在每次迭代时都会拨打电话concat，并且concat电话会在您最终要求提供价值时形成一大堆未评估的电话号码。通过使用利弊，只有通过前值的所需数量（和concat，但不是递归栈吹concat），我们得到一个更好的表现懒惰的序列：

user> 
(defn recurrence 
    [f seed] 
    (let [step (apply f seed) 
     new-state (concat (rest seed) (list step))] 
    (lazy-seq (cons step (recurrence f new-state))))) 
#'user/recurrence 
user> (def fibs (recurrence +' [0 1])) 
#'user/fibs 
user> (take 10 fibs) 
(1 2 3 5 8 13 21 34 55 89) 
user> (first (drop 1000 fibs)) 
113796925398360272257523782552224175572745930353730513145086634176691092536145985470146129334641866902783673042322088625863396052888690096969577173696370562180400527049497109023054114771394568040040412172632376N

来源

2014-10-18 19:08:37 noisesmith

一个想法：我们可以删除CONCAT的使用，使功能多如果我们为状态使用deque（从而允许有效地丢弃最旧的元素，并且有效地添加最新的），那么效率更高。 – noisesmith 2014-10-18 19:23:14

谢谢您也解释失败的原因。 – Thumbnail 2014-10-18 20:58:16

我试过使用队列的建议 - 我认为没有必要使用双流队。请参阅[这里]（http://stackoverflow.com/a/43126749/1562315）。 – Thumbnail 2017-03-30 19:29:32

从the accepted answer开始。

我们想用seed开始序列。
正如作者所建议的那样，我们使用队列来提高效率。没有必要使用deque：clojure的PersistentQueue就是我们所需要的。

的适应recurrence可能是这样的：

(defn recurrence 
    [f seed] 
    (let [init-window (into (clojure.lang.PersistentQueue/EMPTY) seed) 
     unroll (fn unroll [w] (lazy-seq (cons 
              (peek w) 
              (unroll (-> w 
                 pop 
                 (conj (apply f w)))))))] 
    (unroll init-window)))

......和以前一样......

(def fibs (recurrence +' [0 1]))

然后

(take 12 fibs) 
;(0 1 1 2 3 5 8 13 21 34 55 89)

和

(first (drop 10002 fibs)) 
;880831379899970646053558729988579234456913330153760309328124858158886643077890113852386470615726945667558880086588624767580943752349815097022155951060156018129408784874658905396963956313602924073406865860606579792362403866826411642270661211435590340090149458419810817251120025713501918959350654895682804718752319215892119222907223279849851227166387954139546662644064653804466345416102543306712688251378793506564112970620367672131344559199027717813404940431009754143637417645359401155245658646088296578097547699141284451819782703782878668237441026255023475279003880007450550868002409533068098127495095667313120369142331519140185017719214501847645741030739351025342932514280625453085775191996236343792432215700850773568257988920265539647922172315902209901079830195949058505943508013044450503826167880993094540503572266189964694973263576375908606977788395730196227274629745722872833622300472769312273603346624292690875697438264265712313123637644491367875538847442013130532147345613099333195400845560466085176375175045485046787815133225349388996334014329318304865656815129208586686515835880811316065788759195646547703631454040090435955879604123186007481842117640574158367996845627012099571008761776991075470991386301988104753915798231741447012236434261594666985397841758348337030914623617101746431922708522824868155612811426016775968762121429282582582088871795463467796927317452368633552346819405423359738696980252707545944266042764236577381721803749442538053900196250284054406347238606575093877669323501452512412179883698552204038865069179867773579705703841178650618818357366165649529547898801198617541432893443650952033983923542592952070864044249738338089778163986683069566736505126466886304227253105034231716761535350441178724210841830855527586882822093246545813120624113290391593897765219320931179697869997243770533719319530526369830529543842405655495229382251039116426750156771132964376N

另一种方式的基础上，偷一个想法 - 我认为 - 从喜悦的Clojure的，是...

(defn recurrence 
    [f seed] 
    (let [init-window (into (clojure.lang.PersistentQueue/EMPTY) seed) 
     windows (iterate 
        (fn [w] (-> w, pop, (conj (apply f w)))) 
        init-window)] 
    (map peek windows)))

来源

2017-03-30 19:25:08 Thumbnail

回答

相关问题