How to return the result of a call to filter_map

Question

Here I have a vector vec of (char, usize) pairs, and I want to write a function

fn take_lt(&'a vec, cutoff: usize) -> Iterator<'a, char>

which returns an iterator over the chars matching values less than cutoff.

1. Is there a way to do this without the overhead of allocating something to heap (ie boxing up a Fn environment or creating another vector)?
2. Is there a way to do this
   without having to explicitly write out the hideous associated return type?

After trying this many different ways (a couple of which compiled, but all of which involved heap allocation which I'd like to avoid), I came up with:

use std::iter::repeat;
use std::iter::FilterMap;
use std::iter::Zip;
use std::iter::Repeat;
use std::slice;

fn take_lt<'a>(vec: &'a[(char, usize)], cutoff: usize) -> FilterMap<Zip<slice::Iter<'a, (char, usize)>, Repeat<usize>>, &fn((&(char, usize), usize)) -> Option<char>> {
    fn cmp_fun((&(x, a), b): (&(char, usize), usize)) -> Option<char> {
        if a < b {
            Some(x)
        } else {
            None
        }
    }
    vec.iter().zip(repeat(cutoff)).filter_map(&cmp_fun)
}

This is close, but I get:

src/lib.rs:15:47: 15:55 error: mismatched types:
 expected `&fn((&(char, usize), usize)) -> core::option::Option<char>`,
    found `&fn((&(char, usize), usize)) -> core::option::Option<char> {take_lt::cmp_fun}`
(expected fn pointer,
    found fn item) [E0308]
src/lib.rs:15     vec.iter().zip(repeat(cutoff)).filter_map(&cmp_fun)
                                                            ^~~~~~~~

A little googling suggests I try casting the function item to a function pointer, as in:

vec.iter().zip(repeat(cutoff)).filter_map(&(cmp_fun as fn((&(char, usize), usize)) -> Option<char>))

but that fails with:

src/lib.rs:15:49: 15:103 error: borrowed value does not live long enough
src/lib.rs:15     vec.iter().zip(repeat(cutoff)).filter_map(&(cmp_fun as fn((&(char, usize), usize)) -> Option<char>))
                                                              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
src/lib.rs:7:167: 16:2 note: reference must be valid for the lifetime 'a as defined on the block at 7:166...
src/lib.rs: 7 fn take_lt<'a>(vec: &'a[(char, usize)], cutoff: usize) -> FilterMap<Zip<slice::Iter<'a, (char, usize)>, Repeat<usize>>, &fn((&(char, usize), usize)) -> Option<char>> {
src/lib.rs: 8     fn cmp_fun((&(x, a), b): (&(char, usize), usize)) -> Option<char> {
src/lib.rs: 9         if a < b {
src/lib.rs:10             Some(x)
src/lib.rs:11         } else {
src/lib.rs:12             None
              ...
src/lib.rs:7:167: 16:2 note: ...but borrowed value is only valid for the block at 7:166
src/lib.rs: 7 fn take_lt<'a>(vec: &'a[(char, usize)], cutoff: usize) -> FilterMap<Zip<slice::Iter<'a, (char, usize)>, Repeat<usize>>, &fn((&(char, usize), usize)) -> Option<char>> {
src/lib.rs: 8     fn cmp_fun((&(x, a), b): (&(char, usize), usize)) -> Option<char> {
src/lib.rs: 9         if a < b {
src/lib.rs:10             Some(x)
src/lib.rs:11         } else {
src/lib.rs:12             None
              ...

Answer 1

Each function has a unique, distinct type, that is compatible with an fn type. This mirrors the fact that closures also have distinct types. This is what the compiler means by found fn item: it didn't find the fn type you specified in the return type, but rather the unique type of the cmp_fun function.

fn types are already pointers, so there's no need (at least in your situation) to take a reference to an fn; you can just take an fn directly. By doing this, the compiler will implicitly cast the function to the more general fn type.

fn take_lt<'a>(vec: &'a[(char, usize)], cutoff: usize) -> FilterMap<Zip<slice::Iter<'a, (char, usize)>, Repeat<usize>>, fn((&(char, usize), usize)) -> Option<char>> {
    fn cmp_fun((&(x, a), b): (&(char, usize), usize)) -> Option<char> {
        if a < b {
            Some(x)
        } else {
            None
        }
    }
    vec.iter().zip(repeat(cutoff)).filter_map(cmp_fun)
}

Answer 2

You were close:

// type alias for the return type (optional, I just find it a bit
// optically easier to work with). I added:
// a 'a lifetime parameter that ties the return Iter lifetime to the 
// input slice
// a 'static lifetime for the function pointer
type RetTake<'a> = FilterMap<Zip<slice::Iter<'a, (char, usize)>, 
    Repeat<usize>>, &'static fn((&(char, usize), usize)) -> Option<char>>;

fn take_lt<'a>(vec: &'a[(char, usize)], cutoff: usize) -> RetTake {
    fn cmp_fun((&(x, a), b): (&(char, usize), usize)) -> Option<char> {
        if a < b {
            Some(x)
        } else {
            None
        }
    }

    // I think this explicit static binding 
    // used not to be necessary, but I now can't get rustc
    // to give the reference to the function pointer the static lifetime
    // it needs otherwise 
    static F: fn((&(char, usize), usize)) -> Option<char> = cmp_fun;
    vec.iter().zip(repeat(cutoff)).filter_map(&F)
}

as an alternative you can create your own struct implementing the iterator logic you need and returning that struct. For instance:

struct CutoffIterator<'a> {
    iter: slice::Iter<'a, (char, usize)>,
    cutoff: usize,
}

impl<'a> Iterator for CutoffIterator<'a> {
    type Item = char;

    fn next(&mut self) -> Option<char> {
        loop {
            match self.iter.next() {
                Some(&(x, a)) if a < self.cutoff => return Some(x),
                Some(&(_, a)) if a >= self.cutoff => continue,
                _ => return None
            }
        }
    }
}

fn take_lt2(vec: &[(char, usize)], cutoff: usize) -> CutoffIterator {
    CutoffIterator { iter: vec.iter(), cutoff: cutoff }
}