In Rust trait, should `pop` return a value?

[scotts]

@hirzel brought this up in a PR:

I think pop should not return anything. I can see from the implementation of some of the aggregation algorithms that it lowers the oldest item and returns that. There are two problems with that. First, it is wasteful to do the lowering if that return value gets discarded by the caller. Second, and more importantly, not all aggregation algorithms hold on to that oldest item, so it is unavailable to be lowered and returned. Specifically, Two-Stacks Lite and DABA Lite don't keep around singleton partials for the front portion of the queue, since that portion is optimized for eviction, where it makes more sense to keep around partials for larger sublists.

I had a similar reaction when @segeljakt first designed FifoWindow. The main reason for doing it is that is lines up with Rust conventions. Regarding point 1, I don't think it's a major concern: if the return value of pop is unused, and the call to pop itself is inlined, dead-code elimination should avoid any overhead (even the call to lower should go away).

Point 2 is more of a concern, but I admit I don't fully follow it. Is the problem that in some cases, the partial result from the thing being evicted is nonsensical to return?

[hirzel]

Consider this example for Two-Stacks Lite, from page 7 of the arXiv paper:

When we pop "c", the data structure does not contain anything that is just "c". And returning "cd..g" is arbitrary as well as inconsistent with how other algorithms would behave.

[scotts]

Yes, agreed, I understand now. I will submit a PR soon which changes the trait so that pop does not return a value.