HKTs in Rust (well, kind of)

hkts.rs

trait Functor {
    type A;
    type F<B>;

    fn fmap<B>(self, f: impl Fn(Self::A) -> B) -> Self::F<B>;
}

impl<T> Functor for Option<T> {
    type A = T;
    type F<B> = Option<B>;

    fn fmap<B>(self, f: impl Fn(Self::A) -> B) -> Self::F<B> {
        self.map(f)
    }
}

impl<T, E> Functor for Result<T, E> {
    type A = T;
    type F<B> = Result<B, E>;

    fn fmap<B>(self, f: impl Fn(Self::A) -> B) -> Self::F<B> {
        self.map(f)
    }
}

impl<T> Functor for Vec<T> {
    type A = T;
    type F<B> = Vec<B>;

    fn fmap<B>(self, f: impl Fn(Self::A) -> B) -> Self::F<B> {
        self.into_iter().map(f).collect()
    }
}

trait Applicative: Functor {
    fn pure(v: Self::A) -> Self;

    fn ap<B>(self, fns: Self::F<impl Fn(Self::A) -> B>) -> Self::F<B>;
}

impl<T> Applicative for Option<T> {
    fn pure(v: Self::A) -> Self {
        Some(v)
    }

    fn ap<B>(self, fns: Self::F<impl Fn(Self::A) -> B>) -> Self::F<B> {
        match fns {
            None => None,
            Some(f) => self.map(f),
        }
    }
}

impl<T, E> Applicative for Result<T, E> {
    fn pure(v: Self::A) -> Self {
        Ok(v)
    }

    fn ap<B>(self, fns: Self::F<impl Fn(Self::A) -> B>) -> Self::F<B> {
        match fns {
            Err(e) => Err(e),
            Ok(f) => self.map(f),
        }
    }
}

impl<T> Applicative for Vec<T>
where
    Self: Clone,
{
    fn pure(v: Self::A) -> Self {
        vec![v]
    }

    fn ap<B>(self, fns: Self::F<impl Fn(Self::A) -> B>) -> Self::F<B> {
        fns.iter()
            .flat_map(|f| self.clone().into_iter().map(f))
            .collect()
    }
}

trait Monad: Applicative {
    fn bind<B>(self, f: impl Fn(Self::A) -> Self::F<B>) -> Self::F<B>;
}

impl<T> Monad for Option<T> {
    fn bind<B>(self, f: impl Fn(Self::A) -> Self::F<B>) -> Self::F<B> {
        self.and_then(f)
    }
}

impl<T, E> Monad for Result<T, E> {
    fn bind<B>(self, f: impl Fn(Self::A) -> Self::F<B>) -> Self::F<B> {
        self.and_then(f)
    }
}

impl<T> Monad for Vec<T>
where
    T: Clone,
{
    fn bind<B>(self, f: impl Fn(Self::A) -> Self::F<B>) -> Self::F<B> {
        self.into_iter().flat_map(f).collect()
    }
}

#[test]
fn test() {
    let opt = Some(1);
    assert_eq!(opt.fmap(|x| x + 1), Some(2));
    let v = vec![1, 2, 3];
    assert_eq!(v.fmap(|x| x + 1), vec![2, 3, 4]);

    let opt1 = Option::pure(1);
    let opt2 = Option::pure(2);

    let fns = |x: u32| move |y: u32| x + y;
    assert_eq!(opt2.ap(opt1.fmap(fns)), Some(3));

    let v1 = vec![1, 2, 3];
    let v2 = vec![1, 2, 3];

    let fns = |x: u32| move |y: u32| x * y;
    assert_eq!(v2.ap(v1.fmap(fns)), vec![1, 2, 3, 2, 4, 6, 3, 6, 9]);

    let v1 = vec![1, 2, 3];
    let v2 = vec![1, 2, 3];

    assert_eq!(
        v1.bind(|x1| v2.clone().bind(|x2| Applicative::pure((x1, x2)))),
        vec![
            (1, 1),
            (1, 2),
            (1, 3),
            (2, 1),
            (2, 2),
            (2, 3),
            (3, 1),
            (3, 2),
            (3, 3)
        ]
    )
}