> No, it's easy to get right in any specific case. It's iterating over a dang list, it's the first thing you learn how to do as a programmer. It's only hard to get right if you're trying to solve it for every use case with a single interface.
Isn't any correct implementation of any function that retains any only the elements that pass some predicate going to have to do basically the same thing that reject! does, or else be slow (creating a new list instead of mutating in place)?
I guess there's a somewhat simpler implementation that would work for some use cases (those in which order is not important) that just swaps in the last element instead of removing. But if maintaining order is important the complexity is similar.
I think that what would happen if Ruby didn't include reject! is that most programmers would just needlessly create new arrays all the time, since that's easier to write.
> [won't] any function that retains ... elements that pass some predicate going to have to do basically the same thing that reject! does ...?
Well, possible things you might want that still fall under the banner of "in-place reject":
- single slice at the end, vs atomic iterations as the article stated
- traversing the list in different directions, or according to priority
- aborting part way through
- any of a million domain concerns
If you rolled your own iteration, you have a platform for handling any of these. If you used a library, even the standard library, you need to start over from scratch, and either build your own iteration anyway, or find another library.
The exception to this is something like Haskell where the abstractions of the abstractions are modelled in the type system, so you never have to start anything over you just bisect your types and reassign responsibilities around the wound.
it might be quite fast, but it's never going to be as fast as a mutable version of the same thing. there are plenty of cases where you have many (millions?) of elements and want to remove only a few. in that case, copying an array of many elements for the sake of immutability is quite wasteful
*edit: i say never, but if you do cool stuff with referencing array ranges so that you don't copy, but reference the unchanged parts of the previous array then sure, but that's more of a low level feature of the language (eg erlang and clojure both do this i thiiiink?) than something you'd want to implement in a library because it can be suuuuper tricky to get right
No one does immutability with copying, that would be a joke. There is also nothing tricky about not copying full lists on append at userland lib, just more advanced data structures.
Yes, it won't be as fast in modifying. But it will be a lot faster in other operations, so it's a trade off and you chose appropriately for your use case.
Plus, it's a lot easier to read and understand "immutable code".
I'm going to assume this bottlenecked-by-mem-alloc work isn't Ruby.
The rule of thumb I personally go by is that if you're working in e.g. Ruby or Python it's better to favor immutability over mutability because mem alloc will almost never be the problem.
I say this having worked on a Python (pypy) product where mem alloc WAS the bottleneck in a particular area. So I know it's not always true, but almost always. Probably preaching to the choir here :)
Isn't any correct implementation of any function that retains any only the elements that pass some predicate going to have to do basically the same thing that reject! does, or else be slow (creating a new list instead of mutating in place)?
I guess there's a somewhat simpler implementation that would work for some use cases (those in which order is not important) that just swaps in the last element instead of removing. But if maintaining order is important the complexity is similar.
I think that what would happen if Ruby didn't include reject! is that most programmers would just needlessly create new arrays all the time, since that's easier to write.