A list is a monad

What helped me grok the mathematical rigor is: If you have a series of monad operations that exist purely in monad world -- in Haskell, if your expression is parametric over the type of the monad -- you shouldn't have to worry about how you do it.

This is what monads being categorically commutative ("a monoid in the category of endofunctors") buys you. You want to turn monad X into monad Y? Sure, just join, flatten, return, bind in whatever way makes the type checker happy. Anything that only uses what's in the Monad typeclass must necessarily be a monad morphism, so if you're generic over your monads, you get that for free. And of course `fmap` and `bind` are required to be parameterized monad morphisms, so there's a lot you can get for free.

Yep, you need category theory to express something as trivial as the definition of a monad.

The more constrained your theory is, the fewer models you have of it and also the more structure you can exploit.

Monads, I think, offer enough structure in that we can exploit things like monad composition (as fraught as it is), monadic do/for syntax, and abstracting out "traversals" (over data structures most concretely, but also other sorts of traversals) with monadic accumulators.

There's at least one other practical advantage as well, that of "chunking".

A chess master is more capable of quickly memorizing realistic board states than an amateur (and equally good at memorizing randomized board states). When we have a grasp of relevant, powerful structures underlying our world, we can "chunk" along them to reason more quickly. People familiar with monads often can hand-wave a set of unknowns in a problem by recognizing it to be a monad-shaped problem that can be independently solved later.

See for instance the MonadIO typeclass from Haskell [0]. Constraining against this typeclass allows one to write monadic code / do-notation that works with any monad, so long as that monad supports the execution of IO statements.

Now for instance, arbitrary effects (error handling, resource management, etc) can be composed on top of an IO monad (e.g. via monad transformers), and MonadIO code, that is written to only depend on the IO effects, can still be executed in these contexts with more effects layered on top.

[0] https://hackage.haskell.org/package/base-4.21.0.0/docs/Contr...

Traverse (or foldM) is probably a good start, likely the most useful monad-generic (or applicative-generic) function, that is simple but incredibly powerful and useful.

More generally, Monads essentially support function composition between monadic functions, so you can use it to write code that is agnostic to the monad it runs in. This can let you write e.g. prod. Code that is in IO or Async or Maybe, but for unit testing run it in Identity.

Also, it allows syntax sugar such as do notation that makes it clear to work with even when you know which monad you're working in.

Your basic problem is that your programming language can’t express the concept cleanly. You need what’s called “Higher-Kinded Types”.

To give you a concrete example, in C#

Func<A, B>, List<A> -> List<B>

Func<A, B>, Task<A> -> Task<B>

Func<A, B>, Func<C, A> -> Func<C, B>

Can’t be expressed using a generalisation. But in Haskell, you can write

(Functor F) => Func<A,B>, F<A> -> F<B>

One of the biggest things that makes monads hard to understand is that the type systems of most languages can’t represent them. Annoying, that includes the “typeless” ones.

> If all monad instances work differently what is the value of the Monad interface? What kind of usefull generic code can one write against the Monad interface.

