Can't Unify Super Generic Code

[Gankra]

I was trying to verify that the associated-items-based HKT described in the associated items RFC still worked. As best I know, I updated everything to work with today's stable Rust (1.7), but it fails out in unifying in the actual implementation of Mappable for Vec<T> (see the FIXME).

// The kind * -> *
trait TypeToType<Input> {
    type Output;
}

struct Vec_;

impl<T> TypeToType<T> for Vec_ {
    type Output = Vec<T>;
}

trait Mappable 
    where Self: Sized,
{
    type E;
    type HKT: TypeToType<Self::E, Output=Self>;

    fn map<F, O>(self, f: F) -> <Self::HKT as TypeToType<O>>::Output
        where F: FnMut(Self::E) -> O,
              Self::HKT: TypeToType<O>;
}

impl<T> Mappable for Vec<T> {
    type E = T;
    type HKT = Vec_;

    // FIXME: I won't unify `Vec_::Output = Vec<O>`!
    fn map<F, O>(self, mut f: F) -> <Self::HKT as TypeToType<O>>::Output
        where F: FnMut(Self::E) -> O,
              Self::HKT: TypeToType<O>
    {
        let r: Vec<O> = self.into_iter().map(&mut f).collect();
        r
    }

}


fn main() {
    let nums: Vec<u32> = vec![1, 2, 3, 4, 5, 6];
    let bools: Vec<bool> = nums.map(|x| x < 3);
}

[aturon]

cc @nikomatsakis

[jonas-schievink]

cc #30472 and #28994 (dupe?)

[aturon]

@jonas-schievink Yes, I think you're right -- the projection works if you define a helper like:

fn project<O>(v: Vec<O>) -> <Vec_ as TypeToType<O>>::Output {
    v
}

[aturon]

Actually, I was a bit too hasty: HRTBs are not clearly at fault here, since there's no lifetime involved in the FnMut where clause. I suspect it's related, but not identical to the other bugs.

[Gankra]

The full fix, to be clear:

fn project_vec<O>(v: Vec<O>) -> <Vec_ as TypeToType<O>>::Output {
    v
}

impl<T> Mappable for Vec<T> {
    type E = T;
    type HKT = Vec_;

    fn map<F, O>(self, mut f: F) -> <Self::HKT as TypeToType<O>>::Output
        where F: FnMut(Self::E) -> O,
              Self::HKT: TypeToType<O>
    {
        let r: Vec<O> = self.into_iter().map(&mut f).collect();
        project_vec::<O>(r)
    }

}

But this shouldn't be necessary.

[bstrie]

Triage: the given code still fails to compile as of Rust 1.41. Error message:

error[E0308]: mismatched types
  --> src/main.rs:33:9
   |
28 |     fn map<F, O>(self, mut f: F) -> <Self::HKT as TypeToType<O>>::Output
   |                                     ------------------------------------ expected `<Vec_ as TypeToType<O>>::Output` because of return type
...
33 |         r
   |         ^ expected associated type, found struct `std::vec::Vec`
   |
   = note: expected associated type `<Vec_ as TypeToType<O>>::Output`
                       found struct `std::vec::Vec<O>`
   = note: consider constraining the associated type `<Vec_ as TypeToType<O>>::Output` to `std::vec::Vec<O>` or calling a method that returns `<Vec_ as TypeToType<O>>::Output`
   = note: for more information, visit https://doc.rust-lang.org/book/ch19-03-advanced-traits.html