rustidioms

How to stop a call to map if nested find returns None?


I have the following struct:

struct Thing {
    id: usize,
    cost: u32,
    numbers: Vec<usize>
}

I am considering the following three Thing objects and a vector chain_of_things that contains some Ids:

let some_things = [
    Thing { id: 0, cost: 10, numbers: vec![1, 2] },
    Thing { id: 1, cost: 15, numbers: vec![3] },
    Thing { id: 2, cost: 20, numbers: vec![0, 1] },
    Thing { id: 3, cost: 5, numbers: vec![1] }
];
let chain_of_things = [0, 1, 3];

Note that for convenience, the Ids of the Things in the vector some_things coincide with their position in the vector. A pair (thing_1, thing_2) is feasible, if the id of thing_2 is contained in thing_1.numbers.

The task is to find out if the given chain_of_things is feasible, meaning that for every index i the pair (some_things[chain_of_things[i]], some_things[chain_of_things[i+1]]) must be feasible. If the chain is feasible, I want to return the sum of the costs of the things. Otherwise, I want to return an error.

Solving this task using a for loop is trivial. I want to solve it using a call to map and inside if a call to find. My approach so far looks as follows:

let mut cost = some_things[chain_of_things[0]].cost;

let results: Vec<_> =
    chain_of_things[..chain_of_things.len() - 1]
        .iter()
        .enumerate()
        .map(|(index, thing_id)| {
            if let Some(number) = some_things[*thing_id].numbers
                .iter()
                .find(|&&x| {x == chain_of_things[index + 1] })
            {
                cost += some_things[chain_of_things[index + 1]].cost;
                cost
            }
            else {
                u32::MAX
            }
        }).collect();

This works but has multiple drawbacks:

  1. I need to iterate over the result vector to search for a MAX value to determine if all pairs were feasible.
  2. The map iterator does not stop as soon as the first non-feasible pair is found.

How do I achieve a behavior that circumvents the mentioned drawbacks?

My question seems to be related to: How do I stop iteration and return an error when Iterator::map returns a Result::Err?

I think the solution there is to have an extra find function that returns a Result<T, E>. But the find function I'm calling returns an Option<T>. I could write my own find function but it would only wrap the Option<T> and somehow convert it into a Result<T, E> which seems overkill.


Solution

  • This solution seems fairly idiomatic. You can add prints into map(|pair| ... line to verify that the chain is not processed further after encountering first bad pair.

    let chain_of_things = [0,1,3];
    let sum_cost = chain_of_things
        .map(|i| &some_things[i]) // get things by indices
        .windows(2) // iterate pairs in chain
        .map(|pair| pair[0].numbers
            .contains(&pair[1].id)
            .then_some(pair[1].cost)
        ) // get Some(cost) if feasible, else None
        .sum::<Option<u32>>() // Option implements Sum, stopping iteration on first None
        .map(|sum| sum + some_things[chain_of_things[0]].cost); // add first thing's cost
    
    println!("Answer: {:?}", sum_cost);