Code that composes a bunch of operations, for whatever kind of composition those operations need (some people call Monad "programmable semicolons", because it's a lot like sequencing). E.g. traversals of datastructures, or some kind of "do this in a context" operation. Essentially any function you pass a "callback" to should probably be written in terms of monads so that it can accept callbacks that need different kinds of composition beyond just being called at different points in the control flow.

Here is an analogy. List is a container whose elements can be any type. There are general operations applying to a list, e.g. map, reduce, filter, find, etc. Any data type (int, float, or bool) of list elements can use these same operations regardless.

It’s similar for monad. If you can provide a unit constructor to turn an object value into a monad value and a “map” operation that unwraps a monad value, applies a function to it, and wraps the result, you have monadized the object type. Your objects can participate in any algorithm operates on monads.

The monad algorithms are the same. The only things different are the unit constructor and the mapping function.

Everything in here, for a start:

https://hackage.haskell.org/package/base-4.21.0.0/docs/Contr...

https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-...

Lots of useful generic code. MapM is a version of `map` that works with any Monad, `sequence` works with any monad, and so on. These are used very frequently.

But the bigger benefit is when syntax sugar like `do` notation comes in. Because it works for any Monad, people can write their own Monads and take advantage of the syntax sugar. That leads to an explosion of creativity unavailable to languages who "lock down" their syntax sugar to just what the language designers intended. In other words, what requires a change to other languages can often be a library in Haskell.

yes, exactly, not sure why your comment was downvoted. Also, generally it's not cardinality of 0..1, it is `[]` vs `xs:[]`, that is - either empty, or a multitude of values, where 1 is a specific instance of the multitude (singleton).

Wow, this is a great post, thank you for sharing. It echoes my thoughts exactly.

Yes, this is how you learn math. It helps to pair definitions with examples and exercises.

I mean if someone is learning chess for the first time, then yes you should start with the rules rather than jumping right into waxing philosophic about positional strategy to show off how smart you are.

Yes.

If you don't already know category theory, learning it is hard. The terms on wikipedia seem to form a dense graph of links. It's hard to get a foothold of comprehension. For people that already know C++, or are at least familiar with this syntax, this is more useful than describing it in haskell syntax or category theory. There seems to be a chicken and egg problem regarding haskell and monads. Learning c++ may be harder or easier than category theory. I'm no sure, as I don't understand either one of them. But this syntax makes more sense to me than something expressed in terms of category theory vocabulary.

For people who are more familiar with C++ than category theory, yes.

Its a harmful metaphor and clickbait title.

Nope. It's that there's only one lawful Functor instance. But Applicatives and Monads can be multiple - lists are the classic example (zip vs cross-product)

When you bind with (the Haskell definition for) the List monad - `someList >>= \someElement -> ...` it's like you're saying "this is a forking point - run the rest of the computation for each of the possible values of someElement as taken from someList". And because Haskell is lazy, it's (pardon the informality here) not necessarily just going to pick the first option and then glom onto it if it, say, were to cause an infinite loop if the computation were eagerly evaluated; it'll give you all the possibilities, and as long as you're careful not to force ones that shouldn't be forced, you won't run into any problems. Nondeterminism!

A nice demonstration of this is writing a very simple regex matcher with the List monad. A naive implementation in Haskell with the List monad Just Works, because it's effectively a direct translation of Nondeterministic Finite Automata into code.

From automata theory, you might know that nondeterministic automata are represented by a set of states. Deterministic automata are always in a specific state, while nondeterministic ones are in multiple at once. Lists are used for non-determinism in Haskell the same way as a set, mainly because they are easier to implement. But the total order that a list induces over a set is not that relevant.

Determinism, in that given some set of inputs you only ever receive one output.

Non-determinism, in that given some set of inputs it's possible to receive a collection (a list) of possible outputs.

With lists you can express things like all possible pairings of all possible outcomes, or the Cartesian product:

    ghci> liftM2 (,) ['a', 'b', 'c'] [1,2,3]
    [('a',1),('a',2),('a',3),('b',1),('b',2),('b',3),('c',1),('c',2),('c',3)]

    ghci> :{
    ghci| do
    ghci|   x <- ['a', 'b', 'c']
    ghci|   y <- [1,2,3]
    ghci|   return (x, y)
    ghci| :}
    [('a',1),('a',2),('a',3),('b',1),('b',2),('b',3),('c',1),('c',2),('c',3)]

Not exactly. The flatMap() operation itself isn’t going to flatten an arbitrarily nested todo list. It just concatenates the lists that are returned after applying the callback to each item.

The monad part is about what happens if you call flatMap() repeatedly. That is, each call to flatMap() is one action, and these actions can be nested without affecting the result.

Yes, your understanding is correct. It's literally calling map() on an array, followed by a flat().

Sorry, I should have added more context to my post. I edited my post and added a link to the MDN definition of the flatMap function.

This is a good explanation:

https://users.scala-lang.org/t/what-is-a-monad-in-scala/4169

It's like... what would you call all types that have a .write() method? Writable right? What would you call all types that have a .dispose() method? Disposable. What would you call all types that have a .flatMap() method? Monad obviously.

something that you can call flatMap() on.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

First off, I'm not sure it's even worth it to understand this stuff... Second, someone should be along to slam it soon enough and insist I've missed some gibberishy business that you'll never understand.

With those caveats in mind, here's a more intensive scala-based monad tutorial I made:

https://github.com/zaboople/techknow/blob/master/scala/monad...

But really, don't burn up too much of your short life trying to come to terms with this stuff. There's a reason most languages don't get around to supporting Monads...

You might like https://philipnilsson.github.io/Badness10k/escaping-hell-wit... which is a longer version of the same kind of argument.

To get a minimal idea, you can think about a monad as of a parametrized class: M<T>. Its functioning follows "monad laws" that allow you to do certain things with it, and with the value(s) of T wrapped my it. In particular, you can always "map" the values:

  M<T1>::map(f: (T1 -> T2)): M<T2>
  List<int>([1, 2, 3]).map(x => toString(x)) == List<string>(["1", "2", "3"])

  M<M<T>>::flatten(): M<T>  // [["a", "b"], ["c", "d"]] -> ["a", "b", "c", "d"]

  M<T1>::flatMap(f: (T1 => M<T2>)): M<T2>
  List(["a b", "c d"]).flatMap(x => x.split()) == List(["a", "b", "c", "d"])

But Optional<T> is also a monad:

  let x: Optional<int> = Some(1);
  let y: Optional<int> = Nothing;
  x.map(n => n + 1).map(n => n * 2) == Some(4);
  y.map(n => n + 1).map(n => n * 2) == Nothing;

You can also notice how chaining of map-like operations does operation sequencing:

  fetch(url).then(content => content.json()).then(data => process(data))

  async () => {
    const response = await fetch(url);
    const data = await response.json();
    process(data);
  } 

I wrote a post about a highly related topic here. It may be helpful to you in understanding the parent comment: https://chadnauseam.com/coding/random/how-side-effects-work-...

[dead]

You're quite right! Thanks for the correction. I should have said that a list is an element of a free algebra over the List monad, which is less pithy.

Sorry for moaning - it's just the usual despair that I feel every time I read a new explanation and fail to understand it. This isn't your fault.

> From an OOP perspective, they have some properties that make them, in some sense, sorta like containers, e.g., they contain a value like the Maybe monad.

Not always! I find this is a big source of confusion; not all monads contain values, sometimes beginners think they can or should "get the value out" of a monad and that tends to lead to writing the wrong kind of code.