How I finally learned what a "monad" is

25

gthm 4 years ago | link

I did a PhD in maths where I had to do a lot of algebraic geometry, so I’m comfortable with category theory and its concepts and applications. I’ve never seen those ideas being used in nontrivial or useful ways in programming, and by now think that either me or a lot of other people are missing some point. I’m not sure which.

Category theory became popular in mathematics, and especially algebraic geometry, because it provided a “one higher level” from which to look upon the fields and see that a lot of the ideas we were working with were actually a shadow of a single more abstract idea. For example, the direct products of groups, rings, fields, vector spaces and so on were understood as different incarnations of the category-theoretic product. This helped to standardize a lot of arguments, and give names to some concepts differing groups had been grappling with in isolation before. Grothendieck was able to wield these abstract notions so deftly that he could use them to “take compass bearings” and figure out in what directions he should go. That is unbelievably powerful.

In programming, I can see how one would model the state of a program as a monad. A monad is basically defined around the idea that we can’t always undo whatever we just did, so that makes sense. I’ve also read a fair number of Haskell programmers and their explanations of how category theory fits into programming. None of it seems to even have the promise of the same levels of usefulness as we’ve seen in mathematics, and a lot of it seems to be actively harmful by raising jargon barriers around trivial ideas.

8

bsima 4 years ago | link

That is a great story, I would definitely read more of your writing about math if you shared it somewhere.
4

JordiGH 4 years ago | link

I too have encountered category theory during my maths degree (never managed to get the PhD, though), and I also agree that category theory in programming seems very out of place. The most interesting application I’ve seen for it is in homological algebra, but I’m pretty sure no programmer has any interest in abelian categories. The most prototypical functor for me is the Galois functor, which programmers have no need for.

The result is that when I see computer people talk about category theory, it’s all utterly foreign to me. They tell me I should like it because I like mathematics, but I do not. I’ve made some effort to understand why they like it and have never been very convinced by it, as unconvinced as you seem yourself.
4

inactive-user edited 4 years ago | link

I’ve also read a fair number of Haskell programmers and their explanations of how category theory fits into programming.

I’d be interested in your take on this discussion, in particular the first comment by Gershom Bazerman, as well as his post here. It seems like he has a good perspective on it, but I don’t have the mathematical knowledge to really confirm that one way or the other. Or maybe you’ve already read this particular stuff and dismissed it; in either case it’d be handy to get a sense of what you think to place it in context, if you’re willing.

Here is another post which your comment reminded me of, which I wish I had the mathematical ability to fully understand; I’d also love to hear what you think about that as well.

I’m really not trying to challenge anything you said about the misapplication of CT in Haskell/programming in general (if I haven’t emphasized this enough at this point, I don’t think I’m qualified to do so), I’m just always interested in adding more data to my collection, hoping that at some point I’ll have built up the mathematical maturity to understand the different positions better.

None of it seems to even have the promise of the same levels of usefulness as we’ve seen in mathematics, and a lot of it seems to be actively harmful by raising jargon barriers around trivial ideas.

As a programmer who barely understands category theory, all I can say is that I’ve personally found the small number of concepts I’ve encountered useful, and, most importantly, more useful than anything else out there (which I’ll generalize as “design patterns and other vague, poorly specified stuff”) for providing a basis for designing modular structures to base programs on. I find that the most basic concepts presented in category theory map well to the kind of abstraction present in programming, and I’d love to get a better sense of where you find the jargon barriers to be and how we could eliminate those (and fwiw I think this is a general problem in programming, not limited to Haskell nerds dropping category theory terms into their discussions). In particular I’ve found concepts like Monoid, Monad, and Functor to be useful–especially in understanding how they interrelate and can be used together. They’ve enhanced my ability to think conceptually and logically about the kinds of structures I deal with in programming all the time, even where I may not be applying these structures directly in whatever program I’m considering. I may be doing it wrong, but insofar as I’ve developed the correct intuition around these things, they seem useful to me.

