Gregg Reynolds wrote:
Tillmann Rendel wrote:
An example where it would be wrong to ignore e:
sum ([1, 2] >>= const [21])
This expression should evaluate to sum [21, 21] = 42, not sum [21] = 21.
Sigh. I hate it when this happens. Just when I thought I had it figured out, it turns out I'm clueless. This is very enlightening and should definitely be included in any monad tutorial. Actually you don't even need "sum" and "const" to demo the point, "[1,2] >>= \x -> [21]" evals to "[21, 21]" in ghci. And I have absolutely no idea why. Very mysterious, the Kleisli star. :(
Just walk through the evaluation step by step, it's not so mysterious. [1,2] >>= \x -> [21] == {CT definition of bind} join . fmap (\x -> [21]) $ [1,2] == join [(\x -> [21]) 1, (\x -> [21]) 2] == join [[21],[21]] == [21,21] Or if you prefer to use the Haskell function definitions instead of the category theory definitions (it's all the same): [1,2] >>= \x -> [21] == concatMap (\x -> [21]) [1,2] == concat . map (\x -> [21]) $ [1,2] == concat [(\x -> [21]) 1, (\x -> [21]) 2] == concat [[21],[21]] == [21,21] This is exactly the point I was raising earlier. The "statefullness" of monads has nothing to do with IO, but every monad has some of it. In general it is wrong to throw it away just because the function passed to bind happens to ignore the value associated with it. There are some cases where that can be correct, but in general it is not. For lists, we can envision the statefullness as a path through a decision tree. To get the intuition right, it's easiest to pretend that we never call join (or that join does nothing). If we don't call join, eventually after a number of binds or maps we'll end up with some value of type [[...[a]...]]. We can draw that value out as a B-tree where each level has a branch of whatever arity it needs. In this B-tree, every leaf is associated with a unique path through the tree and therefore they can be distinguished. The reason the above example works the way it does is that the initial list has two leaves each associated with their unique paths through this tree of choices. The function passed into bind is a continuation of sorts. So, given that we can non-deterministically choose either of the paths in the original tree, for each choice we must then continue with (\x -> [21]) applied to the seed value for that choice (1 or 2, as appropriate). Because we had two choices initially, and from there we have only one choice, we will have 2*1 choices in the end: /\ / \ (1) (2) | | | | 21 21 If we imagine a finite state automaton, we might think that the two 21s could be collapsed together since they represent the same "state". But that is not so: the list monad is for *paths* through an FSA not for states in an FSA. (For states in an FSA we'd want the set monad instead.) Of course for the list monad we don't actually keep around the decision tree. In fact lists generalize over all possible decision trees which could yield the given distribution of path-endpoints, so it's not quite the way envisioned above. -- Live well, ~wren