How do you "insert" into a vector?

[Glen Peterson]

In Java, I sometimes want to prepend things to the beginning of a vector, or insert them into the middle, shifting the current item and all subsequent items to the right.

Using assoc where the index is equal to the size of the vector is the same as an append, but with any other index, it is either a replace, or throws an exception.  This seems weird to me:

user=> (assoc [2 4 6] 1 7)

[2 7 6]

user=> (assoc [2 4 6] 2 7)

[2 4 7]

user=> (assoc [2 4 6] 3 7)

[2 4 6 7]

user=> (assoc [2 4 6] 4 7)

IndexOutOfBoundsException   clojure.lang.PersistentVector.assocN (PersistentVector.java:137)

How do you "insert" in Clojure shifting subsequent items to the right?  Maybe you don't use a vector, but use a sequence instead?  A brief example might be helpful.

[John Tollison]

I always do it the hard way and then suspect there's a better way. 

One hard way:

(defn insert [v i e] (vec (concat (subvec v 0 i) [e] (subvec v i))))

(insert [1 2 3 4] 2 10)

user => [1 2 10 3 4]

[John Tollison]

Or, 

(defn insert [v i e] (vec (concat (take i v) [e] (drop i v))))

[John Tollison]

Chousers answer (from google clojure group): https://groups.google.com/forum/#!topic/clojure/zjZDSziZVQk

(apply conj [:a :b] :q [:c :d]) 
  ;=> [:a :b :q :c :d] 

Apparently, there's no direct way to do it because it's not efficient

[Jeff Dik]

This is a great question!  I've run into cases like this a few times, where a common thing you want to do isn't directly available in Clojure.  Usually, there are good reasons :-)

On Sun, May 3, 2015 at 7:30 PM, John Tollison <jtoll...@gmail.com> wrote:

Chousers answer (from google clojure group): https://groups.google.com/forum/#!topic/clojure/zjZDSziZVQk

(apply conj [:a :b] :q [:c :d]) 
  ;=> [:a :b :q :c :d] 

Apparently, there's no direct way to do it because it's not efficient

That's an interesting thread.  Yeah, 'insert' is not defined on vectors because it's not efficient except on the end.  As Rich said later in the thread, "Not having insert on vector is not an oversight."

'conj' efficiently adds an element to the front of a list or to the back of a vector.  Chouser mentions that if you need to do insertions into an immutable vector-like data structure, you probably want finger trees.  He later went on and wrote a contrib library: https://github.com/clojure/data.finger-tree and gave a talk about it: https://www.youtube.com/watch?v=UXdr_K0Lwg4

What's probably more efficient (by constant factors, I think) today is RRB trees and there's a contrib library for that too: https://github.com/clojure/core.rrb-vector.  We can probably forgive Chouser and Rich for not mentioning RRB trees since the paper describing them was written after that thread (3/11/2012) :-)

So, if you check out that library, you might want wonder why there's no 'insert'.  I don't know, but here's one:

(defn insert [v i e]

  (fv/catvec (conj (fv/subvec v 0 i) e) (fv/subvec v i)))

And there you have it, a O(log N) insert on a immutable persistent rrb-vector!

As I was looking into this, it struck me again how "new" these immutable persistent data structures are.  I was also surprised that I haven't been desiring an 'insert' function more often.

Thanks,

Jeff

P.S.  Maybe I'll email the rrb-vector author and see if he wants to include an 'insert' function.

On Sunday, May 3, 2015 at 7:23:08 PM UTC-4, John Tollison wrote:

Or, 

(defn insert [v i e] (vec (concat (take i v) [e] (drop i v))))

On Sunday, May 3, 2015 at 9:28:22 AM UTC-4, John Tollison wrote:

I always do it the hard way and then suspect there's a better way. 

One hard way:

(defn insert [v i e] (vec (concat (subvec v 0 i) [e] (subvec v i))))

(insert [1 2 3 4] 2 10)

user => [1 2 10 3 4]

On Sunday, May 3, 2015 at 9:02:44 AM UTC-4, Glen Peterson wrote:

In Java, I sometimes want to prepend things to the beginning of a vector, or insert them into the middle, shifting the current item and all subsequent items to the right.

Using assoc where the index is equal to the size of the vector is the same as an append, but with any other index, it is either a replace, or throws an exception.  This seems weird to me:

user=> (assoc [2 4 6] 1 7)

[2 7 6]

user=> (assoc [2 4 6] 2 7)

[2 4 7]

user=> (assoc [2 4 6] 3 7)

[2 4 6 7]

user=> (assoc [2 4 6] 4 7)

IndexOutOfBoundsException   clojure.lang.PersistentVector.assocN (PersistentVector.java:137)

How do you "insert" in Clojure shifting subsequent items to the right?  Maybe you don't use a vector, but use a sequence instead?  A brief example might be helpful.

--
You received this message because you are subscribed to the Google Groups "Greenville Clojure Users Group" group.
To unsubscribe from this group and stop receiving emails from it, send an email to greenville-cloj...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Glen Peterson]

SWEET! Thank you both John and Jeff. Once again, Jeff, you have your
finger on the pulse in a way that I cannot even imagine.

I wish CHouser used "prepend" and "append" instead of consl and conjr.
"insert" taking an index would work too with (insert 0 x) being
prepend and (insert size x) being append.

