Tracking issue for {min,max} on iterators

[alexcrichton]

This is a tracking issue for the unstable iter_cmp feature in the standard library. This is the ability to get the min or max elements out of an iterator via a custom closure for comparisons.

Some open questions are:

• Is _by the right suffix here? The stable <[T]>::sort_by function has a different signature than these two functions, so these may want to change suffix to something like min_with.
• Is it useful to compare with a closure from &A to B? Lifetimes could perhaps get in the way where interior references to A could not be returned (e.g. comparing by just the String name of a person, not their height as well).

[nagisa]

Is _by the right suffix here?

Haskell uses by as well, if that has any weight.

[nagisa]

Used min_by/max_by today. Very useful addition.

[alexcrichton]

Nominating for discussion in 1.6

[aturon]

I'm in favor of stabilizing something here, but don't want to keep the _by suffixes with these signatures (given that sort_by is stable).

[malbarbo]

Agree with @aturon.

[alexcrichton]

🔔 This issue is now entering its cycle-long final comment period for stabilization 🔔

The libs team discussed this and the conclusion was to stabilize this via one of two routes:

1. Change these functions to match sort_by where the closure takes two arguments and ranks them.
2. Rename these functions to have a different suffix and retain the existing semantics.

We're a little up in the air about which of these should be done, but I would personally lean towards option (1) to have the closure take two arguments.

[cuviper]

I like the existing semantics better, because it reduces how many times the comparison keys must be computed, in case that's an expensive thing to produce. But I can also appreciate the lifetime issues of trying to key interior references.

Can we just have both flavors? (min_by for comparison functions, min_with for key functions)

[aturon]

@cuviper We discussed having both flavors at the libs meeting, and there is general support for the idea, but I worry that there will be a paper cut around which of _by and _with to use. If we can come up with a really evocative name, say min_ranked or something, then I'd be in favor of supporting both.

[alexcrichton]

One note brought up by @huonw is that we could also have something like:

struct Rank2Compare<F>(F);

impl<A, B, F> FnMut(A, A) -> Ordering for Rank2Compare<F> 
    where F: FnMut(A) -> B, B: Ord
{ /* ... */ }

iter.min_by(|a, b| a.field1.cmp(&b.field1));
iter.min_by(Rank2Compare(|a| &a.field1));

Which is to say that the "compare a and b" function is the most general, so we could build up "min by via a ranking function" on top with a special comparator. Note that the name "Rank2Compare" is pretty awful, and there may not be a fantastic name for this :)

[cuviper]

How about min_by_key/min_by_rank, then min_by is "by whatever, you order it." (matching sort_by)

"Rank" is weird to me here, but maybe I'm just used to Python's min(..., key=...).

[aturon]

@cuviper _by_key and _by sound great to me!

[huonw]

Haskell calls Rank2Compare "comparing", which flows kinda nicely iter.min_by(comparing(|x| &x.field1)). (This approach works naturally with, say, sort_by, without requiring an extra function there too.)

One downside to the .min_by(comparing(...)) approach is one has to recompute the key/rank of the minimum each time, whereas a specialised min_by_key can be more efficient by storing it.

[fenhl]

I agree that max_by and min_by should match sort_by for consistency, but coming from Python, comparing by a key seems like a more intuitive approach. What would it take to also get {max,min,sort}_by_key functions added?

[BurntSushi]

I agree that we should have {min,max}_by methods to match sort_by. I know I personally get a paper cut with the as_ref/by_ref naming, so it would be nice to avoid that here! Adding {min,max,sort}_by_key seems harmless/low mental burden, but the additional functions seem unfortunate.

[alexcrichton]

This was discussed in the libs team triage today and the decision was to stabilize with the _by_key suffixes here.

[aturon]

After our team discussion, I was feeling a bit suspicious about the signature:

fn min_by<B, F>(self, f: F) -> Option<Self::Item> where B: Ord, F: FnMut(&Self::Item) -> B

As @alexcrichton points out in the original issue, it's not obvious that you can return interior references here (e.g. projecting out a component of a struct), because the return type B does not scope over the borrow of &Self::Item (which would require HKT).

And, in fact, this is largely the case -- although in some cases an iterator over references is able to do such a projection:

fn main() {
    let v = vec![(0, vec![0, 1])];
    // this is OK -- the use of `iter` means there's a layer of reference
    // internally whose lifetime you can use for the output reference.
    v.iter().min_by(|v| &v.1); 

    // for some reason, this doesn't work:
    // v.iter().min_by(|v| v); 
    // v.iter().min_by(|v| &*v);     

    // this is not OK, no internal reference:
    // v.into_iter().min_by(|v| &v.1); 
}

This is unfortunate, but I think should not block stabilization; we just don't have a way to allow both extracting interior references and computing new owned values. Perhaps with HKT there will be a backcompat way to add this functionality later.

[malbarbo]

@aturon

v.iter().min_by(|v| a);
v.iter().min_by(|v| &*a);

the type of a is &&Vec, which appears to not implement Ord. Its strange because &T implements Ord if T does, so &A with A=&T should implement Ord, maybe this is a bug? Anyway, *a solve this case.

I don't know how to deal with the example v.into_iter().min_by(|v| &v.1), which is a valid use case.

[alexcrichton]

The methods max_by_key and min_by_key are now stable, so closing.