RFC: rename push/pop/unshift/shift to push_{front,back}/pop_{front,back}

[erickt]

I'm in the finishing touches of adding a container::MutableSeq, and I'm realizing it's a bit inconsistent that vec has methods like push() whereas DList has push_back(). I personally feel that we should rename the vec methods to make it explicit where exactly we are pushing/popping the values. I suggest that we make these following renames:

.push() => .push_back()
.pop() => .pop_back()
.unshift() => .push_front()
.shift() => .pop_front()

We could also use append() and prepend() for push() and pop(), but I don't like that as much. Or we could rename the DList methods, but I'm also not in favor of that. What does everyone else think?

[brson]

I've always had a hard time remembering what shift and unshift mean.

[ghost]

shift() is more descriptive in that it's O(n), and push_back() for such a common operation smells too much like C++ to me.

[nikomatsakis]

I guess we took shift and unshift from JS, but I agree they are inscrutable. I like the C++ names, but I'm also game for other names. I think we should copy some languages, whether it be C++, Java, C#, Scala, Python, whatever. Maybe @erickt you can can survey the names used in other languages? (or someone else who is motivated)

[pnkfelix]

Off the top of my head

.unshift() => .shift_off_front()
.shift(x) => .shift_onto_front(x)

(and leave push/pop as they are. Or perhaps also add synonyms push_onto_back and pop_off_back to match up with the above, though I'm not terribly wedded to that idea.)

The main idea here would be make the shifting operations self-describing in both effect and in expense.

[erickt]

@Jurily: Just because C++ uses the name .push_back() doesn't make it a bad idea :) We need a generic interface for mutable sequences, and it's helpful to have some symmetry in the names for pushing and popping values from both ends of the sequence.

The reason why I want to make this change is that I want to unify all the sequence types under a common trait. So if/when I make that change, DList and RingBuf won't have that O(n) overhead to push a value on the front of the sequence. So I think it'd be helpful to have a more general purpose name. I think it's fair to say that .push_front() and .pop_back() might not be the right names, so I'll do a survey into what other languages are using.

[pnkfelix]

@erickt Why should the names chosen for some unified trait like MutableSeq have an influence on the names we select for vec ? (This is one of the advantages of traits over templates: you don't have to choose your method names up front to match all possible scenarios where the type could be used for a generic instantiation.)

I would think for a particular data-type, you should choose names that convey each methods behavior (in terms of effect, time expense, etc).

And then for the unified trait, you would choose names that focus on the end-to-end effect, because the trait presumably won't dictate constraints on O(1) versus O(n), unless it does. :)

[metajack]

Clojure uses conj (for conjoin) which does the most efficient type of addition of a single item to a collection. For a list this is push_front and for a vector it is push_back. It also has methods that push exactly where you specify. The thing that is nice about this is that you usually only need to use conj.

So it might be interesting to have push and pop be the efficent thing for the particular collection, and also provide push_front, pop_back etc for the specific ones.

[erickt]

A bunch of languages done:

C++:

FrontInsertionSequence: (implemented by list, slist, deque)
push front: seq.push_front(x)
pop front: seq.pop_front()

BackInsertionSequence: (implemented by vector, list, deque)
push back: seq.push_back(x)
pop back: seq.pop_back()

Python:

list:
push front: list.insert(0, x)
push back: list.append(x)
pop front: list.remove(0, x)
pop back: list.pop()

collections.deque:
push front: deque.appendleft(x)
push back: deque.append(x)
pop front: deque.popleft()
pop back: deque.pop()

Java:

Array:

java.util.Collection:
push: collection.add(x)

java.util.List:
push front: list.add(0, x)
push back: list.add(x)
pop front: list.remove(0)
pop back: list.remove(ArrayList.size() - 1)

java.util.Stack:
push back’: stack.push(x)
pop back: stack.pop()

java.util.Queue:
push front: queue.add(x)
pop back: queue.remove()

java.util.Deque:
push front: deque.addFirst(x)
push back: deque.addLast(x)
pop front: deque.removeFirst()
pop back: deque.removeLast()

Javascript:

push front: array.unshift(x)
push back: array.push(x)
pop front: array.shift()
pop back: array.pop()

Scala:

Seq:
push front: x +=: buf
push back: buf += x
pop front: buf.remove(0)
pop back: buf.remove(buf.size - 1)

[glaebhoerl]

I like simple english words like append, prepend, remove_first, remove_last, etc.

[adrientetar]

I like the cpp names personally.

[erickt]

There's also the push_all/ extend style methods:

C++:
push front all: list.insert(list.begin(), x.begin(), x.end())  
push back all: list.insert(list.end(), x.begin(), x.end())

Java:
push back all: list.addAll(x)

Python:
push back all: list.extend(xs)

Scala:
push front all: buf ++=: xs
push back all: xs ++= buf

[ghost]

Is there any reason why we can't have all of the above? Qt has this kitchen-sink approach, it's really nice to not have to guess names.

[thestinger]

@Jurily: There's no need to guess names when you can just hit tab to get a list of the available methods, or look in the documentation. The idiomatic Rust style is to expose as few methods as necessary to provide all of the important functionality, with convenience wrappers for common cases.

[glaebhoerl]

@Jurily Many/most of the duplicated names in Qt only exist in order to be compatible with the STL and STL-conforming templates. Qt itself has its own preferences (which are generally in line with my own).

So for completeness's sake:

C++/Qt:

QList:
push front: list.prepend(x)
push back: list.append(x), list += x, list << x
pop front: list.removeFirst()
pop back: list.removeLast()
push back all: list.append(xs), list += xs, list << xs

QVector:
push front: vec.prepend(x)
push back: vec.append(x), vec += x, vec << x
pop front: vec.removeFirst()
pop back: vec.removeLast()
push back all: vec += xs, vec << xs

QLinkedList:
push front: list.prepend(x)
push back: list.append(x), list += x, list << x
pop front: list.removeFirst()
pop back: list.removeLast()
push back all: list += xs, list << xs

We're still missing C#.

[erickt]

@glehel: Here's C#:

IList:
push front: v.Insert(0, x)
push back: v.Add(x)
pop front: v.RemoveAt(0, x)
pop back: v.RemoveAt(v.Count(), x)

ArrayList: (include IList)
push front all: v.InsertRange(0, collection)
push back all: v.InsertRange(v.Count(), collection)

Queue:
push front: q.Enqueue()
pop back: q.Dequeue()

Stack:
push back: s.Push()
pop back: s.Pop()

[nikomatsakis]

I think I like push/pop to stay as they are and to remove shift/unshift. For shift/unshift you can use insert/remove with an integer argument. I believe this is analogous to what Java does and I never found it especially painful.

[nikomatsakis]

Well I guess Java calls it add or append or something like that. Oh well. I still like it. :)

[erickt]

@nikomatsakis: I'd be fine with that decision. If we do that, then I would suggest that deque-like structures should then get a special python-ish push_front/pop_front and keep push/pop for operations at the end of the structure. So that'd work out to be:

trait MutableSeq<T> {
    fn push(&mut self, t: T);
    fn pop(&mut self) -> Option<T>;
    fn insert(&mut self, idx: uint, t: T);
    fn remove(&mut self, idx: uint) -> Option<T>;
    ...
}

trait MutableDeque<T>: MutableSeq<T> {
    fn push_front(&mut self, t: T);
    fn pop_front(&mut self) -> Option<T>;
    ...
}

Although MutableSeq could be broken up some more. I'm tempted to copy C++ STL and have a FrontInsertionSeq and BackInsertionSeq, but that might be getting a little silly.

Also, before anyone implements this, I've got a WIP patch that implements most of this, so I'll take care of doing any renaming if/when we decide what to rename.

[TeXitoi]

#10852 (comment)

I really like this proposition. I think having push and pop being the fastest add and remove an element is great. It can be some Queue trait, including most of the classical collection as stacks and extra::priority_queue will propose that trait.

[brson]

Nominiting. These naming convention issues need to get resolved.

[pnkfelix]

Accepted for 1.0, P-backcompat-libs.

[lilyball]

I like @erickt's proposal. It preserves familiar naming, keeps the common push operation with a very short name, and gives a hint as to which operations are considered fast and which may not be.