4 ms·
This is yet another "monad" that can't do the list monad, and is not therefore actually a monad. The function passed to bind may be called zero times, once, or
by jerf 16y ago
This is yet another "monad" that can't do the list monad, and is not therefore actually a monad. The function passed to bind may be called zero times, once, or n times. (Or perhaps rather, any number of times, but I think phrasing it this way underscores the place where many putative monads fall down.)
I mention this because this is actually critical to understanding the nature of Monads, it's not just an incidental point.
One way of understanding Monads is that they turn everything that would be a "statement" in most languages into a "function", and these functions are nested in each other. (Well, arguably this is what it is, but it's not necessarily the best understanding. It is in my opinion the best start, though; at least it leaves you with a true understanding, even if all the clever tricks aren't obvious yet.) Statement one actually calls into statement two calls into statement three, etc. The Maybe monad works by taking these functions (the collection of which constitute the "monadic value"), but wrapping it in a check for Nothing, and if you have a Nothing it simply returns Nothing. This has two effects: It returns Nothing, and because it stopped calling down the function chain, it stops "executing" your monadic value. Otherwise it extracts the value from its wrapper and "keeps going" into (not down, into; each bind or <- is a nested function call) the rest of the monadic value.
The List monad works by taking each element for a given line in sequence, then calling the remainder of the monadic value, hence the classic
cartesian_closure = do
a <- [1, 2, 3]
b <- [4, 5, 6]
return (a, b)
which will return
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
See how we start with 1 for "a", then "call" the remainder of the Monadic value, which itself starts with 4 for "b" and proceeds on, and so forth. The bind function for the list monad is responsible for poking through the list like this.
By turning "statements" into "functions" which are then something we can manipulate like any other functions, Monads provide the "programmable semicolon" functionality, though this isn't the best way to understand them.
(This is why the State monad is pure, not "cheated imperative". It takes the old functional paradigm of passing down a state value as a parameter to a series of recursive functions, and abstracts out that parameter. It's exactly the same as the "old" functional answer, just spelled differently.)
(Edit: This still glosses over some things because it's a post, not a place I can spend three hours polishing. I hesitate to add another "monad tutorial" to the intarwebs...)
- jmillikin 16y ago> This is yet another "monad" that can't do the list monad, > and is not therefore actually a monad. The function passed > to bind may be called zero times, once, or n times. (Or > perhaps rather, any number of times, but I think phrasing > it this way underscores the place where many putative > monads fall down.) The author's implementation support lists just fine -- Monad is just a typeclass, which can be emulated using Python's inheritance. Unfortunately dynamic typing makes the code much uglier than in Haskell, but that's to be expected. class List(Monad): def __init__(self, items): self.__items = list(items) def __str__(self): return str(self.__items) def bind(self, func): items = [] for ii in map(func, self.__items): items.extend(ii.__items) return List(items) print List([1, 2, 3, 4]) >> (lambda x: List([x * x]))
- jerf 16y agoCan you show me how to convert the example I showed, using the yield-based notation? I did try but I couldn't get it to do much, not even what I thought it should. (I did add the unit for list.) print List([1, 2, 3]) >> (lambda a: List([4, 5, 6]) >> lambda b: List([(a, b)]))) does work as I expect, but I was thinking about the yield syntax when I said it doesn't work. If you can provide it I will stand corrected.
- jmillikin 16y agoOh, I didn't look much at the yield-based stuff -- I think it looks worse than the lambdas, since it depends on magic exceptions and can't be used to write procedures which work for any monad. If it doesn't work, I'm not surprised.