Using impl trait in trait implementation

I want to implement IntoIterator for a struct that I have written.
Implementing the iterator isn't too hard, and works through a long
iterator chain; the data is stored in a BTreeMap<_, BTreeSet<AnnotatedAxiom>>, so essentially I just have to squash it
down.

impl IntoIterator for AxiomMappedOntology {
    type Item = AnnotatedAxiom;
    type IntoIter = std::vec::IntoIter<AnnotatedAxiom>;
    fn into_iter(self) -> Self::IntoIter {
        let btreemap = self.index().axiom.into_inner();
        let v:Vec<AnnotatedAxiom> =  btreemap.into_iter()
            .map(|(_k,v)| v)
            .flat_map(BTreeSet::into_iter)
            .map(Rc::try_unwrap)
            .map(Result::unwrap).collect();
        v.into_iter()
    }
}

The problem is that I at the end of this chain I have to call
.collect() to get a Vec and then another into_iter, because this
gives me a predictable and usable type.

Of course, for this purpose impl trait was defined, but I can't work
out how to use that here, since I can't use impl trait in type
aliases.

type IntoIter = impl Iterator<Item=AnnotatedAxiom>;

Is there a work around here that I am not seeing? Best I have come up
with so far is to add a newtype struct with Box<dyn Iterator> inside.

At first sight I believe it's similar to this and this.

Sorry that I'm unable to answer with the code specific to your example. Since I lack the definition of your structure, I wouldn't have been able to verify that my code work. I give you instead a (tested) self-contained example that should be quite similar to what you need, so you can try to replicate it in your case.

This code requires a nightly version of the compiler, in order to have access to a feature that enables impl Trait in associated types.

#![feature(type_alias_impl_trait)]

struct CombinationOfIteratorAdaptors<I: IntoIterator<Item = i32>>(I);

impl<I: IntoIterator<Item = i32>> IntoIterator for CombinationOfIteratorAdaptors<I> {
    type Item = i32;
    type IntoIter = impl Iterator<Item = i32>;

    fn into_iter(self) -> Self::IntoIter {
        self.0
            .into_iter()
            .skip(5)
            .filter(move |x| *x % 2 == 0)
            .map(|x| x + 100)
    }
}

fn main() {
    for x in CombinationOfIteratorAdaptors(vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) {
        println!("{:?}", x);
    }
}

I learnt this technique from this answer.

If you don't want to use nightly, I think your options are to use function pointer / boxed functions or manually implementing the Iterator trait for a new custom type that you create which replicates all the work of those map and flat_map.

My struct is big and nasty, but as you say, it doesn't really matter. type_alias_impl_trait was the best that I could see, but I don't really want to move to nightly, although giving that this has taken me three years so far, perhaps I should worry less about this.

I may test my solution (everything into a Vec first and Box<dyn Iterator> to see which is slower, or wait till impl trait types come out, if there is no workaround.

Actually, since in map/flat_map you only use functions and not closures

you might be able to get around it by explicitly naming the return type using function pointers

Map<Map<...>, fn(Option<T>) -> T>

so everything is static (just very ugly to read).

Function pointers are an option, though they will be introducing dynamic function calls.

I’ve created some version using type_alias_impl_trait that is better than the simple impl Iterator<Item = AnnotatedAxiom>:

#![feature(type_alias_impl_trait)]
impl IntoIterator for AxiomMappedOntology {
    type Item = AnnotatedAxiom;
    type IntoIter = iter::Map<
        iter::FlatMap<
            btree_map::IntoIter<SomeKey, BTreeSet<Rc<AnnotatedAxiom>>>,
            btree_set::IntoIter<Rc<AnnotatedAxiom>>,
            impl FnMut(
                (SomeKey, BTreeSet<Rc<AnnotatedAxiom>>),
            ) -> btree_set::IntoIter<Rc<AnnotatedAxiom>>,
        >,
        impl FnMut(Rc<AnnotatedAxiom>) -> AnnotatedAxiom,
    >;
    fn into_iter(self) -> Self::IntoIter {
        let btreemap = self.index().axiom.into_inner();
        btreemap
            .into_iter()
            .flat_map(|(_k, v)| v.into_iter())
            .map(|x| Rc::try_unwrap(x).unwrap())
    }
}

(playground)

This version has the advantage that you also get instances for things like FusedIterator or (probably) even DoubleEndedIterator. And everything that might be added in the Future.

(replacing both of the impl FnMut(..) -> .. above with fn(..) -> .. will by the way give you the function pointer version)

Is it because you are explicit about the outer layers? Shouldn't the type system be able to automatically infer that the returned impl Iterator is actually a Map<FlatMap<_,_,_>,_>?

The compiler will know. It will (.. at least I believe it will) still not let you (or rather the users of your impl) use any of the extra trait impls like FusedIterator, so that you can change the actual type behind the impl without it being a breaking change. Now that I’m thinking about it, it probably would be even nicer to just explicitly list the traits such as impl Iterator<...> + FusedIterator + ... so that your implementation can still change.

2 Likes

Also, I'm a bit confused why with only one map works, while with two maps it doesn't, complaining about getting closures instead of the expected function pointers.

Oh what an idiot I am. Of course!

Ah this is very clever! Of course, while being allowed to change the implementation, it could be difficult to keep up with the additional promises...

The problem is that the type inference is (apparently, for some reason) not smart enough to pin down the nested type to a function pointer (so that it introduces the correct cast). This works. This works, too.

1 Like

Oh... I think it's time for me to go to bed. I feel a bit confused. I would have never thought about casting a pure closure (one without state) to a function pointer. Even if it makes a lot of sense now that you mention it.

Now that you revealed the trick, this second alternative does not come as a surprise :smiley:

The standard library usually creates a new type and implements Iterator (and DoubleEndedIterator/ExactSizeIterator/FusedIterator if applicable) for it.

In your case, I would implement Iterator with the next and size_hint methods, and FusedIterator. It's more boilerplate than using type_alias_impl_trait on nightly, though.

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.