Back at you with an older video describing, in a very complimentary,
exciting, and accessible way, why PersistentVector is the way it is in
Clojure, though it never mentions that you can only append to the end.
I know this has the word, "Scala" in the title, but it's really about
data structures in Clojure - and that's why you *might* not have seen
it already:
"Extreme Cleverness: Functional Data Structures in Scala" - Daniel Spiewak
https://www.youtube.com/watch?v=pNhBQJN44YQ

My own tests have shown that 2.5x the speed of java.util.ArrayList for
inserts is a very reasonable performance estimate for 0-1M entries if
the machine isn't loaded down with work in other threads. Actually
around 1M entries, it's maybe even faster than ArrayList. When the
machine is bogged down with lots of threads, it's more like 4.5x. I
don't know why.

Linked lists have the fastest prepend operation, and Clojure has those
built-in, so you really are only missing the insert-in-the-middle
operation. Come to think of it, with Strings in Java, I've written
one-off stuff where I split at some point and concatenate the first
part, some new thing, and the latter part, just the way I'd have to
with a PersistentVector. Actually, for escaping the occasional
character entity in text to make it safe for HTML, the split/concat
approach is about 100x faster than making the replacement with Java's
regular expressions and has always been fast enough to not be the
slowest point of what I was working on.

Coming from a Java background, I just expected the primary operation
of List to be insert() pushing subsequent items to the right, but it's
append() on a PersistentVector. It sounds like most of the time
that's just fine in practice, and only occasionally an issue. I think
it's mostly an expectation/habit, not an actual issue.

It looks like this question has morphed into "What's the best ordered
persistent data structure to support an insert operation?" That's a
much more interesting question!

That Bagwell/Rompf RRB trees paper comes out of EFPL in Switzerland
where Odersky teaches. Would that be a great place to study CS right
now, or what? I just want to go there and see if I can soak up any IQ
points by osmosis.

I just sent the Bagwell/Rompf RRB paper to the printer, though I guess
printing it is the easy part...

--
Glen K. Peterson
(828) 393-0081

[John Tollison]

Huh, that looks easier than I thought it would be!! Do you end up with proper equality semantics and everything else? It could make a good topic for a future meetup. I watched the video on finger trees a while back. I've been wanting a good sorted multiset/bag for a couple of years.

[yanick ekwanti]

On Wednesday, March 20, 2024 at 3:09:28 AM UTC+1 yanick ekwanti wrote:

PolkaDot mushroom chocolate – The dotted Belgian delight with a punch

https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic

Culinary innovations are here to redefine the boundaries of flavor. Need proof? Meet PolkaDot chocolate bars! Mouth-watering Belgian chocolate harmoniously entwined with the purest mushroom varieties carefully crammed into a polka-dotted bar – it is not just a snack but an extraordinary experience for your senses.

https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic

Every bite of this chocolate bar will take you beyond your culinary dreams. Get ready for an exquisite exploration fueled by magic mushrooms and the indulgent sweetness of the Cinnamon Toast Crunch flavor. It adds an extra layer of delight, with each bar resonating perfectly with the next.

https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic

The PolkaDot magic chocolate for sale is visually appetizing, too. The playful polka-dotted shape is an invitation to savor the artistry of the chocolatiers who have done their best to make it irresistible. Because they contain psilocybin, you wouldn’t give them to little ones, but PolkaDot bars are amazing as presents for grown-ups who don’t mind some punch.

https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic

Preserving the goodness of your PolkaDot chocolate

If you want to keep your indulgence ready to bite over time, you won’t be disappointed with PolkaDot. Store it in a dry container – with other treats or alone – and your mushroom bar will not lose any delicious or invigorating properties within 12 months. This means you can stock up on PolkaDot chocolate online without any fear of its magic tapering off.

https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic

There’s a caveat, though. Once you open the enchanting package, it’s best to have your delightful goodness within two weeks. The fresher, the better – it’s the key to unlocking the full spectrum of the Cinnamon Toast Crunch flavor and top-grade mushrooms.

Careful handling and secure delivery

https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic

If you are in the US, you can buy PolkaDot magic Belgian chocolate in the fastest way at Global Supply. We understand that when you crave something as extraordinary as PolkaDot bars, waiting is not an option. Our well-thought-out delivery system means you can get this product with overnight shipping, so all your cravings are promptly met.

https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
But what about the discreetness of PolkaDot packaging? The great news is that we put your bars in an invisible box to ensure your indulgence remains a delightful secret until you decide to unwrap it. Until then, nobody is going to judge your purchase or ask for a bite!

https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic

For the best experiences, we go above and beyond to ship PolkaDot chocolate with mushrooms at their freshest. You can trust us to deliver your bars safely and securely, preserving their quality and crunchy flavor until you’re ready to experience that magic.Treat yourself to the extraordinary as you buy PolkaDot chocolate online. This is where the Belgian taste, unusual texture, and psilocybin effects unite to create a sensory masterpiece. With a shelf life that allows you to savor it at your own pace and our dedication to discreet, secure delivery, nothing keeps you from having PolkaDot as your everyday treat. At only $50 per box, your taste buds will be quick to thank you

https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic
https://t.me/budExotic

[yanick ekwanti]