8 ms·

I love this blog, but I'm not sure that I agree with this: > In my mind, I’d just rather not have a reject! at all, and callers who need to mutate an array in-

I love this blog, but I'm not sure that I agree with this: > In my mind, I’d just rather not have a reject! at all, and callers who need to mutate an array in-place can figure out how to do safely with respect to their own use cases. We ought to have a standard version of the reject! code precisely because it's so difficult to get right. Saying application developers should solve the problem themselves just sounds like some sort of political move: 'sure they may get the edge cases wrong, but then it will be their fault not ours'. One of the best things about Ruby is that having helper methods for every kind of possible operation frees application developers from re-solving these edge-case problems and allows them to just write their business logic.

erikpukinskis 10y ago
Edit: I know this sounds like I am trying to dismiss the problem. That's not my point. I'm trying to say the problem is compounded by the choice to bundle the solutions to several different problems. If people have criticisms I would love to read a reply. </Edit> > We ought to have a standard version of the reject! code precisely because it's so difficult to get right. 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. Essentially: you are taking two different algorithms and trying two switch between them behind a single interface. Meaty if-statements behind flags are an indication this is happening. It's cool of you want that but put it in a library and give it a GitHub per. An example: I don't use a library to merge attributes on objects. I cut and paste one of a few snippets or write from scratch. Sometimes you want to mutate an object, sometimes you want a copy, sometimes you want to shallow copy or keep a reference to the parent. I could write a nasty complicated function that intelligently solved "the problem". But all that does is bundle together a bunch of different solutions to different problems and make it hard for me to understand which one it picked. Edit 2: I could be persuaded that what I'm saying is just not Rubyish. I'm a JavaScript programmer (after many years of Ruby) so maybe there's some truth in that. I do think that distancing ourselves from the mechanics of list manipulation can be bad for our code quality.
- pcwalton 10y ago
  > 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.
  - STRML 10y ago
    In this case, perhaps mutability is the real problem. Array#filter is quite fast in JS and never mutates the array.
    - rickycook 10y ago
      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
      - elmigranto 10y ago
        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".
leereeves 10y ago
Rather than an edge case, I'd call this a case of trying to satisfy two incompatible goals: fast and internally consistent after each deletion. Either implementation will be a poor choice for some use cases (hence the bug reports about both).
- xg15 10y ago
  Couldn't you easily satisfy both goals by moving the "copy all elements not marked for deletion into a new array" code into a "finally" clause? If I remember correctly, that should ensure the code is executed even if the block contains a break. That said, I'd wager Ruby's strange way of handling breaks in blocks passed to functions is the real source of problems here.
  - phamilton 10y ago
    `..into a new array` is precisely what `reject` does. We're talking about `reject!` which modifies the existing array.
    - brandonbloom 10y ago
      xg15's comment still makes sense if you replace "copy all ..." with "slide the remaining elements down by the number of removed elements" to match the mutative behavior. However, a bigger problem is concurrent modification: What happens if your reject! predicate has a side effect which modifies the array? Ideally you'd receive a "ConcurrentModificationException" or the like.
      - leereeves 10y ago
        That would still require O(n) space (to store the list of elements to keep or remove) so why not simply use the regular `reject` ?
        brandonbloom 10y ago
        Because you're saving the O(N) time copy... iirc, Ruby's array doesn't expose the distinction between length and capacity, but internally it may decide to amortize the cost of such copies. For example, if reject only removes a small % of elements, it may choose not to shrink capacity.
catnaroek 10y ago
The problem with `reject!` is that it's too ad-hoc: the more fundamental operation is to filter the elements of a stream. The input stream could be generated from any data structure (not necessarily an array), and the output stream could similarly be redirected into any data structure (not necessarily an array, let alone physically the same array).
- marvy 10y ago
  Not clear what you're suggesting here. Can you implement reject! using your propose more general interface? If so, how? Is it more efficient than just creating a copy and then overwriting the original, like this? ary = ary.reject {|x| x > 2} If there's a language agnostic insight to be had here, I'd love to see it. Actually, even if it's language dependent, I'd like to see it.
  - catnaroek 10y ago
    Have something akin to C++'s `std::copy_if`. auto first = vec.begin(); auto last = vec.end(); last = std::copy_if(first, last, first, [](int x) { return x > 2; }); auto size = std::distance(first, last); vec.resize(size); (Ironically, in C++ this doesn't always work, because not all types are copyable or movable. But Ruby has no such problems.)
    - marvy 10y ago
      Okay, but with copy_if, you need an extra resize step at the end, which is annoying in C++ and that Ruby users currently have the luxury of avoiding. And this seems fundamental. The reason that copy_if can't call resize for you is that it assumes nothing about the underlying container; indeed there may not even be one. You say this is a good thing, and there are certainly advantages, but it doesn't seem to solve this problem, unless I'm missing something. Or maybe you're saying that the need to call resize is worth it, since you get a more general interface for the price?
      - catnaroek 10y ago
