What is a monad? And who needs Haskell anyway?

I was watching this Computerphile video: "What is a Monad?" What is a Monad? - Computerphile - YouTube thinking that Computerphile were likely to be able to explain what is a monad in a simple enough way for normal people to understand.

The explanation revolves around creating as simple expression evaluator in Haskell, which has to not crash on divide by zero. This is already going down hill, who knows Haskell? But I persevere:

He starts with writing the Haskell data type:

data Expr = Val Int | Div Expr Expr

Well, soon I'm lost in the weeds, as are most other commentators on that video, but that single line at the start suggested a Rust Option or Error type.

Many hours later.... I had this expression evaluator running in Rust:

#[derive(Debug, Clone)]
enum Expr {
    Value(Option<i32>),
    Div(Box<(Expr, Expr)>),
}

fn safe_div(m: Option<i32>, n: Option<i32>) -> Option<i32> {
    match (m, n) {
        (Some(m), Some(n)) => {
            if n == 0 {
                None
            } else {
                Some(m / n)
            }
        },
        (_,_) => None
    }
}

fn eval(e: Expr) -> Option<i32> {
    match e {
        Expr::Value(v) => v,
        Expr::Div(operands) => safe_div(eval(operands.0) , eval(operands.1)),
    }
}

Which as far as I can tell does what the Haskell code in the video does. Using Rust's Option type rather than the Haskell's Maybe monad. As far as I can tell it is not much longer and far easier to read!

The presenter says that this "monad" thing is one of the greatest developments in computer science in 25 years. But surely we have been doing this in languages like C since forever, with tagged unions and function pointers? Did the computer science guys just find out how to program? :slight_smile: Of course it's a big thing that languages like Haskell and Rust support this kind of thing very robustly rather than hacking it together in C.

Anyway, I still don't know what a monad is. Where is the monad? Apparently there is one in there as rust analyzer popped up occasionally with some message about "rust-monad".

Is there a better way to do what I have there? Before I start extending it for other operators?

6 Likes

Maybe is just an example of a monad. A monad is not a concrete type but a concept / an abstraction.
In Rust, Monad would be a trait. However afaik Rust traits are not yet able to represent a monad.

Option in Rust is roughly the same as Maybe in Haskell. In a way, Option is already a monad, it's just that Rust cannot (yet) generically abstract that functionality into a trait.

EDIT:
It's a bit like collections. There are no collection traits in Rust yet (at least not in the standard library) but the collections themselves have all the functionality they need.

5 Likes

Monad is a pattern that generalizes behavior, not a specific type. My hubris demands me attempt to summarize the abstraction tower:

A functor is a context you can map operations over. So you can turn a function T -> U into a function List<T> -> List<U> or a Option<T> -> Option<U> or a BinaryTree<T> -> BinaryTree<U> or a Command<T> -> Command<U> or whatever (where List, Option, Command, etc. are the functors.) A functor instance for some generic type F means that you can do these operations over the structure of F, whatever that structure is, turning it from a structure of Ts to Us.

An applicative functor is a functor that can encode sequential application. Don't worry about this one too much, everyone forgets about it even though it's the one you usually need. It lets you treat your functor like an idiom by requiring a constructor T -> F<T> (just a basic constructor, which functors don't require) and an application function F<T -> U> -> F<T> -> F<U>. We can add usize + usize, so it'd be nice to be able to just do Option<usize> + Option<usize> and get out the obvious thing without having to define a special addition operation. Same with List<usize> + List<usize>.

Then there's the monad at the top. It's an applicative functor where each step can determine the next step. They're composed with a bind operation that takes a T -> F<U> and produces a F<T> -> F<U>. In lists, this lets you do flat_map; in options, and_then; and if you treat the world as a structure as Haskell's IO does, bind is (similar to but different than) Rust's semicolon, which chains expressions into a bigger expression.

The important thing to remember, though, is it's just patterns of types and functions. Anything F that you can define a function fn map<T, U, F: Fn(T) -> U>(t: T, f: F<T>) -> F<U> for is a functor (as long as it fulfills some other laws about mapping the identity that are pretty common sense so let's ignore them here.) It's just a way of thinking about things generically.

