What is a monad? And who needs Haskell anyway?

Like @ZiCog, I'm of the older generation and find a lot of this newfangled stuff confusing. Recently, a friend explained monads in a way I can almost understand. The most important feature for me is that the monad lets me chain operations containing Option or Result without needing to worry about None or Err values. Here's a silly example.

fn main() {
   let v = vec![Some("1"), Some("2"), None, Some("x")];
   let new_vec: Vec<_> = v.iter()
        .map(|i| i
            .and_then(|i| i.parse::<i32>().ok()
            .map(|i| i+42)))
        .collect();
    println!("{:?}", new_vec);
}

It prints [Some(43), Some(44), None, None]. The and_then() and map() monads on Option automatically take care of the None elements.

3 Likes

Pretty much. It lets you turn a Vec<Vec<T>> into a Vec<T>.

As an example, imagine you are calling an API which uses pagination. Every call to the API will return a list of items, so if you wrote something like (0..num_pages).map(|page_number| get_page(page_number)) you could use flat_map() to flatten that all down into a single Vec.

Sure, you could use a for-loop and Vec::extend(), but sometimes the functional version ends up being more ergonomic or performant.

wow I am not the only one not to be clear about what a monad is :smiley: almost everyone puts it differently :smiley: I am relieved :smiley:

1 Like

Here's yet another attempt to demystify the why of monads, but not actually explain them. Sorry, if the misunderstandings this is attempting to clear up are not the actual reason for folk's underlying struggle with monads.

First, I'll start by echoing others:

So to summarize:

  1. The concept of a monad doesn't give List or Option their powers to flat_map or to automatically handle Nones. Those are their inherent powers provided to them by their methods. These inherent abilities allow them to be classified as monads.
  2. Like everything in abstract algebra, monads are a pattern. The talk of monads only really becomes relevant when we ask whether the language's type system allows you to take advantage of this pattern to, e.g., DRY out the code. Rust's type system does not at the moment (more on that at the end).

So perhaps let's focus on very familiar patterns that rust does allow us to generalize over, and not talk about monads just so that everything feels extremely familiar.

A familiar pattern: In many programming languages, a very common pattern we see with some binary operators (integer addition, integer multiplication, string concatenation, list concatenation) is the following:

  1. When you apply the operation to two instances you get a new instance of the same type (e.g. 1+2 is also an int, concat("a", "b") is also a string.
  2. The operation is associative: e.g. a + (b + c) = (a + b) + c
  3. There is an identity element: e.g. 0 + a = a + 0 = a

Any pair of (type, operator) that satisfies these three properties is called a ...sigh... monoid1, because mathematicians haven't historically taken the most difficult problem in computer science seriously enough. Examples:

  • (int, +) - identity is 0
  • (int, *) - identity is 1
  • (string, concatenation) - identity is an empty string
  • (list, concatenation) - identity is an empty list

In Rust, we can abstract monoids with a trait2:

trait Monoid {
  fn id() -> Self;
  fn op(self, other: Self) -> Self;
}

You can easily define this for (i32, +):

impl trait for i32 {
  fn id() -> Self { 0 }
  fn op(self, other: Self) -> Self { self + other }
}

and for (String, concatenation)3

impl trait for String {
  fn id() -> Self { 0 }
  fn op(mut self, other: Self) -> Self { self += &other; self }
}

This trait now allows us to write extremely general methods that abstract over all monoids. E.g.

fn monoid_em_all<T: Monoid>(list: List<T>) -> T {
  let mut res = T::id();
  for val in list {
    res = res.op(val);
  }
  res
}

And now this single function can add all integers in a list or concatenate all strings in a list. Or whatever the relevant equivalent is for any monoid. And this helper is reusable in any generic context where we know that T: Monoid. DRYness galore.

All very familiar, I hope?

Monads: I don't think it will be helpful to define monads here. What is important is that Rust's type system does not allow us to abstract over properties like monads. Why? Because:

In other words, there's no way in Rust for us to say

impl Monad for Vec { ... } // Look, Ma, no `<T>`!

Vec<T> is a type, but Vec is a type-constructor—it takes a type T as an argument and produces another type Vec<T>4. Being able to abstract over monads (like we abstracted over monoids above) enables a very nice do {} notation in Haskell, which simultaneously supports:

just because the two corresponding type constructors implement the same abstraction—monad! Such is the power of higher-kinded abstraction. Now, if you actually want to concretely comprehend this, then:

:wink:

So what now?

In the end, what matters in rust isn't whether or not we define a monad trait, but whether we can. Support for such higher-kinded abstractions is typically brought up in discussions about rust support for either:

  • abstracting over higher-kinded types, or
  • associated type constructors (which offers the requisite abilities, possibly at the expense of poorer type inference).

El Fin

Footnotes

  1. This really nice table shows its relation to other tragic epithets of abstract algebra. If it isn't abundantly unclear, I don't ...uh... lava the terminology.
  2. This is lie, or, at least, not fully general. I'm brushing under the rug that you can only implement this for ints once, even though there are clearly at least two different monoids for ints. Supporting both is possible with the classic rust double-dispatch trick, but that's tangential to the narrative.
  3. This is clearly inefficient since we would want to take other as a &str instead of requiring the caller to pass ownership of an allocated value...but then this wouldn't be a mathematical monoid. A rustier variant of monoid can be defined by using other: &<Self as Deref>::Target instead.
  4. Vec is thus a "type-level" function of kind * → *, where each * represents a concrete type. So monads also tend to appear in discussions espousing rust support for abstracting over "higher-kinded types" to support defining and implementing "higher-kinded traits" like monad.
8 Likes

Haven't read all the above, but from a bit of a naive perspective, I think of the difference of these things as whether or not you can pass different kinds of containers to a map() function.

Like if we could have some single global map() function that can accept any ol' Option, Result, or Future, and call that thing's map(), and then return the new Option, Result, or Future.

This isn't doable in Rust atm. It is in Haskell. Even if we change "single global" to "default method on a generic Monad/Functor Trait"

I'm a bit skeptical about the usefulness of being able to map() arbitrary things. It's nice in theory, like you can define generic functions that can work on a wider range of types, and it's amazing for code golf, but in reality I'm not so sure it really offers that much improvement.

(no doubt there's many other usefuless of HKT's, just speaking to my naive understanding of these super generic "categories")

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.