Re: Converting seqs to vectors & caching lazyseqs

[Meikel Brandmeyer]

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...

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]



I cannot figure out how to write the function using recur. Any ideas?

I would like to write a function to convert these multidimensional LazySeqs to vectors. This is in case a user needs constant lookup time. 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).

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



user=> (vectorize '(1 2 (3 4 5) ((6) 7 8) () 9 10))
[1 2 [3 4 5] [[6] 7 8] [] 9 10]

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". 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.

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



Hope this helps.

Sincerely
Meikel

They calculate the value of an element only once and then cache the result.

smime.p7s
Description: S/MIME cryptographic signature