Extra bound makes compiler fail recognizing types as equal

Experimenting with improving the fmap crate (see also Playing with non_lifetime_binders), I came across this curious compilation issue:

use std::collections::HashSet;
use std::hash::Hash;

pub trait FunctorTyCon<'a> {
    type Type<T>: ProtoFunctor<'a, Inner = T, TyCon = Self>
    where
        T: 'a;
}

pub trait ProtoFunctor<'a> {
    type Inner: 'a;
    type TyCon: FunctorTyCon<'a, Type<Self::Inner> = Self>;
}

pub trait Functor<'a, T>
where
    Self: ProtoFunctor<'a, TyCon = Self::TyCon_>,
    T: 'a,
{
    type TyCon_: FunctorTyCon<'a, Type<Self::Inner> = Self>
    // Uncommenting this line makes the test below fail to compile:
    //    + FunctorTyCon<'a, Type<T> = Self::Mapped>
        ;
    type Mapped: Functor<'a, T>;
    fn fmap<F>(
        self,
        f: F,
    ) -> <Self::TyCon as FunctorTyCon<'a>>::Type<T>
    where
        F: 'a + Send + FnMut(Self::Inner) -> T;
}

pub struct Vec_;

impl<'a> FunctorTyCon<'a> for Vec_ {
    type Type<T> = Vec<T>
    where
        T: 'a;
}

impl<'a, T> ProtoFunctor<'a> for Vec<T>
where
    T: 'a,
{
    type Inner = T;
    type TyCon = Vec_;
}

impl<'a, A, B> Functor<'a, B> for Vec<A>
where
    A: 'a,
    B: 'a,
{
    type TyCon_ = Vec_;
    type Mapped = Vec<B>;
    fn fmap<F>(self, f: F) -> Self::Mapped
    where
        F: 'a + Send + FnMut(Self::Inner) -> B,
    {
        self.into_iter().map(f).collect::<Vec<B>>()
    }
}

pub struct HashSet_;

impl<'a> FunctorTyCon<'a> for HashSet_ {
    type Type<T> = HashSet<T>
    where
        T: 'a;
}

impl<'a, T> ProtoFunctor<'a> for HashSet<T>
where
    T: 'a,
{
    type Inner = T;
    type TyCon = HashSet_;
}

impl<'a, A, B> Functor<'a, B> for HashSet<A>
where
    A: 'a + Eq + Hash,
    B: 'a + Eq + Hash,
{
    type TyCon_ = HashSet_;
    type Mapped = HashSet<B>;
    fn fmap<F>(self, mut f: F) -> Self::Mapped
    where
        F: 'a + Send + FnMut(Self::Inner) -> B,
    {
        let mut set = HashSet::with_capacity(self.len());
        for item in self {
            set.insert(f(item));
        }
        set
    }
}

#[test]
fn test_vec() {
    fn foo<'a, T>(functor: T) -> T // T::Mapped
    where
        T: Functor<'a, u8, Inner = u8>,
    {
        functor.fmap(|x| (x * 2) as u8)
    }
    assert_eq!(foo(vec![4u8, 7, 9]), vec![8, 14, 18]);
    let mut set = HashSet::new();
    set.insert(15);
    let set = foo(set);
    assert!(set.len() == 1);
    assert!(set.contains(&30));
}

(Playground)

Another problem (that may or may not be related): Applicative functors: Compiler hangs when adding a bound.

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.