←back to thread

A list is a monad

(alexyorke.github.io)
153 points polygot | 5 comments | 29 Jun 25 17:53 UTC | HN request time: 0.001s | source
Show context
nemo1618 ◴[02 Jul 25 18:20 UTC] No.44447106[source]▶
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.

replies(4): >>44447152 #>>44447222 #>>44448276 #>>44451386 #
1. blakehawkins ◴[02 Jul 25 18:25 UTC] No.44447152[source]▶
Can you explain the nondeterminism part of your comment more?
replies(3): >>44447260 #>>44447375 #>>44447400 #
2. ryandv ◴[02 Jul 25 18:34 UTC] No.44447260[source]▶
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.
3. pkal ◴[02 Jul 25 18:45 UTC] No.44447375[source]▶
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.
replies(1): >>44447462 #
4. wk_end ◴[02 Jul 25 18:48 UTC] No.44447400[source]▶
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.

5. ryandv ◴[02 Jul 25 18:54 UTC] No.44447462[source]▶
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...