How to accept any function parameter that has iter()

I've this function:

fn combinations(nums: &BTreeSet<usize>) -> Vec<(usize, usize)> {
    let nums = Vec::from_iter(nums.iter());
    let mut res = Vec::new();

    for width in 1..nums.len() {
        for i in width..nums.len() {
            res.push((*nums[i - width], *nums[i]));
        }
    }
    res
}

I'd like to generalize this function such it is not limited to accepting BTreeSet, and can be called with anything that can be turned into an Iterator. I tried with using a generic parameter T: IntoIterator, but I still couldn't invoke iter() on the argument.

You just need to take any IntoIterator:

fn foo<I>(iter: I)
where
    I: IntoIterator<Item = usize>,
{}

If you want a version which works with &usize you'll have to write something like:

fn foo<'a, I>(iter: I)
where
    I: IntoIterator<Item = &'a usize>,
{}
2 Likes

You can use T: IntoIterator<Item = usize>, and use .into_iter() on the argument. To use it from a reference, the user can call combinations(collection.iter().copied()).

This requires the caller to call iter(), which I'm trying to avoid.

No, IntoIterator is generally implemented for both the the container itself and for a reference to that container.

For example .zip(&vec) works fine (as long as the yielded Item are coherent).

Playground

2 Likes

The problem is, you can't use &vec directly if you also want to accept owned collections, since &Vec<usize>: IntoIterator<Item = &usize>, not IntoIterator<Item = usize>. @bruce-wayne, the most general form is to use T: IntoIterator, and to avoid .iter() on the caller's end would require decreasing the flexibility.

I went with this answer because either way, the caller is having to call iter(), so, I don't want to impose another copied call. Thank you.

The way to say “type T is a collection of Foo that has an .iter() method” in Rust is: for<'a> &'a T: IntoIterator<Item = &'a Foo>; because all (standard library) types with an .iter() methods will have that particular IntoIterator implementation. I.e. your code generalizes directly into

use std::collections::BTreeSet;

fn combinations<T>(nums: &T) -> Vec<(usize, usize)>
   where
       for<'a> &'a T: IntoIterator<Item = &'a usize>,
{
    let nums = Vec::from_iter(nums.into_iter()); // need to write `into_iter`
    let mut res = Vec::new();

    for width in 1..nums.len() {
        for i in width..nums.len() {
            res.push((*nums[i - width], *nums[i]));
        }
    }
    res
}

fn it_works(nums: &BTreeSet<usize>) -> Vec<(usize, usize)> {
    combinations(nums)
}

Note that the .into_iter() call works on the &T in this case, so it is equivalent to using the (convenience-method) .iter() for concrete types.

Suggestions, to generalize this further to T: IntoIterator<Item = &'a usize> get rid of the “higher-ranked trait bound” with for, which means you will no longer be able to iterate over the argument nums: T more than one time. (Unless you specify, say, T: Copy.), but since you don’t do this anyway, generalizing like this is an option, and it will mean you can accept types like – say – [&usize; 10], too.

use std::collections::BTreeSet;

fn combinations<'a, T>(nums: T) -> Vec<(usize, usize)>
   where
       T: IntoIterator<Item = &'a usize>,
{
    let nums = Vec::from_iter(nums.into_iter()); // need to write `into_iter`
    let mut res = Vec::new();

    for width in 1..nums.len() {
        for i in width..nums.len() {
            res.push((*nums[i - width], *nums[i]));
        }
    }
    res
}

fn it_works(nums: &BTreeSet<usize>) -> Vec<(usize, usize)> {
    combinations(nums)
}

fn it_works2() -> Vec<(usize, usize)> {
    combinations([&1, &2, &3, &4, &5, &6, &7, &8, &9, &10])
}

Generalizing even further to accept owned collections of usize or &usize or borrowed collections of usize is possible, too, e.g. using a Borrow<usize> bound on the item type.

use std::collections::BTreeSet;
use std::borrow::Borrow;

fn combinations<T>(nums: T) -> Vec<(usize, usize)>
   where
       T: IntoIterator,
       T::Item: Borrow<usize>,
{
    // now a Vec<usize> instead of Vec<&usize>, so the code changed slightly
    // alternatively, you could have created a `Vec<T>` and added the '.borrow()` calls
    // further down below in the code
    let nums = Vec::from_iter(nums.into_iter().map(|i| *i.borrow()));
    let mut res = Vec::new();

    for width in 1..nums.len() {
        for i in width..nums.len() {
            res.push((nums[i - width], nums[i]));
        }
    }
    res
}

fn it_works(nums: &BTreeSet<usize>) -> Vec<(usize, usize)> {
    combinations(nums)
}

fn it_works2() -> Vec<(usize, usize)> {
    combinations([&1, &2, &3, &4, &5, &6, &7, &8, &9, &10])
}


fn it_works3() -> Vec<(usize, usize)> {
    combinations([1, 2, 3, 4, 5])
}

Another side-note on such generic functions: If you write something generic like this in production code, especially if the logic is more involved than in this example, you could often consider introducing an as-small-as-possible convenience-layer “outer” function that uses the generic interface to then call a less generic helper function internally. This way, you can avoid code duplication of the core logic.

use std::collections::BTreeSet;
use std::borrow::Borrow;

fn combinations<T>(nums: T) -> Vec<(usize, usize)>
   where
       T: IntoIterator,
       T::Item: Borrow<usize>,
{
    // non-generic function used internally,
    // this code doesn’t need to be duplicated for every choice of
    // `T` and `T::Item` anymore, at the “expense” of adding one function-call
    fn combinations_of_vec(nums: Vec<usize>) -> Vec<(usize, usize)> {
        let mut res = Vec::new();
    
        for width in 1..nums.len() {
            for i in width..nums.len() {
                res.push((nums[i - width], nums[i]));
            }
        }
        res
    }
    combinations_of_vec(Vec::from_iter(nums.into_iter().map(|i| *i.borrow())))
}
5 Likes

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.