←back to thread

A list is a monad

(alexyorke.github.io)
153 points polygot | 1 comments | 29 Jun 25 17:53 UTC | HN request time: 0.22s | 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 #
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 #
1. 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.