Generalizing over Generics in Rust (Part 1) - AKA Higher Kinded Types in Rust

16 Likes

This was requested over on reddit by /u/CalligrapherMinute77

Is it feasible to implement join, i.e. bind(id) in the most general fashion?

The special case of Option:

fn join<X>(mmx: Option<Option<X>>) -> Option<X> {
    OptionFamily.bind(mmx, |mx| mx)
}

Yes, you can. I just chose what Haskell did, with no real reason. Thinking about it now, it would be less efficient to use join. For example, if you want a family over Vec, join would require you to have a Vec<Vec<_>>, which could be a lot of memory at once. Using bind can reduce the maximum memory usage to just two Vec<_> at once.

Now I've ended up in something working. It turns out to be pretty straightforward:

fn join<M, X>(m: M, mmx: This<M, This<M, X>>) -> This<M, X>
where
    M: Monad<This<M, X>, X>
{
    m.bind(mmx, |mx| mx)
}
1 Like