[solved] Largest item in a possibly empty vector (without early return)

tl;dr: ok, I already solved this while writing this post and before posting, but I've decided to still post it in the hopes that someone maybe, possibly, pretty please(?) would actually find this useful. :slight_smile: Don't read this if you're not a beginner - to save your time.


In rustbook's generics chapter there is an example of extracting a function that finds the largest item(of i32 type there) in a vector. It eventually looks like this:

fn largest(list: &[i32]) -> i32 {
    let mut largest = list[0];

    for &item in list.iter() {
        if item > largest {
            largest = item;
        }
    }

    largest
}

fn main() {
    let number_list = vec![34, 50, 25, 100, 65];

    let result = largest(&number_list);
    println!("The largest number is {}", result);

    let number_list = vec![102, 34, 6000, 89, 54, 2, 43, 8];

    let result = largest(&number_list);
    println!("The largest number is {}", result);
    
    let number_list = vec![]; //FIXME: How handle this case?!

    let result = largest(&number_list);
    println!("The largest number is {}", result);
}

I notice their example does not handle empty vectors, probably because it's not relevant to the point they're trying to make in that context and thus are trying to keep things simple. But it would be really nice to mention that in the text.

For learning purposes I attempted to find a way to handle that case (when the vector is empty) and ran into some trouble.

The simple/easy way that works seems to be this(playground):

fn largest(list: &[i32]) -> Option<i32> {
    if list.is_empty() {
        return None;
    }
    let mut largest = list[0];

    for &item in list.iter() {
        if item > largest {
            largest = item;;
        }
    }

    Some(largest)
}

But I'm interested in the other ways too (for learning purposes!).
One way that I want to see if can work, is without using ifs and without returning early if the vector is empty, therefore I've the following non-working code(because vec::get(index) returns an Option<&i32> instead of Option<i32> thus I have to somehow reference the local variable item when setting largest (??) ):

fn largest(list: &[i32]) -> Option<&i32> {
    let mut largest:Option<&i32> = list.get(0);

    for &item in list.iter() {
        if item > *largest.unwrap() {  
            largest = Some(&item);
        }
    }

    largest
}

error[E0515]: cannot return value referencing local variable 'item'
playground link

How could I make this work?
Since this is for learning purposes, I'd appreciate small hints instead of full solution :smiley: unless it simply can't be done, then I need to know as such.

Oh, this is ridiculous: I just found the solution(playground):

fn largest(list: &[i32]) -> Option<&i32> {
    let mut largest:Option<&i32> = list.get(0);

    for item in list.iter() {
        if item > largest.unwrap() {
            largest = Some(item);
        }
    }

    largest
}

It's weird because for item in list.iter() used to not work before (in 2017) (on second thought, it worked just not without changing the rest of the code), and yet that link explains why:
in for item in list.iter() , item is actually an &i32 ie. a reference to an i32
in for &item in list.iter() , item is actually an i32 ie. an i32 (moved out from vec)

Ok, this is a bit unclear to me due to possibly implicity Copy trait being at work here, so I'm re-doing the above with a non-Copy type:
ok it worked (playground)

#[derive(Debug, PartialOrd, PartialEq)]
struct NonCopyI32(i32);

fn largest(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
    let mut largest:Option<&NonCopyI32> = list.get(0);

    for item in list.iter() {
        if item > largest.unwrap() {
            largest = Some(item);
        }
    }

    largest
}

And here follows the non-working variant that shows that in for &item in list.iter() a NonCopyI32 element moves out of the vector (but if using just i32 instead, it would've just been copied, so non-obvious - to me) (playground):

#[derive(Debug, PartialOrd, PartialEq)]
struct NonCopyI32(i32);

fn largest(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
    let mut largest:Option<&NonCopyI32> = list.get(0);

    for &item in list.iter() {
        if item > *largest.unwrap() {
            largest = Some(&item);
        }
        //let a:u32=item; //to see type of `item`
    }

    largest
}

(to see how the above errors if the i32 type(or equivalent) were used instead, then only add , Copy, Clone to the derive line)

Well, this was fun! :slight_smile:

1 Like

just for fun i tried to put the for loop into a .iter().fold() and got it running.

fn largest(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
    list.iter().fold(None, |largest, item| match largest {
        // if `item` is bigger as `largest` return `item`
        Some(largest) if item > largest => Some(item),
        // else return `largest`
        largest @ Some(_) => largest,
        // first `item` return it
        None => Some(item),
    })
}

playground

it's even .unwrap() free

edit: add comments and playground.

1 Like

You're looking at the first element twice in this approach, so I encourage you to experiment more with other ways. For example, what if you just start with let mut largest = None;? (And also do smallest, since there's a weird trick that works for largest but not for smallest.)

1 Like

