Playing with GATs, transformers, and more

abonimable-snoyman.rs

#![feature(generic_associated_types)]
#[allow(dead_code)]

trait Functor {
    type Unwrapped;
    type Wrapped<B>: Functor;

    fn map<F, B>(self, f: F) -> Self::Wrapped<B>
    where
        F: FnMut(Self::Unwrapped) -> B;
}

impl<A> Functor for Option<A> {
    type Unwrapped = A;
    type Wrapped<B> = Option<B>;

    fn map<F: FnMut(A) -> B, B>(self, mut f: F) -> Option<B> {
        match self {
            Some(x) => Some(f(x)),
            None => None,
        }
    }
}

impl<A> Functor for Vec<A> {
    type Unwrapped = A;
    type Wrapped<B> = Vec<B>;

    fn map<F: FnMut(A) -> B, B>(self, f: F) -> Vec<B> {
        self.into_iter().map(f).collect()
    }
}

trait Pointed: Functor {
    fn wrap<T>(t: T) -> Self::Wrapped<T>;
}

impl<A> Pointed for Option<A> {
    fn wrap<T>(t: T) -> Option<T> {
        Some(t)
    }
}

impl<A> Pointed for Vec<A> {
    fn wrap<T>(t: T) -> Vec<T> {
        vec![t]
    }
}

trait Applicative: Pointed {
    /*
    fn apply<A, B>(self, a: Self::Wrapped<A>) -> Self::Wrapped<B>
    where
        Self::Unwrapped: FnOnce(A) -> B
    {
        self.lift_a2(|f, a| f(a), a)
    }
    */

    //type WrappedApplicative<B>: Applicative;

    /*
    fn rewrap_applicative<T>(w: Self::Wrapped<T>) -> Self::Wrapped<T>;

    fn pure<T>(t: T) -> Self::Wrapped<T> {
        rewrap_applicative(Self::wrap(t))
    }
    */

    fn lift_a2<F, B, C>(self, b: Self::Wrapped<B>, f: F) -> Self::Wrapped<C>
    where
        F: FnMut(Self::Unwrapped, B) -> C;
}

/* FIXME didn't work
fn lift_a2<F, A, B, C>(f: F, a: A, b: A::WrappedApplicative<B>) -> A::WrappedApplicative<C>
where
    F: FnOnce(A::Unwrapped, B) -> C,
    A: Applicative
{
    a.map(|a| { move |b| f(a, b) }).apply(b)
}
*/

impl<A> Applicative for Option<A> {
    //type WrappedApplicative<B> = Option<B>;
    /*
    fn rewrap_applicative<T>(w: Self::Wrapped<T>) -> Self::Wrapped<T> {
        w
    }
    */

    fn lift_a2<F, B, C>(self, b: Self::Wrapped<B>, mut f: F) -> Self::Wrapped<C>
    where
        F: FnMut(Self::Unwrapped, B) -> C
    {
        let a = self?;
        let b = b?;
        Some(f(a, b))
    }

    /*
    fn apply<B, C>(self, b: Self::Wrapped<B>) -> Self::Wrapped<C>
    where
        Self::Unwrapped: FnOnce(B) -> C
    {
        let f = self?;
        let b = b?;
        Some(f(b))
    }
    */
}

/*
impl<A: Clone> Applicative for Vec<A> {
    fn lift_a2<F, B, C>(self, f: F, b: Self::Wrapped<B>) -> Self::Wrapped<C>
    where
        F: FnOnce(Self::Unwrapped, B) -> C
    {
        let mut result = Vec::new();
        for a in self {
            for b in &b {
                result.push(f(a.clone(), b.clone()));
            }
        }
        result
    }
}
*/

trait Monad : Applicative {
    fn bind<B, F>(self, f: F) -> Self::Wrapped<B>
    where
        F: FnMut(Self::Unwrapped) -> Self::Wrapped<B>;
}

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

struct Identity<T>(T);

impl<T> Functor for Identity<T> {
    type Unwrapped = T;
    type Wrapped<A> = Identity<A>;

    fn map<F, B>(self, mut f: F) -> Identity<B>
    where
        F: FnMut(T) -> B
    {
        Identity(f(self.0))
    }
}

impl<A> Pointed for Identity<A> {
    fn wrap<T>(t: T) -> Identity<T> {
        Identity(t)
    }
}

impl<T> Applicative for Identity<T> {
    /*
    type WrappedApplicative<B> = Identity<B>;
    fn rewrap_applicative<A>(w: Self::Wrapped<A>) -> Self::WrappedApplicative<A> {
        w
    }
    */

