monad.rs

pub trait Object<T> {}
pub trait Is<Obj> where Obj: Object<Self> {}
impl<T, Obj: Object<T>> Is<Obj> for T {}

pub trait Arrow<F, In> { type Out; }
pub trait IsArrow<Arr, In>
where Arr: Arrow<Self, In, Out = Self::Out> { type Out; }
impl<F, Arr: Arrow<F, In>> IsArrow<Arr, In> for F { type Out = F::Out; }

pub trait Id<T> {
    const id: impl IsArrow<Self, T, Out = T>;
}
pub trait Comp<Arr, R, S, T>: IsArrow<Arr, R, Out = S> {
    fn comp(self, g: impl IsArrow<Arr, S, Out = T>) -> impl IsArrow<Arr, R, Out = T>;
}
pub trait Functor<Arr> {
    type Obj<type>;
    fn map<S, T>(
        self: impl Is<Self::Obj<S>>,
        f: impl IsArrow<Arr, S, Out = T>,
    ) -> impl Is<Self::Obj<T>>;
}
pub trait Monad<Arr>: Functor<Arr> {
    fn pure<T>(x: T) -> impl Is<Self::Obj<T>>;
    fn flatten(self: impl Is<Self::Obj<impl Is<Self::Obj<T>>>>) -> impl Is<Self::Obj<T>>;

    fn flat_map<S, T>(
        self: impl Is<Self::Obj<S>>,
        f: impl IsArrow<Arr, S, Out: Is<Self::Obj<T>>>,
    ) -> impl Is<Self::Obj<T>> {
        self.map(f).flatten()
    }
}

// TODO(eddyb) have to seal a lot of these impls *somehow*.
pub struct TypeObj<T>;
impl<T> Object<T> for TypeObj<T> {}

pub struct FnArr;
impl<F: Fn(S) -> T, S, T> Arrow<F, S> for FnArr { type Out = T; }
impl Id<T> for FnArr {
    const id: impl Fn(T) -> T = |x| x;
}
impl<F: Fn(R) -> S, R, S, T> Comp<FnArr, R, S, T> for F {
    fn comp(self, g: impl Fn(S) -> T) -> impl Fn(R) -> T {
        |x| g(self(x))
    }
}

pub struct FnMutArr;
impl<F: FnMut(S) -> T, S, T> Arrow<F, S> for FnMutArr { type Out = T; }
impl Id<T> for FnMutArr {
    const id: impl FnMut(T) -> T = |x| x;
}
impl<F: FnMut(R) -> S, R, S, T> Comp<FnMutArr, R, S, T> for F {
    fn comp(self, g: impl Fn(S) -> T) -> impl FnMut(R) -> T {
        |x| g(self(x))
    }
}

pub struct FnOnceArr;
impl<F: FnOnce(S) -> T, S, T> Arrow<F, S> for FnOnceArr { type Out = T; }
impl Id<T> for FnOnceArr {
    const id: impl FnOnce(T) -> T = |x| x;
}
impl<F: FnOnce(R) -> S, R, S, T> Comp<FnOnceArr, R, S, T> for F {
    fn comp(self, g: impl FnOnce(S) -> T) -> impl FnOnce(R) -> T {
        |x| g(self(x))
    }
}

pub struct FMOption;
impl Functor<FnOnceArr> for FMOption {
    type Obj<T> = TypeObj<Option<T>>;
    fn map<S, T>(
        self: Option<S>,
        f: impl FnOnce(S) -> T,
    ) -> Option<T> {
        match self {
            Some(x) => Some(f(x)),
            None => None,
        }
    }
}
impl Monad<FnOnceArr> for FMOption {
    fn pure<T>(x: T) -> Option<T> { Some(x) }
    fn flatten(self: Option<Option<T>>) -> Option<T> {
        match self {
            Some(Some(x)) => Some(x),
            Some(None) | None => None,
        }
    }
}

pub struct IterObj<T>;
impl<I, T> Object<I> for IterObj<T> where I: Iterator<Item = T> {}
pub struct FMIter;
impl Functor<FnMutArr> for FMIter {
    type Obj<T> = IterObj<T>;
    fn map<S, T, IS: Iterator<Item = S>, F: FnMut(S) -> T>(
        self: IS,
        f: F,
    ) -> iter::Map<IS, F> {
        iter::Map(self, f)
    }
}
impl Monad<FnMutArr> for FMIter {
    fn pure<T>(x: T) -> iter::Once<T> { iter::once(x) }
    fn flatten<N: Iterator<Item: Iterator<Item = T>>>(self: N) -> iter::Flatten<N> {
        iter::Flatten(self)
    }
}

With "constraint kinds", this (maybe nicer) approach could also work:

trait Functor<trait<type, type> Arrow> for trait<type> {
    fn map<T, U>(self: impl Self<T>, f: impl Arrow<T, U>) -> impl Self<U>;
}

trait IsOption<T> = Self == Option<T>;
trait FnOnceArrow<T, U> = FnOnce(T) -> U;
impl Functor<FnOnceArrow> for IsOption {
    fn map<T, U>(self: Option<T>, f: impl FnOnce(T) -> U) -> Option<T> {
        match self {
            Some(x) => Some(f(x)),
            None => None,
        }
    }
}

trait IsIterator<T> = Iterator<Item = T>;
trait FnMutArrow<T, U> = FnMut(T) -> U;
impl Functor<FnMutArrow> for IsIterator {
    fn map<T, U, I: Iterator<Item = T>, F: FnMut(T) -> U>(
        self: I,
        f: F,
    ) -> iter::Map<I, F> {
        iter::Map(self, f)
    }
}

Tried updating this for current nightly, now that GATs are out: playground.
But it doesn't really work because Is/IsArrow are implied by their impls, but the other direction (rustc assuming the only applicable impl is the only one that could ever exist, and allowing assuming any unifications/bounds of the impl).

EDIT: A bit better terminology, and removing the Foo/IsFoo indirection (only needed cross-crate, a bit like From/Into), but still totally busted for the same reason of a lack of "sealing"/"closed-world" around impls: playground.

EDIT2: recording a last ditch attempt of creating a more indirect "guarantor" system - that also doesn't work because there's no way to "stash a dictionary/vtable", so to speak, in Rust, at the typesystem level...