Wow, that's really good. That's what I was trying to come up with all afternoon. I knew I needed some way to keep track of the function's state, but I couldn't figure it out.
I came up with my own version using Rich's zipper library, traversing the data structure like a tree, but yours is much faster. Thank you. On Sat, Aug 1, 2009 at 5:53 PM, Meikel Brandmeyer <m...@kotka.de> wrote: > Hi, > > Am 01.08.2009 um 18:37 schrieb Garth Sheldon-Coulson: > > I have a program that produces multidimensional LazySeqs, i.e. seqs of >> seqs of seqs of... >> >> I would like to write a function to convert these multidimensional >> LazySeqs to vectors. This is in case a user needs constant lookup time. >> >> The following function will do it: >> >> (defn vectorize [obj] >> (if-not (seq? obj) >> obj >> (vec (map vectorize obj)))) >> >> (def foo (list 1 2 3 (list 1 2 4 (list 1 4)) 2)) >> >> (vectorize foo) >> >> [1 2 3 [1 2 4 [1 4]] 2] >> >> However, since there is no recur there, the function is liable to blow the >> stack on a very deep data structure (or so I gather from reading about >> Clojure's lack of TCO). >> >> I cannot figure out how to write the function using recur. Any ideas? >> > > This function can obviously be not tail-recursive, because you need it's > return value to do further computations. What you could maybe use is > different "stack". > > (defn vectorize > [s] > (loop [s s > v [] > stack nil] > (if-let [s (seq s)] > (let [fst (first s)] > (if (seq? fst) > (recur fst [] (conj stack [(next s) v])) > (recur (next s) (conj v fst) stack))) > (if (seq stack) > (let [[s v-s] (peek stack)] > (recur s (conj v-s v) (pop stack))) > v)))) > > This function runs in constant stack space. It uses a separate list to > store the state needed for the function to continue. This is just what > happens in the call frame on the stack. I'm not sure that this is better, > but it will never cause a stack overflow. > > user=> (vectorize '(1 2 (3 4 5) ((6) 7 8) () 9 10)) > [1 2 [3 4 5] [[6] 7 8] [] 9 10] > > More broadly, this would not be necessary if I could tell my LazySeqs to >> cache accesses and they cached them using a constant-lookup-time data >> structure. I've seen mention that LazySeqs cache access, but they don't seem >> to for me: >> > > This is what's meant with "caching": > > user=> (def x (lazy-seq (cons (do (Thread/sleep 10000) :x) nil))) > #'user/x > user=> (time (first x)) > "Elapsed time: 10000.646 msecs" > :x > user=> (time (first x)) > "Elapsed time: 0.085 msecs" > :x > > They calculate the value of an element only once and then cache the result. > > Hope this helps. > > Sincerely > Meikel > > --~--~---------~--~----~------------~-------~--~----~ 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 Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---