    fn lift_a2<F, B, C>(self, b: Self::Wrapped<B>, mut f: F) -> Self::Wrapped<C>
    where
        F: FnMut(Self::Unwrapped, B) -> C
    {
        Identity(f(self.0, b.0))
    }

    /*
    fn apply<A, B>(self, a: Identity<A>) -> Identity<B>
    where
        Self::Unwrapped: FnOnce(A) -> B
    {
        Identity((self.0)(a.0))
    }
    */
}

impl<T> Monad for Identity<T> {
    fn bind<B, F>(self, mut f: F) -> Identity<B>
    where
        F: FnMut(T) -> Identity<B>
    {
        f(self.0)
    }
}

struct IdentityT<M>(M);

impl<M: Functor> Functor for IdentityT<M> {
    type Unwrapped = M::Unwrapped;
    type Wrapped<A> = IdentityT<M::Wrapped<A>>;

    fn map<F, B>(self, f: F) -> Self::Wrapped<B>
    where
        F: FnMut(M::Unwrapped) -> B
    {
        IdentityT(self.0.map(f))
    }
}

impl<M: Pointed> Pointed for IdentityT<M> {
    fn wrap<T>(t: T) -> IdentityT<M::Wrapped<T>> {
        IdentityT(M::wrap(t))
    }
}

impl<M: Applicative> Applicative for IdentityT<M> {
    /*
    type WrappedApplicative<A> = IdentityT<M::WrappedApplicative<A>>;
    fn rewrap_applicative<T>(w: Self::Wrapped<T>) -> Self::WrappedApplicative<T> {
        IdentityT(M::rewrap_applicative(w.0))
    }
    */

    fn lift_a2<F, B, C>(self, b: Self::Wrapped<B>, f: F) -> Self::Wrapped<C>
    where
        F: FnMut(Self::Unwrapped, B) -> C
    {
        IdentityT(self.0.lift_a2(b.0, f))
    }

    /*
    fn apply<A, B>(self, a: IdentityT<M::Wrapped<A>>) -> IdentityT<M::Wrapped<B>>
    where
        M::Unwrapped: FnOnce(A) -> B
    {
        IdentityT(self.0.apply(a.0))
    }
    */
}

impl<M: Monad> Monad for IdentityT<M> {
    fn bind<B, F>(self, mut f: F) -> Self::Wrapped<B>
    where
        F: FnMut(Self::Unwrapped) -> Self::Wrapped<B>
    {
        IdentityT(self.0.bind(|x| f(x).0))
    }
}

trait MonadTrans {
    type Base: Monad;

    fn lift(base: Self::Base) -> Self;
}

impl<M: Monad> MonadTrans for IdentityT<M> {
    type Base = M;

    fn lift(base: M) -> Self {
        IdentityT(base)
    }
}

fn main() {
    let x = Some(1).bind(|x| Some(x * 2));
    println!("{:?}", x);

    println!("Age is {:?}", age());
}

#[allow(dead_code)]
#[derive(Debug, PartialEq)]
enum MyOption<A> {
    Some(A),
    None,
}

#[allow(dead_code)]
impl<A> MyOption<A> {
    fn map<F: FnOnce(A) -> B, B>(self, f: F) -> MyOption<B> {
        match self {
            MyOption::Some(a) => MyOption::Some(f(a)),
            MyOption::None => MyOption::None,
        }
    }
}

#[test]
fn test_option_map() {
    assert_eq!(Some(5).map(|x| x + 1), Some(6));
    assert_eq!(None.map(|x: i32| x + 1), None);
}

#[test]
fn test_myoption_map() {
    assert_eq!(MyOption::Some(5).map(|x| x + 1), MyOption::Some(6));
    assert_eq!(MyOption::None.map(|x: i32| x + 1), MyOption::None);
}

#[allow(dead_code)]
#[derive(Debug, PartialEq)]
enum MyResult<A, E> {
    Ok(A),
    Err(E),
}

#[allow(dead_code)]
impl<A, E> MyResult<A, E> {
    fn map<F: FnOnce(A) -> B, B>(self, f: F) -> MyResult<B, E> {
        match self {
            MyResult::Ok(a) => MyResult::Ok(f(a)),
            MyResult::Err(e) => MyResult::Err(e),
        }
    }
}

#[test]
fn test_result_map() {
    assert_eq!(MyResult::Ok(5).map(|x| x + 1), MyResult::Ok::<i32, ()>(6));
    assert_eq!(MyResult::Err("hello").map(|x: i32| x + 1), MyResult::Err("hello"));
}

