←back to thread

A list is a monad

(alexyorke.github.io)
153 points polygot | 2 comments | | HN request time: 0s | source
Show context
nemo1618 ◴[] 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 #
blakehawkins ◴[] No.44447152[source]
Can you explain the nondeterminism part of your comment more?
replies(3): >>44447260 #>>44447375 #>>44447400 #
1. pkal ◴[] 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 #
2. ryandv ◴[] 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...