What would be the benefit of a `Monad` type?

A few weeks ago, I spent a few hours digging into discussions about GAT, higher kinded types, monadic types etc. (Someone who has links on that topic at hand please throw them in here.) From searching "monad" in my history, these were at least:


Which left me pondering. Rust already has "monadic" types – types that act like monads and hold up their axioms (with type system subtleties, but whatever). The discussions I read seem to be about making these a "proper" Monad trait. This would allow one to abstract over monads. But what for? I already have Option, Result, Iterator, Future and a lot of others, what would be the use of making them sub-types of Monad? Where would I have a function that takes a Monad as argument?

I've read a lot about how to implement them in Rust, how to do so as zero-cost abstraction, and I understand that the price for them is a lot of work and complexity in the type system to make this work. But the benefits of these (specifically in Rust) have yet to be explained to me.

3 Likes

In Haskell, every instance of Monad gets do-notation, for free. The equivalent in Rust might be, for example, a generalized version of async syntax across all those types. That is, Result has the ? operator; Future has the await operator; Monad would let both of those work the same way instead of each being defined from scratch.

(An equivalent for Iterator would be very strange to most Rust programmers. It would appear to extract a single item from an iterator, but the rest of the function would then run N times for all N items, and the results would all be concatenated together into a new iterator.)

1 Like

In Haskell, every instance of Monad gets do-notation, for free. The equivalent in Rust might be, for example, a generalized version of async syntax across all those types.

To expand on that. Rust has try/async blocks built-into the language. If it instead had user-defined monads then try/async could just be defined in the standard library and users would be able to define their own kinds of blocks for their own monads.

Edit:

A couple of examples might help.

One thing I wanted to do recently was write code which handles point-cloud probability distributions of values. So I have a type that looks like this:

struct Cloud<T> {
    // list of (value, relative_probability)
    points: Vec<(T, f64)>,
}

And I want to be able to treat a Cloud<T> as if its a T, propogating the "cloudness" to the top of the function/expression. Cloud<T> is a monad, so with user-defined monads I could define my own cloud block and use it like this (where .point is the monadic-bind operator for cloud blocks, similar to .await or ?):

let position: Cloud<u32> = ... ;
let velocity: Cloud<u32> = ... ;
let new_position = cloud { position.point + velocity.point * dt }

Of course it would be trivial to rewrite this specific example to use .map()/.bind() instead of special syntax, but it's not trivial if you're writing more complicated code that needs to handle point-clouds of values.

Another example: sometimes I want to write code which handles errors by breaking on the first Ok it encounters but continuing when it encounters an Err - ie. the opposite of what try does. You can abuse try blocks for this by flipping all your Results before using ? and then flipping the result of the try block, but it's kinda ugly. With user-defined monads you could define a try_err block that does this directly:

fn aquire_banana() -> Result<Banana, (NoBananaInCupboardError, StoreClosedError)> {
    try_err {
        let error0 = look_for_banana_in_cupboard().err;
        let error1 = buy_banana_from_store().err;
        (error0, error1)
    }
}
2 Likes

To offer my $0.02: in Rust, not much.

In pure functional languages, monads are pretty much needed for a handful of use cases for solving very concrete and practical problems. Like, performing I/O, getting through chained fields of types, having syntactic sugar for error handling, etc.

