Add {min,max}_set(_by{_key)?)? functions #323

zayenz · 2018-12-11T15:50:56Z

The function min_set returns a Vec of all the minimum values. All variants for max and with key extraction and comparison functions are added also.

Since the functions need to return an unknown number of values and the values are not known until the iterator is finished, the function needs to allocate memory. Therefore Vec is used for returning the values. From the guidelines for itertools, this also makes it unlikely to be included in the standard library.

The reason for adding these functions is that I often find situations where I want to know all the minimum values.

The naming is not optimal; min_set indicates that a set is returned while a Vec is returned. Another name is all_min, but I think that is less explanatory and not as discoverable. YMMV.

While an empty Vec could be used to handle the case of an empty iterator, I think that it is more safe to push that check into the type-system.

zayenz · 2019-01-11T12:37:34Z

Just wondering if there is any interest in this feature?

fenhl · 2019-07-14T10:10:29Z

I would find this feature useful, although wrapping in Option seems like a strange decision, as Vec methods that require elements to be present already return Option. I foresee many more and_then chains in my code if this is merged as is.

phimuemue

The functionality sounds great! I appreciate that you already considered min/max and by/by_key.

Overall, I think we could try to be a bit simpler and generic in some places.

phimuemue · 2019-07-20T22:19:05Z

src/extrema_set.rs

