←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.209s | 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. 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.