delete! semantics for vector vs. set

[mlubin]

There's an issue with the overloaded use of delete! to mean removing both a particular index from a vector and a particular element from a set: vectors partially implement set functions, and some set functions return vectors. See below.

julia> s1 = IntSet(10,12,13);s2 = IntSet(14,15,16);s3 = IntSet();

julia> u = union(union(s1,s2),s3)
IntSet(10, 12, 13, 14, 15, 16)

julia> delete!(u,12)
12

julia> u2 = union(s1,s2,s3)
6-element Any Array:
 10
 12
 13
 14
 15
 16

julia> delete!(u2,12)
ERROR: BoundsError()
 in delete! at array.jl:765

This particular case would be fixed by implementing union(s::IntSet,sets::IntSet...) to return an IntSet, but I think the problem is a bit bigger than this.

[JeffBezanson]

How about delindex!?

[mlubin]

Sounds good to me. delindex! for deleting indices in a vector and keys in a dictionary, and delete! for deleting elements in a set.

delete! could be defined for vectors and dictionaries as removing matching elements as well, but maybe delete!(::Dict,key) and delete!(::Array,i) should be deprecated for a while before suddenly changing the meaning of the function.

[StefanKarpinski]

Since we probably want the same function for vectors and hashes, this needs a little more thought. Maybe deletekey!?

[mlubin]

delindex! is a bit awkward for dicts and deletekey! is a bit awkward for vectors. Maybe they should be separate?

[mlubin]

The semantics are also different. After removing a key k from dict d, you can no longer access d[k]. For vectors, the elements are shifted, and the index you deleted could still be valid.

[StefanKarpinski]

Good point about the rather different semantics. This is all part of the final collections API bikeshedding push we need to do.

[JeffBezanson]

Stefan and I decided we will rename delete! for Vector to splice!, and add a form splice!(A, out, in) that replaces the indexes out with the values in, e.g.

julia> A = [1,2,3,4,5,6];

julia> splice!(A, 2:3, [7,8,9])
[2, 3]

julia> A
[1,7,8,9,4,5,6]

[JeffBezanson]

In other words, the default value of the third argument to splice! is an empty array.

[StefanKarpinski]

We could also support variants where the indices to remove/replace are non-contiguous, although that would obviously be more complicated to implement, but that's kind of why it's useful to have, actually.

[StefanKarpinski]

Actually, scratch that since when the range isn't contiguous it's ambiguous where to put the replacement values.

[kmsquire]

While I can see the problem highlighted here, I'm wondering if there is a better fix than the one committed?

One of the things I like about julia is that it combines performance with enough common sense that most things are intuitive and just work. I think this change goes against that. delete!() from an array is a common enough operation, and deleting by index is very intuitive. Finding splice!() when I'm looking to delete an element from an array seems potentially quite frustrating.

[johnmyleswhite]

I agree with Kevin that this is a non-intuitive change of names.

-- John

On May 31, 2013, at 8:36 PM, Kevin Squire notifications@github.com wrote:

While I can see the problem highlighted here, I'm wondering if there is a better fix than the one committed?

One of the things I like about julia is that it combines performance with enough common sense that most things are intuitive and just work. I think this change goes against that. delete!() from an array is a common enough operation, and deleting by index is very intuitive. Finding splice!() when I'm looking to delete an element from an array seems potentially quite frustrating.

—
Reply to this email directly or view it on GitHub.

[mlubin]

I'd agree with @kmsquire that there should be a more intuitive and searchable name for ''splice!'' when two arguments are used.

[JeffBezanson]

The cool part is that splice! can replace all of push!, pop!, append!, prepend!, shift!, unshift!, insert!. delete!, and empty!. So we could potentially replace much or all of this array-modifying interface with a single general function, which is a bigger deal than just a renaming.

[kmsquire]

I actually like those names for the array-modifying interface--they're familiar and intuitive.

(Reminds me of the debate between unix and perl philosophies...)

[JeffBezanson]

I don't think I'd actually remove all of them; for one thing, manipulating a single item (as in push!) with splice! requires wrapping it in an array.

It looks like the only other name idea out there is delindex!. Any other ideas?

[kmsquire]

From the original issue:

vectors partially implement set functions, and some set functions return vectors

While having vectors partially implement set functions might seem useful, perhaps that is the real issue here. When I'm using an array, I'm not expecting to be able to intersect it with another array. Why not remove the set functionality from vectors (what functionality is this?), and require users to wrap them in sets (or simply use) sets if they want set functionality.

This particular case would be fixed by implementing union(s::IntSet,sets::IntSet...) to return an IntSet, but I think the problem is a bit bigger than this.

@mlubin, can you elaborate on what the bigger problem is here? Even with the current fix, union(s::IntSet,sets::IntSet...) should return an IntSet.

[mlubin]

The bigger problem was exactly that delete meant different things for vectors and sets while vectors are sometimes used as sets.

[StefanKarpinski]

The delete! operation for dicts and sets is fundamentally different than removing a range of indices from an array and shifting all the following values down to those indices. That saw the main issue here. This recognizes that and generalizes the latter operation with the ability to provide replacement values and calls it splice!. The name comes from Perl, in which the splice function does exactly this. We considered expressing this as a[i:j] = values and having deletion be expressed as a[i:j] = [] but decided that this had the potential to hide too many bugs where the left and right sides were meant to be exactly the same size but might accidentally not be.

[kmsquire]

I understand the point about semantics of delete! operations being different between dicts/sets and arrays. They are also quite similar concepts (removing elements from a collection), and humans are pretty good about using the same word to describe different but related concepts, and garnering the actual meaning from context. In this particular case, while the actual semantics are different, it's unclear what to me what is gained by using a different word. While semantically different between dicts/sets and arrays, delete! is perfectly clear for removing elements of either, human's generally won't be confused, and the computer will interpret it just fine... unless the user is assuming that an array is a set.

(On the other hand, having separate names for these makes an array-based implementation of OrderedDicts/OrderedSets easier, since elements can now be removed by index (via splice!) or key (via delete!). I guess that pretty much deflates the previous paragraph and makes Stefan's point. :-) )

Cheers!

[JeffBezanson]

One possibility is only allowing set operations on OrderedSet(array) rather than on arrays directly. After all, there are other obstacles to using arrays as a drop-in replacement for Sets. For example <= is subset for Set but lexicographic for arrays. And | has been defined as union for Set. It would clearly help matters to change those, and use issubset() instead, and insist on using union and not | for Sets.

[toivoh]

@StefanKarpinski: Wouldn't it still be very useful to provide a two argument version of splice! with non-contiguous indexes?

[StefanKarpinski]

Yes, that would make sense and would work. It's a bit weird that the two-argument version can take any enumeration of indices whereas the three argument version can only take a range. It feels kind of strange.

[toivoh]

I guess that an alternative would be to leave splice! as it is and call the version for any kind of indices delindex!. Not sure if that is better.