In Rust, which is not constrained by the "thou shalt never mutate anything" rule, these problems have more natural and convenient solutions. And while some of the types and APIs do benefit from a monad-like design and usage pattern, it's a lot less useful to abstract over general monads, because there's not much to generalize (or rather, it doesn't solve more problems than the other features of the language).

Some have facetiously argued in the past that "monads are a solution to a problem you shouldn't have". While I don't agree with such a strong statement, I can see where it's coming from.

6 Likes

Thanks for the responses.

The "do"-notation is a great plus and something I'd sometimes really like to have. However, how much of this could be implemented using macros or lang items? I can imagine having structs/traits with a special attribute on the and_then function that enables some syntax sugar.

@canndrew You example is an interesting one, because you are composing the results on or_else instead of and_then. There is an RFC (I think) about postfix-macros, which would allow to have .err!() or the like to what you want. But you could already use good old try!-style circumfix macros.

That is, Result has the ? operator; Future has the await operator; Monad would let both of those work the same way instead of each being defined from scratch.

@rpjohnst Not that I think more about it – is this really something we want? The Result has the ? operator and Future has await, but they are specialized to their use case and thus semantically different, both to each other and to "real" monadic composition. If both shared the do-notation (which maps to and_then), we'd probably end up with less ergonomic code than we have now.

Right, that's a major point made by the Twitter thread you linked. Rust's implementations of these types capture a lot of low-level detail not present in the monad concept. A truly useful unification of ? and await might need to go beyond vanilla monads as well.

On the other hand, monads are pretty abstract and mathematical- the concept doesn't necessarily need to be present in a library as a trait for it to apply. When you say things like "how much of this could be implemented using macros or lang items?" that's not so much an alternative to "monads" as an alternative to trait Monad.

You don't even need any of that for do notation. It can be implemented by a procedural macro that parses the body of a function, turns do syntax into calls to and_then and emits the transformed function.

Given that for the reasons enumerated above, do isn't something that the majority of Rust developers needs, it should indeed be a proc-macro rather than a core language feature.

3 Likes

This is Iterator::map, right?

It's flat_map, technically, since each "branch" of the function produces its own list.

1 Like

Also, I think another reason that Monad (and Functor, etc.) are typeclasses in Haskell is you can have polymorphic functions that are polymorphic over all monads, not just, say, Option<T>.

2 Likes

This is something I subsume under "abstracting over monads", and I understand why Haskell needs and does that. But for Rust, the price to pay for this is a lot higher and I don't see as many uses for it as in Haskell.

As one data point, Scala does implement (or at least implemented when I last used it some years ago) its "for comprehensions" as a set of purely syntactic transformations. Its type system is strong enough to represent monads (as seen in scalaz &co) but there is (was?) no monad abstraction in the standard library. To opt in with your own types, you just have to implement map and flatMap (and possibly withFilter which is a lazy filter) with proper signatures and you're go.

An interesting point that's come up is monad transformers. At the moment, nested monads don't work well in Rust. There's TryStream and TryFuture for Streams and Futures of Results. There's a few distinct methods on Iterator for options and results (but by far not enough) and there's something for Option<Result>, Result<Option>, Option<Option>. You get the idea.

I'don know how but would the use of monads help by this, but I think they might help us to not write a lot of methods for each relevant monad nesting combination.

Monads are the wrong abstraction IMHO. Functors are all you need to have "monadic bind" syntax, what monads give you is two more natural transformations (per monad) that let you collapse any number of levels of nesting of your monad down to one level. eg. The pure and flatten operations on Option allow you to convert:

Option<Option<...<Option<T>>...>>  -->  Option<T>
^~~~~~~~ n times ~~~~~~~^

Which is what allows you to write try blocks (for Option) with n uses of the ? operator for any n.

These aren't the only important natural transformations though. For instance, using ? on a Result will also convert the error type using Into. That is, it uses a generic natural transformation:

Result<Result<T, E0>, E1>  -->  Result<T, E>
where
    E0: Into<E>,
    E1: Into<E>,

This is more general than the flatten operation that you get from Result<_, E> being a monad.

Another example: If you want to be able to use ? inside async blocks then you also need to be able to transform impl Try<Ok = impl Future<Output = T>> into impl Future<Output = impl Try<Ok = T>>, but you don't get this from monads.

So I think if you want to support "monadic" syntax the way to do it is to ditch monads completely and work directly at the level of functors and natural transformations.

How I imagine this working is: for any functor (any trait with a map method) you can give it its own block/bind psuedo-keywords (eg. async/await in the case of Future). You also have to provide an "into" trait which is implemented on types that can be converted into your functor. eg. For Future this would be IntoFuture<T> which is implemented for types that can be converted into an impl Future<Output = T>. The implementations of this trait provide the natural transformations, so you need to at least have T: IntoFuture<T> and F: IntoFuture<T> for F: Future<Output = G>, G: Future<Output = T> if you want the monadic pure and flatten operations. But you can also provide other implementations such as the one that swaps the order of Try and Future above.

When you use your new block syntax all the binds get translated into invocations of map and the entire body of the block is passed to a call to your "into" trait. For example, if we had the following block:

async {
    let b = a.await;
    let c = b?;

    let x: T = foo(c);
    x
}

This gets translated into (something equivalent to):

IntoFuture::<T>::into({
    Future::map(a, |b| {
        Try::map(b, |c| {
            let x: T = foo(c);
            x
        })
    })
})

Note that it can't literally be translated like this due to borrowing, but if you wanted to implement this with macros you can probably expand it to something equivalent using generators and unsafe hackery.

5 Likes

How could this work for Iterator<Result>? I somehow need specialized versions of map, filter, fold, etc., where do they come from? How could I specialize Iterator for my own monadic type, without having to implement all those methods yet again? (TryIterator is really copy+pasting a lot of boilerplate code with little adjustments.)