How to define a general recurrence function in Clojure

Question

I had an idea for a general function for recurrence relations in 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)))))

Then, for example, we can define the Fibonacci sequence as

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

This works well enough for small numbers:

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

But it blows the stack if asked to realise a long sequence:

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

Is there any way to overcome this?

noisesmith · Accepted Answer · 2014-10-18 19:16:16Z

4

The issue here is that you are building up calls to concat with every iteration, and the concat calls build up a big pile of unevaluated thunks that blow up when you finally ask for a value. By using cons and only passing forward the needed count of values (and concat, but not a recursive stack blowing concat), we get a better behaved lazy sequence:

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

edited Oct 18, 2014 at 19:16

answered Oct 18, 2014 at 19:08

noisesmith

20.2k2 gold badges43 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

noisesmith Over a year ago

A thought: we could remove the usage of concat, and make the function much more efficient, if we used a deque for the state (thus allowing efficient dropping of the oldest element in state, and efficient adding of the newest)

Thumbnail Over a year ago

Thank you for also explaining the cause of the failure.

Thumbnail Over a year ago

I've tried your suggestion of using a queue - no need for a deque, I think. See here.

Community · Accepted Answer · 2017-05-23 11:46:43Z

Starting from the accepted answer.

We want to start the sequence with the seed.
As the author suggests, we use a queue for efficiency. There's no need for a deque: clojure's PersistentQueue is all we need.

The adapted recurrence might look like this:

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

... and, as before ...

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

Then

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

and

(first (drop 10002 fibs))
;88083137989997064605355872998857923445691333015376030932812485815888664307789011385238647061572694566755888008658862476758094375234981509702215595106015601812940878487465890539696395631360292400123725490667987980947195761919733084221263262792135552511961663188744083262743015393903228035182529922900769207624088879893951554938584166812233127685528968882435827903110743620870056104022290494963321073406865860606579792362403866826411642270661211435590340090149458419810817251120025713501918959350654895682804718752319215892119222907223279849851227166387954139546662644064653804466345416102543306712688251378793506564112970620367672131344559199027717813404940431009754143637417645359401155245658646088296578097547699141284451819782703782878668237441026255023475279003880007450550868002409533068098127495095667313120369142331519140185017719214501847645741030739351025342932514280625453085775191996236343792432215700850773568257988920265539647922172315902209901079830195949058505943508013044450503826167880993094540503572266189964694973263576375908606977788395730196227274629745722872833622300472769312273603346624292690875697438264265712313123637644491367875538847442013130532147345613099333195400845560466085176375175045485046787815133225349388996334014329318304865656815129208586686515835880811316065788759195646547703631454040090435955879604123186007481842117640574158367996845627012099571008761776991075470991386301988104753915798231741447012236434261594666985397841758348337030914623617101746431922708522824868155612811426016775968762121429282582582088871795463467796927317452368633552346819405423359738696980252707545944266042764236577381721803749442538053900196250284054406347238606575093877669323501452512412179883698552204038865069179867773579705703841178650618818357366165649529547898801198617541432893443650952033983923542592952070864044249738338089778163986683069566736505126466886304227253105034231716761535350441178724210841830855527586882822093246545813120624113290391593897765219320931179697869997243770533719319530526369830529543842405655495229382251039116426750156771132964376N

Another way, based on an idea stolen - I think - from Joy of Clojure, is ...

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

Collectives™ on Stack Overflow

How to define a general recurrence function in Clojure

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related