In your description, specifically, you've implemented the safe_div operation. If you wanted to make these Exprs robust, you'd need operations for all the mathematical operators; you'd have to code a safe_plus, safe_minus, safe_factorial, etc. The point of treating Option as a (monadic) (applicative) functor is that you'd just use Option's ap function and the normal / operator to produce it, and any other function that took i32s could be instantly transformed into something that took Option<i32>s.

e: An alternate way of thinking about it is that Haskell didn't invent monads; it just let you write things that aren't in monads, unlike C.

22 Likes

Off-topic, but safe_div can be written as

fn safe_div(a: Option<i32>, b: Option<i32>) -> Option<i32> {
    a?.checked_div(b?)
}

(playground)

which is simpler IMO.

4 Likes

Carefully read this page. Understand that "do notation" is essentially just traditional imperative code, and that the key property of imperative code is that state is implicitly transferred from one command to the next. The thing that makes Monads a significant development in PL theory and computer science is that they are a purely functional way to construct this implicit state passing; prior to the discovery of monads, if you wanted to pass state like this, you would have to either be explicit about it or violate functional purity.

Of course every imperative language has monads, because they all implicitly pass state around. They don't often have a "monad abstraction" as a first class construct. (Because why would you, when you can already violate purity and pass state implicitly on a whim?) Monads represent an abstract model of the difference between pure functional code and imperative code, which is expressible within a type system.

