I don't understand this line of code

Hi, I try to understand the Rust example from this page

http://rosettacode.org/wiki/Convex_hull#Rust

I struggle to understand this line

        .min_by(|lhs, rhs| lhs.1.x.partial_cmp(&rhs.1.x).unwrap())

I assume that lhs means left hand side and rhs means right hand side. But why does the closure has two parameters? Where does the second parameter came from?

As far as I understand this code .enumerate() returns a tuple with a number and the corresponding point. Maybe I'm already wrong at this point.

This code involves iterators. The method in question is Iterator::min_by. The .enumerate() method creates an iterator of tuples. The min_by method finds the “minimum” item, it’s a variant of the Iterator::min method, but it doesn’t require an Ord implementation. Instead it expects a closure that serves as an ad-hoc implementation of a Ord::cmp-style function. Hence the signature is the same as Ord::cmp, i.e. fn(&T, &T) -> Ordering where T is the type of the item.

In this particular case, points.iter().enumerate() is an iterator of (usize, &Point) pairs, the |lhs, rhs| lhs.1.x.partial_cmp(&rhs.1.x).unwrap() now compares these (usize, &Point) items by considering their Point's x-coordinate only (which is an f32 value).

The two arguments are two items of the iterator that ought to be compared. The min_by method will operate by going through the whole iterator linearly and always keeping track of the item that’s currently minimal among all the visited items so far. For each new item, hence the currently minimal item needs to be compared to the new item to see if perhaps that new item is smaller. In order to do this, min_by will call the provided closure and determine the ordering relation of these two items based on the result of type Ordering.

2 Likes

So min_by() loops over the iterator by itself (there is no for loop, foreach or next) and lhs is the current element and rhs is the next element of the iterator

in the next iteration lhs is consumed, rhs becomes lhs and the next item becomes rhs

min_by() returns a Result of the minimal value which is unpacked by .expect()

Is that correct so far?

Yes. Its actual implementation (currently) uses fold internally.

the only happens if the previous rhs was actually found to be smaller than the previous lhs. Otherwise previous lhs and new lhs stay the same. Also note that the documentation doesn’t really guarantee the exact calls to cmp, in particular the arguments could also be flipped, that’s an implementation detail. The closure is – basically – expected to behave according to the rules/axioms specified in the Ord/PartialOrd docs, i.e. for the closure f, it expects, for all values x, y and z:

  • calling f(&x, &y) is deterministic (always produces the same result only depending on x/y), at least for the duration of the min_by() call/iteration, and for the elements of the iterator
  • f(&x, &y) == f(&y, &x).reverse()
  • f(&x, &x) == Ordering::Equal
  • if f(&x, &y).is_le() && f(&y, &z).is_le(), then f(&x, &z).is_le() must be true as well

It’s an Option, but other than that basically, yes. None should only happen for an empty iterator.


One equivalent, but direct implementation of min_by (for simplicity written as a free-standing function, not a method) would be the following

use std::cmp::Ordering;

fn min_by<T>(
    mut iter: impl Iterator<Item = T>,
    mut cmp: impl FnMut(&T, &T) -> Ordering,
) -> Option<T> {
    // initially, the first item is the “current minimum”
    let mut current_min = iter.next()?; // returns None if the iterator is empty
    for item in iter {
        // If both are comparing “equal”, keep the current minimum.
        // Only if the next item is comparing as (strictly) “smaller”
        // (i.e. the current minimum is (strictly) “greater”)
        // update the current minimum accordingly.
        if cmp(&current_min, &item) == Ordering::Greater {
            current_min = item
        }
    }
    Some(current_min)
}
3 Likes

Thanks for your explanation. I think now I get it.

Have a nice weekend

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.