Clojure Lazy Sequences that are Vectors

Question

I have noticed that lazy sequences in Clojure seem to be represented internally as linked lists (Or at least they are being treated as a sequence with only sequential access to elements). Even after being cached into memory, access time over the lazy-seq with nth is O(n), not constant time as with vectors.

;; ...created my-lazy-seq here and used the first 50,000 items

(time (nth my-lazy-seq 10000))
"Elapsed time: 1.081325 msecs"

(time (nth my-lazy-seq 20000))
"Elapsed time: 2.554563 msecs"

How do I get a constant-time lookups or create a lazy vector incrementally in Clojure?

Imagine that during generation of the lazy vector, each element is a function of all elements previous to it, so the time spent traversing the list becomes a significant factor.

Related questions only turned up this incomplete Java snippet: Designing a lazy vector: problem with const

j-g-faustus j-g-faustus · Accepted Answer · 2010-06-21T10:40:57

Yes, sequences in Clojure are described as "logical lists" with three operations (first, next and cons).

A sequence is essentially the Clojure version of an iterator (although clojure.org insists that sequences are not iterators, since they don't hold iternal state), and can only move through the backing collection in a linear front-to-end fashion.

Lazy vectors do not exist, at least not in Clojure.

If you want constant time lookups over a range of indexes, without calculating intermediate elements you don't need, you can use a function that calculates the result on the fly. Combined with memoization (or caching the results in an arg-to-result hash on your own) you get pretty much the same effect as I assume you want from the lazy vector.

This obviously only works when there are algorithms that can compute f(n) more directly than going through all preceding f(0)...f(n-1). If there is no such algorithm, when the result for every element depends on the result for every previous element, you can't do better than the sequence iterator in any case.

Edit

BTW, if all you want is for the result to be a vector so you get quick lookups afterwards, and you don't mind that elements are created sequentially the first time, that's simple enough.

Here is a Fibonacci implementation using a vector:

(defn vector-fib [v]
  (let [a (v (- (count v) 2)) ; next-to-last element
        b (peek v)]   ; last element
    (conj v (+ a b))))

(def fib (iterate vector-fib [1 1]))

(first (drop 10 fib))
  => [1 1 2 3 5 8 13 21 34 55 89 144]

Here we are using a lazy sequence to postpone the function calls until asked for (iterate returns a lazy sequence), but the results are collected and returned in a vector.

The vector grows as needed, we add only the elements up to the last one asked for, and once computed it's a constant time lookup.

Was it something like this you had in mind?

Clojure Lazy Sequences that are Vectors

1 Answers