Как определить общую функцию повторения в Clojure

Question

У меня была идея для общей функции для рекуррентных отношений в 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 ... 

Есть ли способ преодолеть это?

Answer 1

Проблема заключается в том, что вы создаете вызовы на 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 

Answer 2

Начиная с the accepted answer.

• Мы хотим начать последовательность с seed.
• Как предлагает автор, мы используем очередь для повышения эффективности. Нет необходимости в deque: clojure's 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)))