tomphoolery 10y ago
I think the argument here is to embrace the immutability of arrays in Ruby. The reason why this is called `reject!` rather than `reject` is because the designers of Ruby wanted you to favor returning new objects rather than mutating objects in place. Sure, you might need to do it from time-to-time and I'm really happy we have methods that enable such behavior, but this brings to mind the old adage "just because you can, doesn't mean you should". The author might have been trying to say in that quote that app developers should find other ways of solving whatever problem they have without resorting to mutating objects in place. I don't think we should go as far as to not include such methods in Ruby if everyone finds them useful from time-to-time, but I also think we should be staying away from mutating objects in place, rather than returning new versions of said objects and using that.
- rickycook 10y ago
  i wouldn't have said that the ! is there because the designers want you to favour immutable rather than mutable operations. it's there for the same reason confirmations are there for deleting files; they want to you be sure you know what you're doing, because the immutable operation is always safe while the mutable operation is sometimes unsafe. if the ! for mutable operations weren't there, people would often be very surprised by the behaviour of reverse, sort, etc because in languages like ruby (python, etc too) they expect things to be fairly safe by default. there are plenty of cases when mutating an object is far preferable to doing the same in an immutable way for both speed, and algorithmic complexity.
  - steveklabnik 10y ago
    Small Ruby conventions note: ! means "dangerous", not "mutable." Yeah, sometimes the kind of danger you're looking at is mutability, but it's a bit broader than that.
    - tamal 10y ago
      To expand, ! means it's a more dangerous version of the method without the ![0]. A method could be dangerous, but not have a safer counterpart, and thus be named without a !. [0] https://www.ruby-forum.com/topic/176830#773946 https://www.ruby-forum.com/topic/176830#773946
seanp2k2 10y ago
Yeah, I like ruby (and especially rails) because it has stuff like this. I also like that most languages have sort() as part of the stdlib. If you need something specific, sometimes they come with more than one sort, or it would be easy enough to write yourself, but I appreciate and expect a high-level language to include the basics so I don't need to keep data structures and algorithms books within reach. Rails, especially rails 5 with API-only mode is particularly great as well.

erikpukinskis 10y ago

Edit: I know this sounds like I am trying to dismiss the problem. That's not my point. I'm trying to say the problem is compounded by the choice to bundle the solutions to several different problems. If people have criticisms I would love to read a reply. </Edit> > We ought to have a standard version of the reject! code precisely because it's so difficult to get right. 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. Essentially: you are taking two different algorithms and trying two switch between them behind a single interface. Meaty if-statements behind flags are an indication this is happening. It's cool of you want that but put it in a library and give it a GitHub per. An example: I don't use a library to merge attributes on objects. I cut and paste one of a few snippets or write from scratch. Sometimes you want to mutate an object, sometimes you want a copy, sometimes you want to shallow copy or keep a reference to the parent. I could write a nasty complicated function that intelligently solved "the problem". But all that does is bundle together a bunch of different solutions to different problems and make it hard for me to understand which one it picked. Edit 2: I could be persuaded that what I'm saying is just not Rubyish. I'm a JavaScript programmer (after many years of Ruby) so maybe there's some truth in that. I do think that distancing ourselves from the mechanics of list manipulation can be bad for our code quality.

pcwalton 10y ago
> 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.
- STRML 10y ago
  In this case, perhaps mutability is the real problem. Array#filter is quite fast in JS and never mutates the array.
  - rickycook 10y ago
    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
    - elmigranto 10y ago
      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".

leereeves 10y ago

Rather than an edge case, I'd call this a case of trying to satisfy two incompatible goals: fast and internally consistent after each deletion. Either implementation will be a poor choice for some use cases (hence the bug reports about both).