If you actually want to understand them, you have to do some homework. Write Haskell. (Don't just read about it. Do not just lazily watch some videos. Nobody learns anything deep like that, do what it takes to acquire an actual education.) Learn to desugar do notation into monadic binds and closures, and you should be able to see pretty clearly how imperative state is threaded through pure functions. Once you can do that, it makes sense to then look at the bigger picture and see how that same mechanism can be generalize to other kinds of behavior, like Options, Results, etc.

16 Likes

A monad is a type that looks like a collection and has a flat_map function. A Vec<T> is a monad. An Option<T> is a monad (it's a collection with zero or one elements) and its flat_map is called and_then. A Future is a monad (it's a collection with exactly one element), although you have to squint as the element doesn't quite exist yet. It's flat_map is then.

The reason people really like these monad types is what haskell calls do-notation. For the case of Option, do notation is the question mark operator. For the case of Future, do notation is the async/await syntax.

For Vec<T>, do notation is be pretty weird. Consider the following code with made-up syntax:

fn foo(a: Vec<u32>) -> Vec<u32> {
    let item: u32 = a?;
    println!("{}", item);
    let item2: u32 = vec![item, item]?;
    return item2;
}

In this case I have borrowed the question mark to refer to vector's flat_map instead of option's and_then. In this context, the question mark would run the remaining code in the function for every item in the vector, so the snippet above would print every item in the vector, and return a vector with each item duplicated, so foo(vec![1, 2, 3]) = vec![1, 1, 2, 2, 3, 3].

If you think about what the question mark does on options, it is actually the same thing. If the option is None the collection has zero elements, and the rest of the code runs zero times. If it is Some, there is one element, and the rest of the code runs once. Similarly, a Future always has exactly one item, so the rest of the code runs once.

Anyway, do notation is a generalization of the question mark and async/await syntax, and using do notation, you could reimplement async/await syntax in haskell as a library, without any special compiler support for Futures whatsoever.

(to be exact, you would need ok-wrapping for the question mark operator to truly be do notation for options)

44 Likes

Thank you, @alice. This explains Haskell's do notation in a way that many of us can grok, and thus serves to unify related concepts in Rust.

2 Likes

I forget who said it, but I read an article (or maybe it was a conference talk?) which talked about how Rust will typically approach monads...

The Monads pattern let you abstract over something by phrasing the particular concept as a series of transformations. For example, Option<T> lets you abstract over whether something is present, Result<T, E> lets you abstract over failure, Iterator<T> lets you abstract over iteration, and Future<T> lets you abstract over an operation which may or may not have completed yet.

We don't really have a way to group these concepts (we need to introduce another layer of indirection - i.e. higher kinded types) so the operation for transforming our data tend to be coded manually. You'll usually see this as an and_then() method (e.g. Iterator::and_then(), Future::then(), Option::and_then(), Result::and_then()).

In situations where you are chaining a lot of these transformations together it's nice to introduce a bit of syntactic sugar. In the case of Result<T, E> and Option<T> it's the ? operator, and with Futures we use async/await. Haskell's type system lets it generalise over the transformation operation, so can achieve everything with their do notation.

11 Likes

I agree with this characterization.

However it just raises the question for me why Rust didn't just add the type infrastructure (e.g. HKT) before working on async, and build on top of that?
(of course then you can go even further and ask why there's no I/O monad either)

Don't misunderstand me, I understand that it's just not in the Rust philosophy to go "full monad". But nonetheless it seems like at least a great tool to implement the various instances of it in the language, ultimately potentially yielding returns multiple times that of the initial investment needed to get that working in the first place.

1 Like

You can find some discussion on why Rust did not just use monads here. Search in particular for comments by withoutboats and steveklabnik.

6 Likes

Thanks for all the comprehensive replies everyone. Again much more that I could have hoped for. There is a lot there and it will take me some time to get a grip on it all. I'll get back with comments later.

I'm not much closer to putting my finger on a monad yet. Rust analyzer was popping up message saying something about "rust-monad", I had no idea what it was talking about but it seems I have captured a monad in my code somehow. I only have to find it :slight_smile:

I gather from this video: "Category Theory 10.1: Monads" Category Theory 10.1: Monads - YouTube are all about compostion. Composition of functions I guess, as pure functional languages don't have any data as far as I can tell.

For some years now I have had the impression that monads are to FP as "switch", "continue", "break" and "exceptions" are to structured programming. Bear with me:

In structured programming one has introduced functions, procedures, "if"s and "while"s etc to tame the mess of GOTO anywhere. But having outlawed goto it was necessary to introduce switch, break, exceptions etc to replace it!

Similarly having outlawed side effects in FP it was necessary to invent monads in order to get anything useful done with state.

I was amazed when I heard withoutboats say exactly that in one presentation I saw last year.

Anyway, back at the coal face, I tweaked my evaluator to handle other arithmetic ops. I figured out how to stuff a function pointer into a enum, so eval() stays very short and the checking for None operands is abstracted out of the operator functions. As far as I can tell that makes it look even more like the Haskell version in the Computerphile video:

type SafeOperator = Box<dyn Fn(i32, i32) -> Option<i32>>;
//#[derive(Debug, Clone)]
enum Expr {
    Value(Option<i32>),
    Op(Box<(Expr, Expr,)>, SafeOperator),
}

fn safe_add(m: i32, n: i32) -> Option<i32> {
    println!("Adding safely");
    Some(m + n)
}

fn safe_sub(m: i32, n: i32) -> Option<i32> {
    Some(m - n)
}

fn safe_mul(m: i32, n: i32) -> Option<i32> {
    Some(m * n)
}

fn safe_div(m: i32, n: i32) -> Option<i32> {
    if n == 0 {
        None
    } else {
        Some(m / n)
    }
}

fn apply <F>(operator: F, m: Option<i32>, n: Option<i32>) -> Option<i32> 
             where F: Fn(i32, i32) -> Option<i32>  {
    match (m, n) {
        (Some(m), Some(n)) => {
            operator(m, n)
        },
        (_,_) => None
    }
}

fn eval(e: Expr) -> Option<i32> {
    match e {
        Expr::Value(v) => v,
        Expr::Op(operands, op) => {
            apply(op, eval(operands.0), eval(operands.1))
        }
    }
}

I have no idea if that is a good way to build such an evaluator but I thought it was kind of neat.

Only problem is I can't clone my expr anymore. Any suggestions?

Haskell has a type system with its own tradeoffs. It allows encoding of a lot of rules in types while still allowing procedures to be reused flexibly. The type system has two difficult and contradictory roles: make it so pieces of the program can be defined in ways that don't allow them to be misused; and make it easy to glue pieces of the program together.

Higher-kinded types are an instance of the latter role: making it easy to reuse code and data types. Imagine you have a procedure which finds the sum of all elements in a numeric collection. Imagine that you want to make that function sum any collection of numeric values. So you want it to operate on Set<i32> and also Vec<i32> and also any other collection type that may be created in the future.

But let's look at preventing misuse: I don't want to see another method call on null again in my programming career (too bad for me -- I will anyway). A strongly-typed alternative to null is Option. It's pretty much the same thing as null, but constructed in a way that's amenable to automatic checking. Let's say you have a procedure f(x, a, b) { (x / a) / b } which takes any 3 integers as inputs. Division by zero means we don't always have a sensible answer, so let's use option types. We'd essentially have something like this as our final code:

if let Some(z) = x / a {
    z / b
} else {
    None
}

You can run into repeated situations of packing and unpacking the option value. Wouldn't it be nice if you could just write (x / a) / b? To handle the packing logic automatically? You can get pretty close.

Now imagine you want to handle packing logic for any kind of packable collection exactly the same way so you can abstract over it in code. This is where the actual category theory language is better suited for description.

I like this analogy.

Monads are how languages like Haskell can model a changing world in an entirely immutable environment. In that way they're the bread and butter of FP, filling a similar role as control flow statements (switch, continue, etc.) for more procedural languages.

What about using an Rc<dyn Fn(...)> instead of Box<dyn Fn(...)>? The closure is immutable so it should be fine to share it around via a shared pointer.

I thought about using Rc but I can't get it to compile. I don't understand why I need a Box anyway.

Edit: Turns out I don't I can just remove Box and it works! I also don't need the generic T or the where clause on the apply function:

type SafeOperator = fn(i32, i32) -> Option<i32>;

#[derive(Debug, Clone)]
enum Expr {
    Value(Option<i32>),
    Op(Box<(Expr, Expr)>, SafeOperator),
}

fn safe_add(m: i32, n: i32) -> Option<i32> {
    println!("Adding safely");
    Some(m + n)
}

fn safe_sub(m: i32, n: i32) -> Option<i32> {
    Some(m - n)
}

fn safe_mul(m: i32, n: i32) -> Option<i32> {
    Some(m * n)
}

fn safe_div(m: i32, n: i32) -> Option<i32> {
    if n == 0 {
        None
    } else {
        Some(m / n)
    }
}

fn apply(operator: SafeOperator, m: Option<i32>, n: Option<i32>) -> Option<i32> {
    match (m, n) {
        (Some(m), Some(n)) => operator(m, n),
        (_,_) => None,
    }
}

fn eval(e: Expr) -> Option<i32> {
    match e {
        Expr::Value(v) => v,
        Expr::Op(operands, op) => apply(op, eval(operands.0), eval(operands.1)),
    }
}

Correction: pure functional languages absolutely have data - otherwise it would be really hard to write useful programs. The "pure" in pure functional doesn't mean there are just functions, it means that all functions are pure, meaning they don't mutate the outside environment or depend on mutable state. This is related to the concept of referential transparency: in a pure functional language an expression can always be substituted by the result of its evaluation (e.g a function call with certain arguments) without impacting the behavior of the program.

4 Likes

Be careful about tying monads too closely to IO or impure functions. They are used for much more than that- e.g. the Maybe and Either a monads have very little to do with the state of the world.

The analogy to structured control flow is much more apt. A monadic function works with values of type M<A> where M: Monad, in terms of Monad::flat_map. This means the function must be written in a sort of continuation-passing style, much like pre-async/await Future combinators or old-style Node.js.

The power comes from the way M's Monad impl plumbs the wrapped M<A> values into the Fn(A) -> M<B>s passed to flat_map. Futures do this in a way that makes the program async, suspending on pending M<A>s. Options and Results do this in a way that makes the program short-circuiting, throwing away the Fn(A) -> M<B> (which represents "the rest of the function") on None or Err M<A>s.

This power happens to be a nice way to represent world-state-affecting code as a "pure" value- for example, much the same way a Future represents a whole computation, you might have flat_map return an opaque M<B> containing the Fn(A) -> M<B>, rather than calling it immediately. In Haskell the type of this opaque object is IO a; main is an object of this type, and the runtime is responsible for actually performing the side-effecting operations represented that way.

2 Likes

Forgive me for being slow but that made no sense to me. It seems to be a circular definition of monad in terms of monad. It also suggests, with "M:Monad", that a monad is a type, which I was told above it is not.

I think what I have here is a major terminology problem. Starting with the original question "What is a monad?" and now I wonder what on Earth is "continuation-passing style"?

Bear with me. I studied Physics not CS. At a time when a CS undergrad course was almost unheard of. I ended up programming in old school structured programming languages like Coral, PL/M, Pascal, C. This terminology has never appeared anywhere.

Undeterred I consult wikipedia:

A function written in continuation-passing style takes an extra argument: an explicit "continuation", i.e. a function of one argument. When the CPS function has computed its result value, it "returns" it by calling the continuation function with this value as the argument. That means that when invoking a CPS function, the calling function is required to supply a procedure to be invoked with the subroutine's "return" value.

Ah ha, BINGO! You are talking about "call backs" (node.js) or function pointers (C). Like so in Rust I guess:

// Coninuation-passing style function.
fn cps<F>(x: i32, continuation: F)
where
    F: Fn(i32),
{
    let result = x + 42;
    continuation(result);
}

fn main() {
    let x = 1;
    cps(x, |x: i32| {
        println!("{}", x);
    });

    fn continuation (x: i32) {
        println!("{}", x);
    }
    cps(x, continuation);
}

Why didn't you say? Well, I guess you did. It's seems to be impossible to find anyone who can translate the terminology to something concrete for us old timers.

Thanks.

Am I monad yet?

3 Likes

To use Rust terms, a Monad is sorta like a trait, but it's one you would implement for Vec, and not for Vec<T>. As for the M: Monad syntax used by @rpjohnst, the M type refers to Vec, not to Monad.

As for continuations, one interesting detail is that the continuation should not really be thought of a function call in the ordinary sense, but rather as return being provided as a sort of function. For example, assembly can be thought of using continuation passing style in the sense that the return position is pushed to the stack (given as an argument), and the ret instruction is used to perform an unconditional jump into the location provided as an argument. Unlike callbacks in C, the continuation callback never returns.

1 Like

As for whether you are a monad, do you have a flat_map method?

3 Likes

There in lies the deep mystery. At least for me.

If functions do not mutate their outside environment then how do you ever get any output?

If functions do not have any mutable state then how do you ever create a state machine, for example how can you simply count anything? Never mind how would you make a data base?

I have heard rumor that the mysterious monad is the trick that enables pure functional languages to actually do anything useful like that. It is, well, mysterious.

It's an odd thing but back in 1980 something I was modifying some Coral, the task was to replace an array with a function. That is to change all the array indexing, with "something[index]" to function calls with "something(index)".

It occurred to me to wonder why we have a different syntax for array indexing than function calling. If we did I would not have to be changing all that code and retesting it.

I mentioned it to my colleagues over lunch. They though I was nuts!

1 Like