So I can readily accept that we have not been able (and maybe never will be able!) to harness category theory at the level Grothendieck did, but it seems like right now it’s yielding results, and part of the value is simply in the exploration and application of a different rigor to programming as a practice. Maybe in ten or twenty years we’ll look back at the folly of applying category theory to programming, but I rather think it’s more likely that we’ll see it as a step on the path toward discovering something deeper, more rigorous and powerful, and more beautiful than what we can imagine for designing programs right now.

Or maybe we’ll go back to being obsessed with design patterns and UML. If that’s the case I hope I’ll have quit and gone into being an organic farmer in Vermont or something.
1

xtian edited 4 years ago | link

I’m interested in hearing more about this as well. It’s been a long-standing question for me whether continuing to investigate category theory would help me write better programs. I have no background in higher math, but my understanding/assumption has been that category theory is relevant to programming insofar as it facilitates composition.

As I see it, the fundamental problem of software design is economically accommodating change. We try to facilitate this by selectively introducing boundaries into our systems in the hopes that the resulting structures can be understood, modified, and rearranged as atomic units. I don’t think it’s controversial to say that our overall success at this is mixed at best.

The promise of category theory seems to be that, rather than relying on hearsay (design patterns) or our own limited experience, we can inform our choices of where to introduce boundaries from a more fundamental, abstract space where the compositional properties of various structures are rigorously understood.

But like I said, this is very much an open question for me. I would love to be convinced that, although there is clearly some overlap, the fields of category theory and software design are generally independent and irrelevant to each other.

9

janiczek 4 years ago | link

I know this is not the point of your article, but did you ever find the Maybe monad instance that is in Elm core library? ie. Maybe.andThen?

With it the motivating example looks like:

comments
    |> Maybe.andThen List.first
    |> Maybe.map (\c -> div [ id "first-comment" ] [ text c ])
    |> Maybe.withDefault (div [] [ text "No comments" ])

5

bsima 4 years ago | link

I did not, but I figured there would be something like this somewhere in the Elm ecosystem. I wrote this a while ago and I haven’t used Elm in at least 8 months so excuse my ignorance, and thank you for pointing this out.

6

brendan 4 years ago | link

Yep, this is how I figured out monads too, but when using Rust! There is more to them though - the laws are important, but it’s sometimes easier to learn them by examples first!

3

edd edited 4 years ago | link

Can you show an example where a monad is useful in a Rust program?

