Monads in Rust, with GATs

Hi, greetings to all fellow monad enthusiasts out there, I’ve come across a way to “encode” type constructors with GATs. Here’s a demo for anyone interested. (This is just a proof of concept so far, in particular it isn’t efficient at all with those clones or anything.)

In case anyone else has already done something similar, please tell me ^^

// a lot of trait definitions omitted, see playground link below

struct Vec_;
impl TyCon for Vec_ {
    type Of<T> = Vec<T>;
}
impl<T> HasTyCon for Vec<T> {
    type Param = T;
    type GetTyCon = Vec_;
}

impl Clone1 for Vec_ {
    type OfIsClone<T: Clone> = CloneProof<Vec<T>>;
}

impl Monad for Vec_ {
    fn pure<T>(x: T) -> Vec<T> {
        vec![x]
    }
    fn bind<A, B, F: Fn(A) -> Vec<B>>(xs: Vec<A>, f: F) -> Vec<B> {
        xs.into_iter().flat_map(f).collect()
    }
}

fn pairs<M: Monad + Clone1, A: Clone, B: Clone>(
    ma: a!(M:<A>),
    mb: a!(M:<B>),
) -> M::Of<(A, B)> {
    do_! {
        x <- ma;
        y <- mb.clone();
        M::pure((x.clone(), y))
    }
}

#[allow(unused)]
// desugared version
fn pairs_explicit<M: Monad + Clone1, A: Clone, B: Clone>(
    ma: impl HasTyCon<Param = A, GetTyCon = M>,
    mb: impl HasTyCon<Param = B, GetTyCon = M>,
) -> M::Of<(A, B)> {
    ma.bind(move |x| mb.clone().bind(move |y| M::pure((x.clone(), y))))
}

fn main() {
    let xs = vec![1, 2, 3];
    let ys = vec![4, 5, 6];
    let zs = pairs(xs, ys);
    println!("{:?}", zs);
}

// Output: "[(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6)]"

(playground)

Edit: Removed 'static constraints. Previous version looked like this.

4 Likes

Just for curiosity: I tried to remove the 'static bounds from the Monad trait and all other places, and everything seems to work fine in the playground. Given that what you did is not exactly trivial and surely there is some reasoning behind these lifetime, can you explain them?

1 Like

I just didn’t come around to try removing those static lifetimes yet. Cool if it works out by just removing 'static everywhere, I would’ve anticipated worse.

Originally I tried having a Monad impl for something like Box<dyn Iterator<Item = T>>, but that didn’t work out too well when I realized I needed to be able to clone stuff. As I didn’t feel like thinking about non-'static trait objects at the time, that’s why I ended up with 'static everywhere.

Edit: Yes indeed, very good observation. I’ve updated the original post.

1 Like

This looks pretty similar to this approach by edmundsmith. Both approaches seem pretty understandable honestly -- it's cool that the approaches are so similar fundamentally, and are both so understandable overall.

1 Like

There was a reddit thread about this, and I posted something very similar to @steffahn's solution

1 Like

Oh, neat, I just read something about this as well from fpcomplete.

That's the reddit thread I linked :grin:

Hahah, ahh, so it is. Extra discussion on the reddit thread is good though!