How to turn this generic function into a trait method that returns an iterator

help
#1

I have this generic function:

pub fn chain<'a, Head, Tail, HeadItem, TailItem>(
    head: Head, tail: Tail
) -> impl Iterator<Item = &'a str> + 'a
where
    Head: IntoIterator<Item = &'a TailItem> + 'a,
    Tail: IntoIterator<Item = &'a HeadItem> + 'a,
    HeadItem: AsRef<str> + ?Sized + 'a,
    TailItem: AsRef<str> + ?Sized + 'a,
{
    head.into_iter().map(|v| v.as_ref()).chain(tail.into_iter().map(|v| v.as_ref()))
}

It allows me to do the following:

fn f() {
    let a: Vec<String> = vec!["1".to_string(), "2".into()];
    let b: Vec<&str> = dbg!(chain(&a, ["A", "B"]).collect()); // 1, 2, A B
    let c: Vec<String> = b.iter().map(|s| s.to_string()).collect();
    dbg!(chain(&["A", "B"], &a).collect::<Vec<&str>>()); // A, B, 1, 2
    dbg!(chain(&c, &a).collect::<Vec<&str>>()); // 1, 2, A, B, 1, 2
}

As an exercise, I'd like to turn this function into a trait that will allow me to do things like ["a", "b"].chain(&vec):

pub trait Chain<Tail, /* possibly more generics */>
/* where clauses */
{
    type Output;
    fn chain(&self, tail: Tail) -> Self::Output;
}
// TODO: impl Chain for &[&str], &[String], &Vec<&str>, &Vec<String> etc. to allow these:
fn g() {
    let a: Vec<String> = vec!["1".to_string(), "2".into()];
    dbg!(a.chain(["A", "B"]).collect::<Vec<&str>>()); // 1, 2, A, B
    dbg!(a.chain(&a).collect::<Vec<&str>>()); // 1, 2, 1, 2
    dbg!(["A", "B"].chain(&a).collect::<Vec<&str>>()); // A, B, 1, 2
    dbg!(["A", "B"].chain(["1", "2"]).collect::<Vec<_>>()); // A, B, 1, 2
}

This is my attemp. But I am having difficulty to figure out the Self::Output type in the impl because of the .map() calls.

Appreciate your help and thanks in advance.

#2

Pragmatically, use a boxed trait object. In the future, you can use impl trait and avoid the allocation. For this case, however:

    type Output =
        StdChain<
            Map<Self::IntoIter, fn(&SelfItem) -> &str>, 
            Map<Tail::IntoIter, fn(&TailItem) -> &str>,
        >;
    fn chain(&self, tail: Tail) -> Self::Output {
        let h = self.into_iter().map(SelfItem::as_ref as fn(&SelfItem) -> &str);
        let t = tail.into_iter().map(TailItem::as_ref as fn(&TailItem) -> &str);
        h.chain(t)
    }

See also:

2 Likes
#3

Note that while you can avoid an allocation by specifying the type in this case, by using fn pointers instead of closures, you're still adding some indirection that the optimizer may or may not see through. (Just something we have to live with for now.)

I think you had some missing ?Sized bounds too; here's a playground with both approaches.

1 Like
#4

First of all, thanks. I wish I could select more than one replies as solution.

While we are at it, I have one more question on the use of _ as a type placeholder in the following line copied from your solution:

        let h = self.into_iter().map(<SelfItem as AsRef<str>>::as_ref as _);

If I am understanding it correctly, the compiler is able to infer type of _ as fn(&SelfItem) -> &str, then why do we need the second as? In other words, why is this not working?

        let h = self.into_iter().map(<SelfItem as AsRef<str>>::as_ref);
#5

Thanks very much. These SO links are very helpful to me.

#6

For context, in case you didn't know, functions have their own, zero-sized type that's not a function pointer. You can't name them, similar to closures. That's why there's no indirection when you use them, but there is once you convert it to a function pointer.

With this:

let h = self.into_iter().map(<SelfItem as AsRef<str>>::as_ref);

There's enough information on the line itself for Rust to know all of the types involved, and it just doesn't look forward far enough to realize that it will need to be a fn pointer. It creates something with the type of the fn item instead. After it's decided, it doesn't try to backtrack and try something else once the mismatch is detected. Perhaps it will work automatically some day, but it doesn't today.

So if you remove the as _, you get

62 |         h.chain(t)
   |         ^^^^^^^^^^ expected fn pointer, found fn item

And the "fn item" is that zero-sized unnameable function type I mentioned.

With this:

let h = self.into_iter().map(<SelfItem as AsRef<str>>::as_ref as _);

The placeholder as _ tells the compiler, "I want to coerce this into something else, but you figure out what that is for me." It can't figure out what that is from the line alone. So the compiler just holds on to it when first encountered, so it can try to figure it out later.

Incidentally, if the compiler runs into a return value at the top level that can coerce to the required type:

fn f<T: AsRef<str> + ?Sized>() -> fn(&T) -> &str {
    <T as AsRef<str>>::as_ref
}

then it will do so. But if the type that needs to coerce is nested inside sometihng else, it won't. There are only a few "coercion-propagating expressions". So you can sometimes get away without coercing things explicitly, but often need to do so when the type to coerce is nested inside something else.

3 Likes
#7

Now it makes sense to me. Really appreciate the thorough and detailed answer. Many thanks.