(I’m not a functional programmer, and have never knowingly used a monad)
1. 10
  steveklabnik 4 years ago | link
  I learned about monads via Maybe in Haskell; the equivalent in Rust is called Option.
  
  Option<T> is a type that can hold something or nothing:
  
  enum Option<T> { None, Some(T), }
  
  Rust doesn’t have null; you use option instead.
  
  Options are a particular instance of the more general Monad concept. Monads have two important operations; Haskell calls them “return” and “bind”. Rust isn’t able to express Monads as a general abstraction, and so doesn’t have a particular name. For Option<T>, return is the Some constructor, that is,
  
  let x = Option::Some("hello");
  
  return takes some type T, in this case, a string slice, and creates an Option<T>. So here, x has the type Option<&str>.
  
  bind takes two arguments: something of the monad type, and a function. This function takes something of a type, and returns an instance of the monad type. That’s… not well worded. Let’s look at the code. For Option<T>, bind is called and_then. Here’s how you use it:
  
  let x = Option::Some("Hello"); let y = x.and_then(|arg| Some(format!("{}!!!", arg))); println!("{:?}", y);
  
  this will print Some("Hello!!!"). The trick is this: the function it takes as an argument only gets called if the Option is Some; if it’s None, nothing happens. This lets you compose things together, and reduces boilerplate when doing so. Let’s look at how and_then is defined:
  
  fn and_then<U, F>(self, f: F) -> Option<U> where F: FnOnce(T) -> Option<U> { match self { Some(x) => f(x), None => None, } }
  
  So, and_then takes an instance of Option and a function, f. It then matches on the instance, and if it’s Some, calls f passing in the information inside the option. If it’s None, then it’s just propagated.
  
  How is this actually useful? Well, these little patterns form building blocks you can use to easily compose code. With just one and_then call, it’s not that much shorter than the match, but with multiple, it’s much more clear what’s going on. But beyond that, other types are also monads, and therefore have bind and return! Rust’s Result<T, E> type, similar to Haskell’s Either, also has and_then and Ok. So once you learn the and_then pattern, you can apply it across a wide array of types.
  
  Make sense?
  1. 3
    
    edd 4 years ago | link
    
    Make sense?
    
    It absolutely does! I’ve used and_then extensively in my own Rust code, but never known that I was using a monad. Thanks for the explanation Steve.
    
    But there’s one gap in my understanding now. Languages like Haskell need monads to express things with side-effects like IO (right?). What’s unique about a monad that allows the expression of side effects in these languages?
    1. 7
      
      steveklabnik 4 years ago | link
      
      No problem!
      
      This is also why Rust “can’t express monads”, we can have instances of individual monads, but can’t express the higher concept of monads themselves. For that, we’d need a way to talk about “the type of a type”, which is another phrasing for “higher minded types”.
      
      So, originally, Haskell didn’t have monads, and IO was done another way. So it’s not required. But, I am about to board a flight, so my answer will have to wait a bit. Maybe someone else will chime in too.
      1. 2
        
        inactive-user edited 4 years ago | link
        
        higher minded types
        
        (Just so others don’t get confused, I think you meant “kinded” here, right?)
        
        1
        
        steveklabnik 4 years ago | link
        
        Heh, yes. Thanks.
    2. 3
      
      puffnfresh 4 years ago | link
      
      A monad has the ability to express sequence, which is useful for imperative programming. It’s not unique, e.g. you can write many imperative programs using just monoid, functor, applicative or many other tools.
      
      The useful function you get out of realising that IO forms a Monad is:
      
      (>>=) :: IO a -> (a -> IO b) -> IO b
      
      An example of using this function:
      
      getLine >>= putStrLn
      1. 4
        
        puffnfresh 4 years ago | link
        
        I should say Monad is unique in being able to express that line of code, but there’s many imperative programs which don’t need Monad. For example, just Semigroup can be used for things like this:
        
        putStrLn "Hello" <> putStrLn "World"
        
        Or we could read some stuff in with Applicative:
        
        data Person = Person { firstName :: String, lastName :: String } liftA2 Person getLine getLine
        
        So Monad isn’t about side-effects or imperative programming, it’s just that imperative programming has a useful Monad, among other things.
      2. 2
        
        edd edited 4 years ago | link
        
        You are way ahead of me here and I’m probably starting to look silly, but isn’t expressing sequence in imperative languages trivial?
        
        For example (Python):
        
        x = f.readline() print(x)
        
        x must be evaluated first because it is an argument of the second line. So sequence falls out of the hat.
        
        Perhaps in a language like Haskell where you have laziness, you can never be sure if you have guarantees of sequence, and that’s why a monad is more useful in that context? Even then, surely data dependencies somewhat impose an ordering to evaluation?
        
        For me, the utility of Steve’s and_then example wasn’t only about sequence, it was also about being able to (concisely) stop early if a None arose in the chain. That’s certainly useful.
        
        2
        
        puffnfresh 4 years ago | link
        
        but isn’t expressing sequence in imperative languages trivial?
        
        Yes.
        
        In Haskell it is too:
        
        (>>=) :: IO a -> (a -> IO b) -> IO b
        
        But we generalise that function signature to Monad:
        
        (>>=) :: Monad m => m a -> (a -> m b) -> m b
        
        We don’t have a built in idea of sequence. We just have functions like these. A generalisation which comes out is Monad. It just gives code reuse.
        
        1
        
        elldritch edited 4 years ago | link
        
        Maybe is an instance of a monad, and there are many different kinds of monads. If you think of Maybe as “a monad that uses and_then for sequencing”, then “vanilla” sequencing can be seen as “a monad that uses id for sequencing” (and Promises in JavaScript can be seen as “a monad that uses Promise#flatMap for sequencing”).
        
        Yes, expressing sequence in eager imperative languages is trivial because you can write statements one after the other. Now imagine a language where you have no statements, and instead everything is expressions. In this expression-only language, you can still express sequence by using data dependencies (you hit this nail right on the head). What would that look like? Probably something like this (in pseudo-JavaScript):
        
        function (next2) { (function (next) { next(f.readline()) })(function (readline_result) { next2(print(readline_result)) }) }
        
        with additional plumbing so that each following step has access to the variables bound in all steps before it (e.g. by passing a dictionary of in-scope variables). A monad captures the spirit of this, so instead of doing all the plumbing yourself, you choose a specific implementation of >>= that does your plumbing for you. The “vanilla” monad’s (this is not a real thing, I’m just making up this name to mean “plain old imperative sequences”) implementation of >>= just does argument plumbing for you, whereas the Maybe monad’s implementation of >>= also checks whether things are None, and the Promise monad’s implementation of >>= also calls Promise#then and flattens any nested promises for you.
        
        What’s useful here is the idea that there is this set of data structures (i.e. monads) that capture different meanings of “sequencing”, and that they all have a similar interface (e.g. they have all an implementation of >>= and return with the same signature) so you can write functions that are generic over all of them.
        
        Does that make sense?
    3. 2
      
      janiczek edited 4 years ago | link
      
      There is a comment below saying it pretty succintly:
      
      A monad is basically defined around the idea that we can’t always undo whatever we just did (…)
      
      To make that concrete, readStuffFromDisk |> IO.andThen (\stuff -> printStuff stuff) - in the function after andThen, the “stuff” is made available to you - the function runs after the side effect happened. You can say it needed specific API and the concept of monads satisfies that API.
      
      Modelling IO with monads allows you to run functions a -> IO b (take a pure value and do an effectful function on it). Compare that to functions like a -> b (Functor). These wouldn’t cut it - let’s say you’d read a String from the disk - you could then only convert it to another string but not do an additional effect.
      
      EDIT: I might not have got the wording entirely right. I ommited a part of the type annotation that says the a comes an effect already. With Functor you could not reuse values that came from an effect; with Monad you can.

3

shapr 4 years ago | link

I like Max Kreminski’s thoughts that center around the problem solution ordering problem: https://mkremins.github.io/blog/doors-headaches-intellectual-need/

He talks about a level in a game where you accidentally pick up a key before you find the locked door. In the next level when you see a locked door, you don’t realize you need to go find a key. Why not?

My paraphrase is “you won’t understand a solution if you’ve never recognized the problem it solves”.

He picks on high school math next, why care about learning trig or calculus if you don’t see the need?

Read the post for the monadic punchline that ropes in game design and education, read the links in the post for more depth and detail.

3

theblacklounge 4 years ago | link

This is a monad tutorial tutorial.

2

yann 4 years ago | link

I doubt that was the intention? It’s more like a personal experience report.

2

yann 4 years ago | link

I’m a student of philosophy, biology, and mathematics.

quotes Deleuze in an article about functional programming

Are you me lmao. Although I’m a math student:) How did you get into Deleuze and Guattari?

3

bsima 4 years ago | link

Accidentally :) I wrote my undergrad thesis on Levinas, so I was exposed to the French thinkers and naturally read bits of Foucault and D&G.
3

steveklabnik 4 years ago | link

Deleuze is my favorite :D
1. 1
  
  yann 4 years ago | link
  
  Wow that’s so great to hear!:D Deleuze is one of the primary reasons behind the gust of motivation for mathematics I’ve gained in the past year. It’s really great how it made me sprawl in so many directions, dynamical systems over formal logic to abstract algebra. It was also really awesome to see these intersect when in the middle of studying for my analysis 2 exam, I stumbled upon an article connecting Taylor series and major analysis topics to algebraic types:D