This is probably not what you had in mind (since it works for smallest too):

fn largest(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
    let mut largest: Option<&NonCopyI32> = None; //list.get(0);

    for item in list.iter() {
        if None == largest {
            largest = Some(item);
            continue;
        } else {
            if item > largest.unwrap() {
                largest = Some(item);
            }
        }
    }

    largest
}

because that seems somehow worse to have two if for each vec value instead of just one in the example that's checking first value twice.

I wonder if you expected me to use some iter methods perhaps not unlike fold in the above mind-boggling example by juggle-tux which took me a while to get :smiley:

May I get another hint? assuming this is mandatory: let mut largest = None;, but if it's not, then I've found this variant:

fn largest3(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
    let mut iterator = list.iter();
    let mut largest:Option<&NonCopyI32> = iterator.next(); // and skip first
    
    for item in iterator {
            if item > largest.unwrap() {
                largest = Some(item);
            }
    }

    largest
}

I have two other (worse)variants:

fn largest2_2(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
    //avoid checking first item twice
    let mut largest: Option<&NonCopyI32> = None; //list.get(0);

    for item in list.iter() {
        match largest {
            //this seems worse :)
            Some(x) if x < item => largest = Some(item),
            Some(_) => (),
            None => largest = Some(item),
        }
    }

    largest
}

//#[derive(Debug)]
fn largest2_3(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
    //avoid checking first item twice
    let mut largest: Option<&NonCopyI32> = None; //list.get(0);

    for item in list.iter() {
        match largest {
            Some(x) => if x < item { largest = Some(item) },
            None => largest = Some(item),
        }
    }

    largest
}

That's essentially what I was thinking, probably just using match largest { and Ord::max to shorten it somewhat.

Edit: Looks like you did the match update in one of the edits :slightly_smiling_face: I personally like the match version because it avoids the .unwrap, which is generally a good approach.

That's not what I was thinking, though it's certainly a good one. The standard library's implementation uses fold:

And you'll also see that it's using this trick you noticed:

This is one of the things I was thinking, though :+1:

For the trick one, notice that you can directly compare options: Option in std::option - Rust

Spoiler
#[derive(Ord, PartialOrd, Eq, PartialEq)]
struct NonCopyI32(i32);

fn largest2_3(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
    let mut largest = None;

    for item in list.iter() {
        largest = Some(item).max(largest);
    }

    largest
}
1 Like

Very interesting! I'm comparing Options:

fn largest4(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
    let mut iterator = list.iter();
    let mut largest: Option<&NonCopyI32> = iterator.next(); //skip first

    loop {
        let item = iterator.next();
        match item {
            None => break,
            i => {
                if i > largest {
                    largest = item;
                }
            }
        }
    }

    largest
}

Is there a better way to match against Some(_) and assign the matched to i ? The way I did it above requires None to be first!

you can do

match item {
    // if `item` is `Some(_)` assign `item` to `i`
    i @ Some(_) => {...}
}
1 Like

you are right i should have pointed out match guards and @ bindings

and maybe avoid name shadowing.

1 Like

Sweet! That's what I was looking for! (seemingly in the wrong places)

fn largest4_1(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
    let mut iterator = list.iter();
    let mut largest: Option<&NonCopyI32> = iterator.next(); //skip first

    loop {
        let item = iterator.next();
        match item {
            i @ Some(_) => {
                if i > largest {
                    largest = item;
                }
            }
            None => break,
        }
    }

    largest
}

I made a bunch of functions with "all" variants thus far on playground, but having trouble translating the easy solution(from OP) to NonCopyI32, that is, this one:

It's interesting how much Copy trait does(for the above), making me think it's "good"(or just generic enough?) code, but for a non-Copy type it needs to be changed (haven't figured out yet how)... if someone answers please hide it inside a spoiler :smiley: because I'm still at it. oh I just missed the return type should be a reference:

spoiler

playground

fn largest_1(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
    if list.is_empty() {
        return None;
    }
    let mut largest: &NonCopyI32 = &list[0];

    for item in list.iter() {
        if item > largest {
            largest = item;;
        }
    }

    Some(largest)
}

Oh thank you! I was about to ask where to find more help about those because looking in std docs wasn't yielding much. Chapter 19 woot! I'm only at 12 so far, but looking very much forward to it! :heart:

if the return type should be a owned value there is clone to get it a bit more generic.

1 Like

This is the easiest way to do it:

pub fn largest(list: &[i32]) -> Option<&i32> {
    list.iter().max()
}

If you think that is cheating, using Option::map() and Iterator::fold() can be elegant and efficient:

pub fn largest(list: &[i32]) -> Option<&i32> {
    let mut iter = list.iter();
    iter.next().map(|first| {
        iter.fold(first, |a, b| a.max(b))
    })
}
1 Like