+
+    for element in it {
+        let key = key_for(&element);
+        if lt(&element, &result[0], &key, &current_key) {


Would it make sense to replace lt (returning bool) by cmp (returning Ordering) so that we could avoid the second call to lt in line 23?

That should work nicely.

As it is, I essentially copied the structure from the minimax set of functions, where I see now that multiple comparisons are also made.

I'm happy to make the change, but will probably not have the time to do so in the next couple of weeks (currently on vacation).

Ah, I see. That didn't occur to me when I looked at minmax last time. I could, however, imagine that things are a bit more complicated there because it needs to look for minimum and maximum simultaneously.

Maybe I should go back and have a look at minmax.

I had a look at minmax and think that it needs to do more stuff since it searches for both the minimum and the maximum. Here, I think we can use less calls to compare elements.

phimuemue · 2019-07-20T22:21:30Z

src/extrema_set.rs

+/// Implementation guts for `min_set`, `min_set_by`, and `min_set_by_key`.
+pub fn min_set_impl<I, K, F, L>(mut it: I,
+                                mut key_for: F,
+                                mut lt: L) -> Option<Vec<I::Item>>


What do you think about returning an empty Vec instead of None? I think it would make things a bit more clear, especially since the types do not indicate that a Some always contains a non-empty vector.

Do you think we could/should be a bit more generic than Vec here? I.e. should we try to be like collect (which returns something FromIterator<Self::Item> and lets the caller choose)?

I personally think that returning an Option is a good choice. In application code that I write, when using max or min functionality of sequences, an empty sequence is often an indication that something has gone awry and should be forced to be handled in another way. I imagine that in most cases, the Option-ness can be handled by the ?-operator. Also, it matches the signature for max/min from the standard library, which returns an Option of an Item. I can naturally change it, but I do think that Option makes sense here.

As for why Vec and not some kind of iterator. The number of results is unknown before computing the result, and the result is unknown before going through the whole input iterator, which implies that some kind of temporary storage area is needed. Since the data is already in a Vec, I thought that the least convoluted thing was to just give the user back that. We can of course wrap the already constructed Vec in something that exposes it like a FromIterator, I have no real opinion here.

Regarding the Vec: I naively thought about substituting the whole Vec even within the implementation (basically allowing to customize the kind of temporary storage), so that no conversion would be required upon returning it.

However, I see that FromIterator alone is possibly a bit too narrow to acchieve that. Maybe any container satisfying Default + Extend or FromIterator + Extend could be used?

Since the code by neccesity (unless double iteration is used) provisionally accumulates an unbounded number of result items, and discards these when a new provisionally best results is found, something more than FromIterator + Extend would be needed AFAIK.

My guess would be that anything that also has the possibility to clear the results is no better than the interal Vec, and would also be less clear. I'd be glad to learn I'm wrong though!

src/extrema_set.rs

phimuemue · 2019-07-20T22:34:39Z

src/lib.rs

+    /// assert_eq!(a.iter().min_set(), Some(vec![&1, &1, &1, &1]));
+    /// ```
+    ///
+    /// The elements can be floats but no particular result is guaranteed


To be honest, I often run into situations where I like to simply compare floats. But most of the time, I am happy that Rust tells me that f64 is not Ord.

Iterator::min also requires Ord. Do you think we should stick to that requirement and require the caller to resolve the float issues?

I agree, floats not being Ord is annoying, but also great.

In this case, I again copied the style and wording from minmax.

zayenz · 2019-07-21T06:40:31Z

I would find this feature useful, although wrapping in Option seems like a strange decision, as Vec methods that require elements to be present already return Option. I foresee many more and_then chains in my code if this is merged as is.

See my reply here: #323 (comment)

src/extrema_set.rs

The function min_set returns a Vec of all the minimum values. All variants for max and with key extraction and comparison functions are added also. Since the functions need to return an unknown number of values and the values are not known until the iterator is finished, the function needs to allocate memory. Therefore Vec is used for returning the values.

phimuemue · 2021-08-20T13:06:04Z

@zayenz Do you want to drive this to completion? (No worries if your answer is "no".)

If so, could you:

Make the returned type simply a Vec? (No Option to denote emptiness.)
Have the relevant functions require Ord? (Instead of PartialOrd; we can relax the constraints later if actually needed.)
Avoid duplicate calls to lt by accepting a FnMut(...)->Ordering in min_set_impl?
Resort to internal iteration (using fold/for_each instead of a manual for-loop)?

zayenz · 2021-08-20T13:41:16Z

@phimuemue I'd forgotten about this one. Yes, I would like to fix this as I think the methods are quite useful.

I will take a look at updating the code, and then seeing about the changes mid next week.

phimuemue · 2022-05-04T20:57:52Z

Hi @zayenz, thanks for this! I did some changes on top of your proposal, and moved the PR to #613.

613: Minmax set (prev "Add {min,max}_set(_by{_key)?)? functions") r=jswrenn a=phimuemue This PR supersedes #323 (I did not know how I could amend to the original PR, so sorry for the "duplicate" PR here.) The original PR by `@zayenz` looked rather good. I adjusted the stuff that came up during discussion back then: * Teturn type `Vec` instead of `Option` - emptiness is sufficiently well represented by `Vec`. * Functions require `Ord` instead of `PartialOrd` - just as `Iterator::min`. * Avoid duplicate calls to `lt` by accepting a `FnMut(...)->Ordering` - seems canonical compared to the `bool`-solution. * Use internal iteration instead of a manual `for`-loop. Moreover, I simplified some bits. Co-authored-by: Mikael Zayenz Lagerkvist <zayenz@gmail.com> Co-authored-by: philipp <descpl@yahoo.de>

zayenz force-pushed the feature/extrema-set branch 2 times, most recently from 0eb8bf3 to 65444a9 Compare December 11, 2018 16:03

zayenz force-pushed the feature/extrema-set branch from 65444a9 to feea621 Compare July 11, 2019 11:37

jswrenn self-assigned this Jul 18, 2019

jswrenn added the waiting-on-review label Jul 18, 2019

phimuemue reviewed Jul 20, 2019

View reviewed changes

phimuemue reviewed Aug 11, 2019

View reviewed changes

src/extrema_set.rs Show resolved Hide resolved

zayenz force-pushed the feature/extrema-set branch from feea621 to 7a7d8c1 Compare October 5, 2019 14:00

phimuemue added waiting-on-author and removed waiting-on-review labels Aug 20, 2021

phimuemue mentioned this pull request May 4, 2022

Minmax set (prev "Add {min,max}_set(_by{_key)?)? functions") #613

Merged

phimuemue closed this May 4, 2022

jswrenn added this to the 0.10.4 milestone Jun 21, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add {min,max}_set(_by{_key)?)? functions #323

Add {min,max}_set(_by{_key)?)? functions #323

zayenz commented Dec 11, 2018

zayenz commented Jan 11, 2019

fenhl commented Jul 14, 2019

phimuemue left a comment

phimuemue Jul 20, 2019

zayenz Jul 21, 2019

phimuemue Jul 21, 2019 •

edited

phimuemue Aug 11, 2019

phimuemue Jul 20, 2019

phimuemue Jul 20, 2019

zayenz Jul 21, 2019

phimuemue Jul 21, 2019

zayenz Aug 4, 2019

phimuemue Jul 20, 2019

zayenz Jul 21, 2019

zayenz commented Jul 21, 2019

phimuemue commented Aug 20, 2021

zayenz commented Aug 20, 2021

phimuemue commented May 4, 2022 •

edited

Add {min,max}_set(_by{_key)?)? functions #323

Add {min,max}_set(_by{_key)?)? functions #323

Conversation

zayenz commented Dec 11, 2018

zayenz commented Jan 11, 2019

fenhl commented Jul 14, 2019

phimuemue left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

phimuemue Jul 21, 2019 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

zayenz commented Jul 21, 2019

phimuemue commented Aug 20, 2021

zayenz commented Aug 20, 2021

phimuemue commented May 4, 2022 • edited

phimuemue Jul 21, 2019 •

edited

phimuemue commented May 4, 2022 •

edited