What is the idiomatic way to prepend to a vector in Clojure?

Question

Prepending to a list is easy:

user=> (conj '(:bar :baz) :foo)
(:foo :bar :baz)

Appending to a vector is easy:

user=> (conj [:bar :baz] :foo) 
[:bar :baz :foo]

How do I (idiomatically) prepend to a vector, while getting back a vector? This does not work as it returns a seq, not a vector:

user=> (cons :foo [:bar :baz])     
(:foo :bar :baz)

This is ugly (IMVHO):

user=> (apply vector (cons :foo [:bar :baz])) 
[:foo :bar :baz]

Note: I basically just want a datastructure that I can append and prepend to. Appending to large lists should have a large performance penalty, so I thought of vectors..

Solution 1

Vectors are not designed for prepending. You have only O(n) prepend:

user=> (into [:foo] [:bar :baz])
[:foo :bar :baz]

What you want is most likely a finger tree.

Solution 2

I know this question is old, but no one said anything about difference lists and since you say you really just want something you can append and prepend with, it sounds like difference lists might help you. They don't seem popular in Clojure, but they are VERY easy to implement and a lot less complex than finger trees, so I made a tiny difference list library, just now (and even tested it). These concatenate in O(1) time (prepend or append). Converting a difference list back to a list should cost you O(n), which is a nice trade-off if you're doing a lot of concatenation. If you're not doing a lot of concatenation, then just stick to lists, right? :)

Here are the functions in this tiny library:

dl: A difference list is actually a function which concats its own contents with the argument and returns the resulting list. Every time you produce a difference list, you're creating a little function that acts like a data structure.

dlempty: Since a difference list just concats its contents to the argument, an empty difference list is the same thing as the identity function.

undl: Because of what difference lists do, you can convert a difference list to a normal list just by calling it with nil, so this function isn't really needed; it's just for convenience.

dlcons: conses an item to the front of the list -- not totally necessary, but consing is a common enough operation and it's just a one-liner (like all of the functions, here).

dlappend: concats two difference lists. I think its definition is the most fun -- check it out! :)

And now, here's that tiny library -- 5 one-line functions that give you a O(1) append/prepend data structure. Not bad, eh? Ah, the beauty of Lambda Calculus...

(defn dl
  "Return a difference list for a list"
  [l]
  (fn [x] (concat l x)))

; Return an empty difference list
(def dlempty identity)

(defn undl
  "Return a list for a difference list (just call the difference list with nil)"
  [aDl]
  (aDl nil))

(defn dlcons
  "Cons an item onto a difference list"
  [item aDl]
  (fn [x] (cons item (aDl x))))

(defn dlappend
  "Append two difference lists"
  [dl1 dl2]
  (fn [x] (dl1 (dl2 x))))

You can see it in action with this:

(undl (dlappend (dl '(1 2 3)) (dl '(4 5 6))))

which returns:

(1 2 3 4 5 6)

This also returns the same thing:

((dl '(1 2 3)) '(4 5 6))

Have fun with difference lists!

Update

Here are some definitions that may be more difficult to understand but I think are better:

(defn dl [& elements] (fn [x] (concat elements x)))
(defn dl-un [l] (l nil))
(defn dl-concat [& lists] (fn [x] ((apply comp lists) x)))

This lets you say something like this:

(dl-un (dl-concat (dl 1) (dl 2 3) (dl) (dl 4)))

Which would return

(1 2 3 4)

Solution 3

As the user optevo said in the comments under the finger trees answer, you can use the clojure/core.rrb-vector lib, which implements RRB-trees:

RRB-Trees build upon Clojure's PersistentVectors, adding logarithmic time concatenation and slicing. ClojureScript is supported with the same API except for the absence of the vector-of function.

I decided to post this as a separate answer, because I think this library deserves that. It supports ClojureScript and it's maintained by Michał Marczyk, who is fairly known within the Clojure community for his work on implementing various data structures.

Solution 4

If you don't fear quasiquoting, this solution is actually pretty elegant (for some definitions of 'elegant'):

> `[~:foo ~@[:bar :baz]]

[:foo :bar :baz]

I actually use this on occasion in real code, since the declarative syntax makes it pretty readable IMHO.

Solution 5

I would suggest using the convenience features built into the Tupelo Library. For example:

(append [1 2] 3  )   ;=> [1 2 3  ]
(append [1 2] 3 4)   ;=> [1 2 3 4]

(prepend   3 [2 1])  ;=> [  3 2 1]
(prepend 4 3 [2 1])  ;=> [4 3 2 1]

by comparison, with raw Clojure it is easy to make a mistake:

; Add to the end
(concat [1 2] 3)    ;=> IllegalArgumentException
(cons   [1 2] 3)    ;=> IllegalArgumentException
(conj   [1 2] 3)    ;=> [1 2 3]
(conj   [1 2] 3 4)  ;=> [1 2 3 4]

; Add to the beginning
(conj     1 [2 3] ) ;=> ClassCastException
(concat   1 [2 3] ) ;=> IllegalArgumentException
(cons     1 [2 3] ) ;=> (1 2 3)
(cons   1 2 [3 4] ) ;=> ArityException

View more solutions

Comments

[optevo]

rrb-vectors can be concatenated (and therefore prepended) in O(log n) time. See github.com/clojure/core.rrb-vector

[Rafał Cieślak]

I'd recommend rrb-vectors, too. I found this post and after digging on the Clojure mailing list, I found another two libs that were supposed to replace data.finger-tree and add ClojureScript support. rrb-vector is a contrib project maintained by Michał Marczyk, which is a respected contributor within the Clojure community. Not that the authors of the other libs aren't, it just that I–being a Clojure newbie–don't recognize them.

[d11wtq]

There's no real reason why Clojure's Vector can't do a prepend with the same time complexity as an append. I've implemented this in Go, here: github.com/d11wtq/persistent/tree/feature/prepend. The solution is to 1) Remember a "start offset" (default = 0) and use that in all tree operations. 2) When prepending, if "start offset" = 0, allocate a new root node, position the old root node halfway within it and update the "start offset" to this position. 3) In all other cases prepend then just becomes a case of decreasing the "start offset" and doing a normal assoc at index 0.

[d11wtq]

The concerns about memory waste in that design are removed by lazily initializing nodes only when they will store data. A shift operation (pop on the left) is achieved by incrementing the "start offset" and doing an assoc of null on the zeroth element. Care must be taken to remove nodes paths followed for indices < "start offset" would take.

[d11wtq]

I haven't explored it yet, but I suspect split and concat could be done in O(log32(n)), effectively O(1) using this same data structure manipulation.

[onetom]

Indeed! I was quite envious of ES6 spread syntax and haven't realized that we can do some of that with quasi-quoting: (let [x [1 2]] `[0 ~@x]) => [0 1 2]