#[allow(dead_code)]
#[derive(PartialEq, Debug)]
enum Validation<A, E> {
    Ok(A),
    Err(E),
}

#[allow(dead_code)]
impl<A, E> Validation<A, E> {
    fn map<F: FnOnce(A) -> B, B>(self, f: F) -> Validation<B, E> {
        match self {
            Validation::Ok(a) => Validation::Ok(f(a)),
            Validation::Err(e) => Validation::Err(e),
        }
    }
}

trait Semigroup {
    fn append(self, rhs: Self) -> Self;
}

impl Semigroup for String {
    fn append(mut self, rhs: Self) -> Self {
        self += &rhs;
        self
    }
}

impl<T> Semigroup for Vec<T> {
    fn append(mut self, mut rhs: Self) -> Self {
        Vec::append(&mut self, &mut rhs);
        self
    }
}

impl Semigroup for () {
    fn append(self, (): ()) -> () {}
}

impl<A, E> Functor for Validation<A, E> {
    type Unwrapped = A;
    type Wrapped<B> = Validation<B, E>;

    fn map<F: FnOnce(A) -> B, B>(self, f: F) -> Validation<B, E> {
        match self {
            Validation::Ok(a) => Validation::Ok(f(a)),
            Validation::Err(e) => Validation::Err(e),
        }
    }
}

impl<A, E> Pointed for Validation<A, E> {
    fn wrap<T>(t: T) -> Validation<T, E> {
        Validation::Ok(t)
    }
}

impl<A, E: Semigroup> Applicative for Validation<A, E> {
    /*
    type WrappedApplicative<B> = Validation<B, E>;
    fn rewrap_applicative<T>(w: Self::Wrapped<T>) -> Self::WrappedApplicative<T> {
        w
    }
    */

    fn lift_a2<F, B, C>(self, b: Self::Wrapped<B>, f: F) -> Self::Wrapped<C>
    where
        F: FnOnce(Self::Unwrapped, B) -> C
    {
        match (self, b) {
            (Validation::Ok(a), Validation::Ok(b)) => Validation::Ok(f(a, b)),
            (Validation::Err(e), Validation::Ok(_)) => Validation::Err(e),
            (Validation::Ok(_), Validation::Err(e)) => Validation::Err(e),
            (Validation::Err(e1), Validation::Err(e2)) => Validation::Err(e1.append(e2)),
        }
    }

    /*
    fn apply<A, B>(self, a: Validation<A, E>) -> Self::Wrapped<B>
    where
        Self::Unwrapped: FnOnce(A) -> B
    {
        match (self, a) {
            (Validation::Ok(f), Validation::Ok(a)) => Validation::Ok(f(a)),
            (Validation::Err(e), Validation::Ok(_)) => Validation::Err(e),
            (Validation::Ok(_), Validation::Err(e)) => Validation::Err(e),
            (Validation::Err(e1), Validation::Err(e2)) => Validation::Err(e1.append(e2)),
        }
    }
    */
}

#[test]
fn test_validation_ok() {
    let a: Validation<i32, ()> = Validation::Ok(5);
    let b: Validation<i32, ()> = Validation::Ok(10);
    assert_eq!(a.lift_a2(b, |x, y| x + y), Validation::Ok(15));
}

#[test]
fn test_validation_err() {
    let a: Validation<i32, Vec<&str>> = Validation::Err(vec!["error1", "error2"]);
    let b: Validation<i32, Vec<&str>> = Validation::Err(vec!["error3"]);
    assert_eq!(a.lift_a2(b, |x, y| x + y), Validation::Err(vec!["error1", "error2", "error3"]));
}

fn traverse<F, M, A, B, I>(iter: I, f: F) -> M::Wrapped<Vec<B>>
where
    F: FnMut(A) -> M,
    M: Applicative<Unwrapped = B>,
    I: IntoIterator<Item = A>,
    M::Wrapped<Vec<B>>: Applicative<Unwrapped = Vec<B>>,
{
    let mut iter = iter.into_iter().map(f);

    let mut result: M::Wrapped<Vec<B>> = match iter.next() {
        Some(b) => b.map(|x| vec![x]),
        None => return M::wrap(Vec::new()),
    };

    for m in iter {
        result = result.lift_a2(m, |vec, b| {
            vec.push(b);
            vec
        });
    }

    result
}

/// Monomorphic functor trait
trait MonoFunctor {
    type Unwrapped; // value "contained inside"
    fn map<F>(self, f: F) -> Self
    where
        F: FnMut(Self::Unwrapped) -> Self::Unwrapped;
}

