Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is my Clojure function likely to be very slow with lists or vectors?

I’m just learning Clojure and I just wrote this function:

(defn replace-last [coll value]
    (assoc coll (dec (count coll)) value))

I’m just a little concerned that it’s likely to be really slow for either lists and/or vectors — I just don’t understand them enough yet to know.

Thanks!

like image 527
Avi Flax Avatar asked Dec 10 '22 03:12

Avi Flax


1 Answers

For vectors, this will be pretty fast -- one of the promises of vectors is fast creation of slightly modified copies.

For lists, this won't work at all -- they are not associative (clojure.lang.Associative) and thus are not valid arguments to assoc. As for other possible approaches, if you need to get an actual list back (as opposed to a seq(able)), you're out of luck -- accessing / replacing the final element of a list is fundamentally a linear time operation. If, on the other hand, you'd be ok with a lazy seq which would look like your list except for the final element, you could implement a semi-lazy variant of butlast (the one in clojure.core is not lazy at all) and use that with lazy-cat:

(defn semi-lazy-butlast [s]
  (cond (empty? s) s
        (empty? (next s)) nil ; or perhaps ()
        :else (lazy-seq (cons (first s)
                              (semi-lazy-butlast (next s))))))

(defn replace-last [s x]
  (if (empty? s) ; do nothing if there is no last element to replace
    s
    (lazy-cat (semi-lazy-butlast s) [x])))

This defers replacing the final element until you actually get close to it in consuming your seq.

A sample interaction:

user=> (take 10 (replace-last (range) :foo))
(0 1 2 3 4 5 6 7 8 9)
user=> (take 10 (replace-last (range 10) :foo))
(0 1 2 3 4 5 6 7 8 :foo)
user=> (replace-last () :foo)
()
like image 93
Michał Marczyk Avatar answered Jan 12 '23 01:01

Michał Marczyk