A list is a monad

I think this adds more confusion than it removes.

A list is not a monad. A list is a data structure; a monad is more like a "trait" or "interface." So you can define a List type that "implements" the monad interface, but this is not an inherent property of lists themselves. That's the sense in which a list "is a" monad: the OOP sense.

Haskell's List monad provides a model for nondeterminism. But that certainly isn't the only way List could satisfy the monad interface! It was a deliberate choice -- a good choice, possibly the best choice, but a choice nonetheless.

Can you explain the nondeterminism part of your comment more?

Isn’t it the case that for a given functor (on Set) there can only be at most one Monad structure?

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)]

... or in more explicit monadic do-notation:

    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)]

and so on.

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.

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.

That's right, and you see this directly reflected in the "types" of the transition functions for DFAs and NFAs, respectively [0] [1]:

    δ : Q × E ⟶ Q
    δ : Q × E ⟶ P(Q)

... where Q denotes the set of the automaton's states, E its alphabet of input symbols, and P the power set operation. Deterministic automata arrive at a definite, single state drawn from Q, while non-deterministic automata may arrive at a set (~list) of possible states, when given a current state from Q and next input symbol from E.

[0] https://en.wikipedia.org/wiki/Deterministic_finite_automaton

[1] https://en.wikipedia.org/wiki/Nondeterministic_finite_automa...

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)

Ah right. Didn’t remember it correctly.

The cross-product is not to be confused with the Cartesian product, which is related to the (in this case unfortunately named) "cross join" in SQL. Cross products operate in ℝ³, while Cartesian products are just defined over sets. The standard List monad instance uses the latter.

Hi, I completely agree. "A" list isn't inherently a monad, and that is where my metaphor starts to fall apart a bit (my post title furthers this issue.)

I can clarify this earlier in part 1 or 2 instead of in to-be-written part 3.

ah yes my bad! good callout

Its a harmful metaphor and clickbait title.

> A list is not a monad. A list is a data structure; a monad is more like a "trait" or "interface."

You operate with things that are bound to PL notions of specific languages. Instead, consider that list isn't a data structure, it's an abstraction that defines a multitude of position-ordered values. The multitude of position-ordered values called "list" is a presented entity of "monad", because it can be used as a valid input for a monadic computation defined consistently (in terms of the monad laws).

This seems harsh to the point of being untrue...