Implementing a trait for T and Iterator<Item=T>

Hi,

I'm trying to implement a trait Foo for both a type T: Bar, and for any I: Iterator<Item=T> where T: Bar. Basically:

use std::iter::Iterator;

trait Foo {}
trait Bar {}

impl<T: Bar> Foo for T {}
impl<I: Iterator<Item=T>, T: Bar> Foo for I {}

Is there a way to implement a trait both for a type T and any collection of T (it's this idea of "collection" that I'm trying to convey by using the Iterator trait)?

If the same type implements both Bar and Iterator<Item = T>, which impl should apply?

struct LittleDude;

impl Bar for LittleDude {}

impl Iterator for LittleDude {
    type Item = Self;
    fn next(&mut self) -> Option<Self::Item> {
        unimplemented!()
    }
}
3 Likes

Yeah, more details are needed to figure out how this should be expressed. One (almost certainly terrible) workaround would be something like this:

use std::iter::Iterator;

trait Foo {}
trait Bar {}

impl<T: Bar> Foo for T {}

struct Fooifier<T>(pub T);

impl Foo for Fooifier<T>
where
    T: Iterator,
    T::Item: Bar,
{}
2 Likes

I think the other way is totally reasonable, since there's already a "please turn this single item into an iterator that produces it" function: std::iter::once.

Thanks for the explanation. I kind of had a feeling of what the problem was but seeing it like this makes it obvious.

There is a technique for writing overlapping impls, but it has big tradeoffs:

  • It can be difficult to reason about
  • It will infect the signature of every generic function or trait that uses Bar
  • Ambiguous cases like @dtolnay's LittleDude will produce an awful error message for users

Basically, you add a dummy type parameter whose sole purpose is to disambiguate between the impls. (Playpen)

pub trait Bar {}
pub trait Foo<Disambig> {}

pub mod marker {
    pub enum Value {}
    pub enum Iter {}
}

impl<T: Bar> Foo<marker::Value> for T {}

impl<Ts> Foo<marker::Iter> for Ts
where
    Ts: IntoIterator,
    Ts::Item: Bar,
{}

In standard usage, the user does not need to worry about the type parameter, because type inference can deduce the type parameter so long as a type only has one impl of the trait.

// a Bar-implementing type
struct SimpleBar;

impl Bar for SimpleBar {}

fn function<Disambig, T>(_x: T)
where
    T: Foo<Disambig>,
{}

fn main() {
    // infers Disambig=marker::Value
    function(SimpleBar);
    // infers Disambig=marker::Iter
    function(vec![SimpleBar, SimpleBar, SimpleBar]);
}

If a type has multiple valid impls, you get this:

error[E0282]: type annotations needed
  --> src/main.rs:49:5
   |
49 |     function(LittleDude);
   |     ^^^^^^^^ cannot infer type for `Disambig`

Would I use it for this? Probably not. There's a reason why std::iter::once exists.

Some use cases where I have seen success with the technique though are:

  • Type-directed indexing. frunk uses the technique to let you pick an element of an HList by type. If there are multiple elements of the same type, though, you get an "inference error" due to the overlapping impls.
  • In my own codebase, I have an unsafe trait for casting newtyped indices embedded deep within types, which lets me write something like:
    let forces: &[(usize, BTreeMap<usize, Vec<V3>>)] = &forces[..];
    let forces: &[(usize, BTreeMap<Atom, Vec<V3>>)] = index_cast(forces);
    let forces: &[(Atom, BTreeMap<Atom, Vec<V3>>)] = index_cast(forces);
    
    It has the limitation that only one index can be changed at a time; if I tried to go straight from the first line to the third, I would get an inscrutible error message.
    My code is not yet public, but here is the trait in question.
1 Like