impl<A> MonoFunctor for Option<A> {
    type Unwrapped = A;
    fn map<F: FnMut(A) -> A>(self, mut f: F) -> Option<A> {
        match self {
            Some(a) => Some(f(a)),
            None => None,
        }
    }
}

/*
trait HktFunctor {
    fn map<A, B, F: FnMut(A) -> B>(self: Self<A>, f: F) -> Self<B>;

impl HktFunctor for Option {
    fn map<A, B, F: FnMut(A) -> B>(self: Option<A>, f: F) -> Option<B> {
        match self {
            Some(a) => Some(f(a)),
            None => None,
        }
    }
}
*/

impl<A, E> Functor for Result<A, E> {
    type Unwrapped = A;
    type Wrapped<B> = Result<B, E>;

    fn map<F: FnMut(A) -> B, B>(self, mut f: F) -> Result<B, E> {
        match self {
            Ok(a) => Ok(f(a)),
            Err(e) => Err(e),
        }
    }
}

impl<A> Functor for MyOption<A> {
    type Unwrapped = A;
    type Wrapped<B> = Result<B, String>; // wut?

    fn map<F: FnMut(A) -> B, B>(self, mut f: F) -> Result<B, String> {
        match self {
            MyOption::Some(a) => Ok(f(a)),
            MyOption::None => Err("Well this is weird, isn't it?".to_owned()),
        }
    }
}

/*

Womp womp

fn join<MOuter, MInner, A>(outer: MOuter) -> MOuter::Wrapped<A>
where
    MOuter: Monad<Unwrapped = MInner>,
    MInner: Monad<Unwrapped = A, Wrapped = MOuter::Wrapped<A>>,
{
    outer.bind(|inner| inner)
}

#[test]
fn test_join() {
    assert_eq!(Some(Some(true)), true);
}
*/

fn birth_year() -> Result<i32, String> {
    Err("No birth year".to_string())
}

fn current_year() -> Result<i32, String> {
    Err("No current year".to_string())
}

fn age() -> Result<i32, String> {
    current_year().lift_a2(birth_year(), |cy, by| cy - by)
}

impl<A, E> Pointed for Result<A, E> {
    fn wrap<T>(t: T) -> Result<T, E> {
        Ok(t)
    }
}

impl<A, E> Applicative for Result<A, E> {
    fn lift_a2<F, B, C>(self, b: Self::Wrapped<B>, f: F) -> Self::Wrapped<C>
    where
        F: FnOnce(Self::Unwrapped, B) -> C
    {
        match (self, b) {
            (Ok(a), Ok(b)) => Ok(f(a, b)),
            (Err(e), _) => Err(e),
            (_, Err(e)) => Err(e),
        }
    }

    /*
    fn apply<A, B>(self, a: Validation<A, E>) -> Self::Wrapped<B>
    where
        Self::Unwrapped: FnOnce(A) -> B
    {
        match (self, a) {
            (Validation::Ok(f), Validation::Ok(a)) => Validation::Ok(f(a)),
            (Validation::Err(e), Validation::Ok(_)) => Validation::Err(e),
            (Validation::Ok(_), Validation::Err(e)) => Validation::Err(e),
            (Validation::Err(e1), Validation::Err(e2)) => Validation::Err(e1.append(e2)),
        }
    }
    */
}

Really nice post!
I have been playing around with a similar idea here https://github.com/mschuwalow/ratz/blob/main/src/hkt.rs, just using a different encoding.

It can avoid the problem of 'forgetting' the specific type that we have by defining the instances not on specific type, but on a phantom type representing the type constructor itself. Then we can establish the link between this phantom type and all members using traits.

pub trait Hkt {
    type Member<T>: Mirror<T = T, Family = Self>;
}

pub trait Mirror {
    type T;
    type Family: Hkt;
    fn as_member(self) -> <Self::Family as Hkt>::Member<Self::T>;
}

For example it looks like this for Option:

impl<T> Mirror for Option<T> {
    type Family = OptionFamily;
    type T = T;

    fn as_member(self) -> <Self::Family as Hkt>::Member<Self::T> {
        self
    }
}
pub struct OptionFamily;
impl Hkt for OptionFamily {
    type Member<T> = Option<T>;
}

This seems to be able to express traverse / join / etc without any problems and looks reasonably clean:

pub trait Traversable: Covariant {
    fn traverse<App: Applicative, A, B: Clone, F: Fn(A) -> App::Member<B>>(
        fa: Self::Member<A>,
        f: F,
    ) -> App::Member<Self::Member<B>>;
}

This has one caveat that the compiler seems to have problems to infer the type of the 'Hkt' given a member, but there are workarounds for this.