How do I return a Filter iterator from a function?

Question

I want something like that:

fn filter_one<'a, T: Int>(input: &'a Vec<T>) -> ??? {
    input.iter().filter(|&x| x == Int::one())
}

What's the return type of that function? (I want to return the Iterator)

(I hope this isn't too obvious, I've been trying for half an hour now and am just starting to get frustrated :p )

EDIT:

I tried to follow the instructions from here => playpen link

the compiler gives me the following error:

<anon>:5:1: 7:2 error: the trait `core::kinds::Sized` is not implemented for the type `for<'r> core::ops::Fn(&'r T) -> bool + 'a`
<anon>:5 fn filter_one<'a, T: Int>(input: &'a Vec<T>) -> Filter<&T, Iter<'a, T>, Fn(&T) -> bool>{
<anon>:6     input.iter().filter(|&x| x == Int::one())
<anon>:7 }
<anon>:5:1: 7:2 note: required by `core::iter::Filter`
<anon>:5 fn filter_one<'a, T: Int>(input: &'a Vec<T>) -> Filter<&T, Iter<'a, T>, Fn(&T) -> bool>{
<anon>:6     input.iter().filter(|&x| x == Int::one())
<anon>:7 }
<anon>:5:1: 7:2 error: the trait `for<'r> core::ops::Fn(&'r &'a T) -> bool` is not implemented for the type `for<'r> core::ops::Fn(&'r T) -> bool + 'a`
<anon>:5 fn filter_one<'a, T: Int>(input: &'a Vec<T>) -> Filter<&T, Iter<'a, T>, Fn(&T) -> bool>{
<anon>:6     input.iter().filter(|&x| x == Int::one())
<anon>:7 }
<anon>:5:1: 7:2 note: required by `core::iter::Filter`
<anon>:5 fn filter_one<'a, T: Int>(input: &'a Vec<T>) -> Filter<&T, Iter<'a, T>, Fn(&T) -> bool>{
<anon>:6     input.iter().filter(|&x| x == Int::one())
<anon>:7 }
error: aborting due to 2 previous errors
playpen: application terminated with error code 101

How do I tell rustc that Fn(&T) -> bool is Sized??

Answer 1

Unfortunately, it is impossible to return iterators which depend on closures (specifically closures, functions will work fine; see below), like the ones returned by filter() or map() adapters. Here's why.

This is the signature of filter() iterator extension method:

fn filter<P>(self, predicate: P) -> Filter<A, Self, P> where P: FnMut(&A) -> bool

Note that the closure argument accepts any type which implements FnMut trait. That's right, most if not all of the standard libraries have recently been switched to use unboxed closures instead of old boxed ones.

This signature means, however, that if you specify a closure as an argument to filter(), just like you do in filter_one():

input.iter().filter(|&x| x == Int::one())

then after monomorphization of this particular call P will become some anonymous unnamed type generated by the compiler. Because it is unnamed, naturally, you can't specify it in type signatures, consequently, you also cannot specify a type of an iterator which depends on unboxed closure - you just wouldn't know what to write as the third argument to Filter<A, I, P>.

You can work around this by using a function instead of a closure, which should be sufficient for your use case:

use std::slice::Items;
use std::iter::Filter;
use std::num::Int;

fn filter_one<T: Int>(input: &[T]) -> Filter<&T, Items<T>, fn(&&T) -> bool> {
    fn equal_to_one<U: Int>(&&x: &&U) -> bool { x == Int::one() }
    input.iter().filter(equal_to_one::<T>)
}

fn main() {
    let v = [1i, 2, 3];
    let r: Vec<int> = filter_one(v.as_slice()).map(|x| *x).collect();
    println!("{}", r);
}

Note that I also have changed &Vec<T> to &[T] - you should never use &Vec<T> because it needlessly limits flexibility of your code.

For more general case of closures, however, it is impossible to do this without abstract return types. There is a proposal to add them, but it was postponed until after 1.0.

Answer 2

Rust 1.26

fn filter_one(input: &[u8]) -> impl Iterator<Item = &u8> {
    input.iter().filter(|&&x| x == 1)
}

fn main() {
    let nums = vec![1, 2, 3, 1, 2, 3];
    let other: Vec<_> = filter_one(&nums).collect();
    println!("{:?}", other);
}

Rust 1.0

fn filter_one<'a>(input: &'a [u8]) -> Box<Iterator<Item = &'a u8> + 'a> {
    Box::new(input.iter().filter(|&&x| x == 1))
}

fn main() {
    let nums = vec![1, 2, 3, 1, 2, 3];
    let other: Vec<_> = filter_one(&nums).collect();
    println!("{:?}", other);
}

This solution requires additional allocation. We create a boxed trait object. Here, the size of the object is always known (it's just a pointer or two), but the size of the object in the heap does not need to be known.

As Vladimir Matveev points out, if your predicate logic doesn't need any information from the environment, you can use a function instead of a closure:

use std::{iter::Filter, slice::Iter};

fn filter_one<'a>(input: &'a [u8]) -> Filter<Iter<u8>, fn(&&u8) -> bool> {
    fn is_one(a: &&u8) -> bool {
        **a == 1
    }

    input.iter().filter(is_one)
}

fn main() {
    let nums = vec![1, 2, 3, 1, 2, 3];
    let other: Vec<_> = filter_one(&nums).collect();
    println!("{:?}", other);
}