Chouser a écrit : > Testing just now on large collections, the version using 'map' is > indeed not only slower, but also overflows the stack. Hm... and > perhaps I see why now. Is it computing the entire chain up to each > result -- O(n^2), demanding n stack frames for the nth result? > The problem is that to compute the rest (reduction f init coll) you call (reduction f init coll) again. So, as you said, at each step you are computing the entire chain up to each result. The expansion of you code (by replacing (reduction f init coll) by its definition) is: (lazy-cons init (map f (rest coll) (lazy-cons init (map f (rest coll) (lazy-cons init (map f (rest coll) (lazy-cons init (map f (rest coll) (...))))
And here is what I mean by "using mutation" to solve this problem (it's a kind of memoization): (defn reduction "Returns a lazy seq of the intermediate values of the reduction (as per reduce) of coll by f, starting with init." ([f coll] (if (seq coll) (reduction f (first coll) (rest coll)) (cons (f) nil))) ([f init coll] (let [self (atom nil) result (lazy-cons init (map f @self coll))] (swap! self (constantly result)) result))) Christophe --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---