followup_hkt_emu.md

Follow-up to Method on Emulating Higher-Kinded Types (HKTs) in Rust

First off, thanks for all the comments and kind words on the original writeup; I've been meaning to follow up on some of the suggestions and write about the different ways to represent monads (and functors, HKTs, etc) that now exist, but a month of being busy has kind of gotten in the way (mainly with three new kittens!).

And for sure, I do not expect (nor do I want) this to become the norm for production-level Rust: rather, I hope that this can contribute to the foundations of programming with higher-level abstractions in Rust, somewhat like how early template metaprogramming in C++ and typeclass-constraint-unification metaprogramming in Haskell have contributed, perhaps indirectly, to later innovations in their respective languages and ecosystems that were much more reasoned, sound and usable.

Changes, Edits, Refinements

One of the things suggested in the comments (thanks ricochet1k and burjui) was to change the impls from being on Concrete<Container<forall_t>, Blah> to just being on Container<Blah>. I initially added the Concrete wrapping to try and fix my memory access woes, before I pivoted around breakthrough #1. After a brief discussion in the gist's comments, a proof-of-concept was provided by burjui, and I adapted my Functor-Applicative-Monad impls to use this technique, greatly simplifying the type signatures.

Another thing I've done is to hide the syntactic tar behind a pair of simple macros. While they are very small, their impact has been a surprising increase in readability (and a drastic reduction in angle brackets):

macro_rules! plug {
    ($t1:ty [ $t2:ty ]) => {
        <$t1 as Plug<$t2>>::result_t
    };
}

macro_rules! unplug {
    ($t:ty, $v:ident) => {
        <$t as Unplug>::$v
    };
}

Now we have

//Remember Self is some F<A>
pub trait Monad : Applicative {
    fn bind<F,B>(f:F, s:Self) -> plug!(Self[B])
    where 
        Self:Plug<F>+Plug<B>,
        F:Fn(unplug!(Self, A)) -> plug!(Self[B])
    ;
}

instead of

pub trait Monad : Applicative {
    fn bind<F,B>(f:F, s:Self) -> <Self as Plug<B>>::result_t
    where 
        Self:Plug<F>+Plug<B>,
        F:Fn(<Self as Unplug>::A) -> <Self as Plug<B>>::result_t
    ;
}

This really helps in the heftier type signatures. It's the little things that add up.

Now, the current impl Monad for Vec and Option look almost idiomatic:

impl<A:Clone> Monad for Vec<A> {
    fn bind<F,B>(f:F, s:Self) -> plug!(Self[B])
    where
        F:Fn(unplug!(Self, A)) -> plug!(Self[B])
    {
        //Binding to assist the type checker,
        //tell it that we are collect()ing to Vec<B>
        let res:Vec<B> = 
            s
            .into_iter()
            .map(|x|f(x))
            .flatten().collect();
        res
    }
}

impl<A> Monad for Option<A> {
    fn bind<F,B>(f:F, s:Self) -> plug!(Self[B])
    where
        F:Fn(unplug!(Self, A)) -> plug!(Self[B])
    {
        match s {
            Some(x) => f(x),
            None => None
        }
    }
}

Thirdly, I've bundled my code up (all ~250 lines of it) and published it to Github. Hopefully this should give a slightly better idea of what can be achieved using the Plug/Unplug HKT/GAT emulation technique, demonstrate a use of higher polymorphism and provide me with a non-self-referential third element for this list.

What's next?

Maybe growing this idea a bit further, or perhaps playing with lifetime branding (à la indexing crate) to solve a problem I have with my emulating-dependent-types technique. And more time with kittens.

(mainly with three new kittens!)

Praise our brother for the Divine Presence shone upon him!

Just kidding :) Love those purring fluffballs.

If you put Unplug as trait bound, you don't have to <Self as Unplug>::A
You can just Self::A
That is valid for any trait that doesn't require another type parameter

Oh cool, I'll see about changing those then

I would have defined res (in Vec<A>::bind) as let res: Vec<B> = s.into_iter().flat_map(f).collect();. Admittedly, I haven't actually tried to run the Rust compiler on that definition, but I can't see any reason not to use iter.flat_map(f) instead of iter.map(|x| f(x)).flatten().