xg15 10y ago
Couldn't you easily satisfy both goals by moving the "copy all elements not marked for deletion into a new array" code into a "finally" clause? If I remember correctly, that should ensure the code is executed even if the block contains a break. That said, I'd wager Ruby's strange way of handling breaks in blocks passed to functions is the real source of problems here.
- phamilton 10y ago
  `..into a new array` is precisely what `reject` does. We're talking about `reject!` which modifies the existing array.
  - brandonbloom 10y ago
    xg15's comment still makes sense if you replace "copy all ..." with "slide the remaining elements down by the number of removed elements" to match the mutative behavior. However, a bigger problem is concurrent modification: What happens if your reject! predicate has a side effect which modifies the array? Ideally you'd receive a "ConcurrentModificationException" or the like.
    - leereeves 10y ago
      That would still require O(n) space (to store the list of elements to keep or remove) so why not simply use the regular `reject` ?
      - brandonbloom 10y ago
        Because you're saving the O(N) time copy... iirc, Ruby's array doesn't expose the distinction between length and capacity, but internally it may decide to amortize the cost of such copies. For example, if reject only removes a small % of elements, it may choose not to shrink capacity.

catnaroek 10y ago

The problem with `reject!` is that it's too ad-hoc: the more fundamental operation is to filter the elements of a stream. The input stream could be generated from any data structure (not necessarily an array), and the output stream could similarly be redirected into any data structure (not necessarily an array, let alone physically the same array).

marvy 10y ago
Not clear what you're suggesting here. Can you implement reject! using your propose more general interface? If so, how? Is it more efficient than just creating a copy and then overwriting the original, like this? ary = ary.reject {|x| x > 2} If there's a language agnostic insight to be had here, I'd love to see it. Actually, even if it's language dependent, I'd like to see it.
- catnaroek 10y ago
  Have something akin to C++'s `std::copy_if`. auto first = vec.begin(); auto last = vec.end(); last = std::copy_if(first, last, first, [](int x) { return x > 2; }); auto size = std::distance(first, last); vec.resize(size); (Ironically, in C++ this doesn't always work, because not all types are copyable or movable. But Ruby has no such problems.)
  - marvy 10y ago
    Okay, but with copy_if, you need an extra resize step at the end, which is annoying in C++ and that Ruby users currently have the luxury of avoiding. And this seems fundamental. The reason that copy_if can't call resize for you is that it assumes nothing about the underlying container; indeed there may not even be one. You say this is a good thing, and there are certainly advantages, but it doesn't seem to solve this problem, unless I'm missing something. Or maybe you're saying that the need to call resize is worth it, since you get a more general interface for the price?
    - catnaroek 10y ago

tomphoolery 10y ago

I think the argument here is to embrace the immutability of arrays in Ruby. The reason why this is called `reject!` rather than `reject` is because the designers of Ruby wanted you to favor returning new objects rather than mutating objects in place. Sure, you might need to do it from time-to-time and I'm really happy we have methods that enable such behavior, but this brings to mind the old adage "just because you can, doesn't mean you should". The author might have been trying to say in that quote that app developers should find other ways of solving whatever problem they have without resorting to mutating objects in place. I don't think we should go as far as to not include such methods in Ruby if everyone finds them useful from time-to-time, but I also think we should be staying away from mutating objects in place, rather than returning new versions of said objects and using that.

rickycook 10y ago
i wouldn't have said that the ! is there because the designers want you to favour immutable rather than mutable operations. it's there for the same reason confirmations are there for deleting files; they want to you be sure you know what you're doing, because the immutable operation is always safe while the mutable operation is sometimes unsafe. if the ! for mutable operations weren't there, people would often be very surprised by the behaviour of reverse, sort, etc because in languages like ruby (python, etc too) they expect things to be fairly safe by default. there are plenty of cases when mutating an object is far preferable to doing the same in an immutable way for both speed, and algorithmic complexity.
- steveklabnik 10y ago
  Small Ruby conventions note: ! means "dangerous", not "mutable." Yeah, sometimes the kind of danger you're looking at is mutability, but it's a bit broader than that.
  - tamal 10y ago
    To expand, ! means it's a more dangerous version of the method without the ![0]. A method could be dangerous, but not have a safer counterpart, and thus be named without a !. [0] https://www.ruby-forum.com/topic/176830#773946 https://www.ruby-forum.com/topic/176830#773946

seanp2k2 10y ago

Yeah, I like ruby (and especially rails) because it has stuff like this. I also like that most languages have sort() as part of the stdlib. If you need something specific, sometimes they come with more than one sort, or it would be easy enough to write yourself, but I appreciate and expect a high-level language to include the basics so I don't need to keep data structures and algorithms books within reach. Rails, especially rails 5 with API-only mode is particularly great as well.