8 ms·

Monoids, Functors, Applicatives, and Monads: Main Ideas

94 points by abishekk92 12y ago

DanWaterworth 12y ago
I've had an idea for a monad tutorial that I think might be quite instructive, but haven't had the motivation yet to write. In essence, the idea is that you are led through the process of implementing: early exit, nondeterminism, threaded state and coroutines using call/cc in scheme. Then monads are introduced as a way of typing those patterns.
- thirsteh 12y ago
  I'm 99% sure this is the way to do it. You can't explain any field of math, much less category theory, without doing exercises.
- peteretep 12y ago
  Have you seen "You Could Have Invented Monads"?
  - agumonkey 12y ago
    I understand concepts better when taken outside their ''''natural'''' environment (namely strongly paramectrically typed [lazy] languages). I often link these two : http://stackoverflow.com/questions/11871065/monads-in-javascript http://stackoverflow.com/questions/11871065/monads-in-javasc... http://dorophone.blogspot.fr/2011/04/deep-emacs-part-1.html http://dorophone.blogspot.fr/2011/04/deep-emacs-part-1.html
- mdcox 12y ago
  It seems like those with functional programming experience either already understand monads or grasp it quickly. At the same time, those without it have an instinctual eye-glaze when shown Haskell, or a lisp. Would it be better to use Python or Javascript which more people understand but still has that functional flair? Just an idea. Either way I look forward to reading it!
  - karavelov 12y ago
    Dynamically typed languages are not the best choice when you try to explain algebras that work on the type level I guess.
  - chriswarbo 12y ago
    > It seems like those with functional programming experience either already understand monads or grasp it quickly. That's probably survivor-bias (amongst Haskellers, at least); ie. those who haven't grasped it yet probably won't class themselves as Haskellers. > Would it be better to use Python or Javascript which more people understand but still has that functional flair? The problem with using such languages is that they're always dealing with concrete values; in particular they have no concept of interfaces (like Java) or typeclasses (like Haskell). It's certainly possible to use monads in such languages, but it's often hard to justify their use, since there are always less-complex ways to implement particular examples, and without interfaces it's hard to relate the examples together. For example, here are a bunch of monad implementations ("return" and "bind", AKA ">>=") in Javascript, but it's not at all obvious why they are related to each other: function state_return(val) { return [null, val]; } function state_bind(x, f) { return f(x[0], x[1]); } function maybe_return(val) { return [val]; } function maybe_bind(x, f) { return (x.length > 0)? f(x[0]) : []; } function list_return(val) { return [val]; } function list_bind(x, f) { return [].concat.apply([], x.map(f)); } function read_return(val) { return function(x) { return val; }; } function read_bind(x, f) { return function(arg) { f(x(arg))(arg); }; } The problem is that in Javascript, the implementation details are there for all to see. I might want to give you a string which depends on some integer state, but you can always see that it's actually implemented as an array containing an int and a string. You're also free to mess up that array by adding or removing elements from it, which are perfectly valid array operations, but which makes no sense for "stateful values". Interfaces like monads are useful when we're not free to mess around with the implementation; when we must perform all actions through a limited API. When we're dealing with such concerns every day ("I'd like to allow X, but don't want anyone to abuse it and end up with Y") then monads (and functors and applicatives, which they're based on) are really useful as standard APIs for allowing arbitrary operations to be performed, under the control of the API. The only example above that even comes close to this idea is the "reader" monad, implemented with `read_return` and `read_bind`. This is because values in the reader monad lets us manipulate the return values of functions, and even in dynamic languages a first-class function is pretty much a black box, so there's little we can do to mess it up.
- klibertp 12y ago
  I think most monad tutorials would be quite ok if they didn't use words like "monad", "bind", "return" and so on. It's just stupid to insist on using names which mean nothing or when they mean something (return) it's actually opposite of what they're supposed to do. And no, there are no upsides to this: you math-inclined people may think so because you were trained to think that way, but it's simply not true. I suspected this for a long time, but recently I saw a talk from Gilad Bracha - http://www.infoq.com/presentations/functional-pros-cons http://www.infoq.com/presentations/functional-pros-cons - which convinced me that I was right. Scroll to ~22 minutes into the talk for relevant section. Ok, I finally said it. I feel better now, thanks ;)
  - deleted 12y ago
    [deleted]
  - abathologist 12y ago
    I find that talk really painful. I do not recommend it. It is mean spirited, full of misleading characterizations, and - I think - it misses the core point of functional programming. Gary Verhaegen's comment "this was a waste of time" addresses the many problems effectively. Brian Craft's "ugh" addresses others. Either of those comments are more worthwhile than the video itself.
    - klibertp 12y ago
      > I find that talk really painful. I suspect it may be painful in some cases, it's somewhat like a clash of different cultures. The guy is firmly rooted in Smalltalk and Lisp schools of thinking and everything he says is rather obvious for those who share the same background. On the other hand it may be obviously false for people following ML tradition and even more so for recent converts. Watching this talk calmed me down. It turns out that I'm not an idiot, that I know how to do FP (because I quite like it!) and that there's no need to change my ways just because some vocal minority proclaims me a heretic for preferring meaningful names or no-nonsense IO handling. On the whole I think it was an hour well-spent. YMMV ofc.
      - 12y ago
- tel 12y ago
  Almost everyone who "know monads well" agrees with you. Studying monads is silly. It's a pattern you'll eventually recognize and just so happens to have a syntactic trick. Study particular instances.
- inglesp 12y ago
  Sounds not-so-dissimilar to Tom Stuart's "Refactoring Ruby with Monads" (https://speakerdeck.com/tomstuart/refactoring-ruby-with-monads https://speakerdeck.com/tomstuart/refactoring-ruby-with-mona...) which is excellent.
- antoaravinth 12y ago
  What about monads in terms of JS over here: https://blog.jcoglan.com/2011/03/05/translation-from-haskell-to-javascript-of-selected-portions-of-the-best-introduction-to-monads-ive-ever-read/ https://blog.jcoglan.com/2011/03/05/translation-from-haskell...
kinofcain 12y ago
Further evidence for my hypothesis that everyone who has ever understood monads has gone on to write a blog post trying to explain them.
- bad_user 12y ago
  This is because monads are quite simple and effective abstractions, yet they've proven hard to explain effectively, because contrary to other well known abstractions (let's take as an example the Iterator), monads are more abstract and have been used to describe things that don't bear a resemblance to each other in the minds of beginners. Lets take the Iterator - which is simple to explain (an API that allows you to iterate over a collection of items only once, a collection of items which may be infinite), but that has on the other hand strong limitations in what you can implement under it (e.g. the API calls are synchronous and you can only get the items one by one, sequentially). An Iterator can be a Monad if you provide a flatMap / bind implementation with the right behavior and lo and behold, this operation doesn't care about how the items are produced (synchronously or asynchronously or in what order). In OOP terms, you could have Iterator be a subtype of Monad, with the Monad being the more generic interface. So it's hard to explain because it is very generic, can be applied to many things and everybody has an aha! moment once they spot the resemblance in the various monad implementations, hence the urge to write a blog post.
- chocolateboy 12y ago
  ... and failed: > Once you understand what monads are, and why they exist, you lose the ability to explain them to anybody. -- Douglas Crockford [1] [1] http://www.youtube.com/watch?v=dkZFtimgAcM http://www.youtube.com/watch?v=dkZFtimgAcM
  - marcosdumay 12y ago
    How can one lose it? Before understanding it, one also has no ability to explain.
antoaravinth 12y ago
Im not getting the idea of monads here. From my understanding monads does series of transformation( composition, unit , lift ) of a function to do its task. So does monad is similar to Adapter pattern in java? which does make two classes work even though they aren't meant to work. Because it does transform the class/ interface to work with other class, right? Am I missing anything here?
- efnx 12y ago
  I like to think of a Monad in terms of the Monad laws, it makes it much less abstract. https://www.haskell.org/haskellwiki/Monad_laws https://www.haskell.org/haskellwiki/Monad_laws Different monads can have drastically different implementations but they should all obey those laws.
  - AnimalMuppet 12y ago
    And anything that obeys those laws is a monad (if I understand correctly). [Edit: And if the implementing pieces are named correctly.]
    - dllthomas 12y ago
      I think "fmap f m = (m >>= f >>> return)" also needs to obey the functor laws. I can quickly show that "fmap id = id" follows from the monad laws, but I don't know whether "fmap (p . q) = (fmap p) . (fmap q)" does.
      - dllthomas 12y ago
        Ah, it does seem to follow: M1: return a >>= f = f a M2: m >>= return = m M3: (m >>= f) >>= g = m >>= (\ x -> f x >>= g) (fmap f . fmap g) m = (fmap f . fmap g) m by defn of (.) = fmap f (fmap g m) by defn of fmap = fmap f (m >>= return . g) by defn of fmap = (m >>= return . g) >>= return . f by M3 = m >>= (\ x -> (return . g) x >>= return . f) by defn of (.) = m >>= (\ x -> return (g x) >>= return . f) by M1 = m >>= (\ x -> (return . f) (g x)) by defn of (.) = m >>= (\ x -> return (f (g x))) by defn of (.) = m >>= (\ x -> (return . (f . g)) x) eta reduction = m >>= return . (f . g) by defn of fmap = fmap (f . g) m (fmap f . fmap g) m = fmap (f . g) m
dllthomas 12y ago
'there’s no such thing as the “IO monad” or the “List monad”' I don't think I agree (depending on just what is meant by "such thing as")... I would say there is such thing as "the IO monad" in the same sense as there is such thing as "the rational field" or "the Z/5 group". It's a particular example of a more general algebraic structure, and you'd use the phrase when you're talking particularly about the structure as it occurs in that instance.
AnimalMuppet 12y ago
Monads, applicatives, functors, and monoids are different algebras. OK. That's really helpful, actually. (At least, I suspect it's going to be really helpful after I've thought about it for a few days.) But monads are the way to do sequencing? Only if you insist on putting yourself in a functional straight-jacket that's so tight that you cannot escape. Then, yes, you do sequencing via monads because you don't have any other way to do it. But if you're a pragmatist rather than an ideologue, it seems more reasonable to just do sequence by doing things in sequence, rather than forcing yourself to do unnatural contortions.
- dllthomas 12y ago
  "Monads, applicatives, functors, and monoids are different algebras. OK. That's really helpful, actually. (At least, I suspect it's going to be really helpful after I've thought about it for a few days.)" I think it's not quite accurate. They're all algebraic structures, but an "algebra" is a more specific thing and I don't think they are algebras specifically (except maybe monoid?). http://en.wikipedia.org/wiki/Algebraic_structure http://en.wikipedia.org/wiki/Algebraic_structure http://en.wikipedia.org/wiki/Algebra_%28ring_theory%29 http://en.wikipedia.org/wiki/Algebra_%28ring_theory%29 "But monads are the way to do sequencing? Only if you insist on putting yourself in a functional straight-jacket that's so tight that you cannot escape." "Chaining actions with bind is the only way to combine actions" in Haskell is more strongly motivated by keeping things sane in the face of non-strict semantics than by a "functional straight-jacket". In fact, it wasn't the way Haskell initially did IO. "Then, yes, you do sequencing via monads because you don't have any other way to do it. But if you're a pragmatist rather than an ideologue, it seems more reasonable to just do sequence by doing things in sequence, rather than forcing yourself to do unnatural contortions." "You have to do things my way, or you're not pragmatic!" seems to be your dogma. Reifying actions in a way that lets you talk about them in the same way you talk about the rest of your data is sometimes a very useful thing.
  - AnimalMuppet 12y ago
    > "Chaining actions with bind is the only way to combine actions" in Haskell is more strongly motivated by keeping things sane in the face of non-strict semantics than by a "functional straight-jacket". OK, if you have non-strict semantics (by which I presume you mean non-sequential), then you need some way to make things sequential when they have to be, and you have no ordinary (non-jumping-through-hoops) way to make them so. > "You have to do things my way, or you're not pragmatic!" seems to be your dogma. Shoe's on the other foot. Haskell's the one that insists that I have to do it Haskell's way. I complain, and you accuse me of being dogmatic. Doesn't work that way. But I suppose you'd say that I have the choice to not use Haskell, so stop complaining. And in fact, I take that choice, precisely because I consider the language's dogmatism to be less pragmatic (and therefore useful) than a multi-paradigm approach.

94 points by abishekk92 12y ago

I've had an idea for a monad tutorial that I think might be quite instructive, but haven't had the motivation yet to write. In essence, the idea is that you are led through the process of implementing: early exit, nondeterminism, threaded state and coroutines using call/cc in scheme. Then monads are introduced as a way of typing those patterns.

thirsteh 12y ago
I'm 99% sure this is the way to do it. You can't explain any field of math, much less category theory, without doing exercises.
peteretep 12y ago
Have you seen "You Could Have Invented Monads"?
- agumonkey 12y ago
  I understand concepts better when taken outside their ''''natural'''' environment (namely strongly paramectrically typed [lazy] languages). I often link these two : http://stackoverflow.com/questions/11871065/monads-in-javascript http://stackoverflow.com/questions/11871065/monads-in-javasc... http://dorophone.blogspot.fr/2011/04/deep-emacs-part-1.html http://dorophone.blogspot.fr/2011/04/deep-emacs-part-1.html
mdcox 12y ago
It seems like those with functional programming experience either already understand monads or grasp it quickly. At the same time, those without it have an instinctual eye-glaze when shown Haskell, or a lisp. Would it be better to use Python or Javascript which more people understand but still has that functional flair? Just an idea. Either way I look forward to reading it!
- karavelov 12y ago
  Dynamically typed languages are not the best choice when you try to explain algebras that work on the type level I guess.
- chriswarbo 12y ago
  > It seems like those with functional programming experience either already understand monads or grasp it quickly. That's probably survivor-bias (amongst Haskellers, at least); ie. those who haven't grasped it yet probably won't class themselves as Haskellers. > Would it be better to use Python or Javascript which more people understand but still has that functional flair? The problem with using such languages is that they're always dealing with concrete values; in particular they have no concept of interfaces (like Java) or typeclasses (like Haskell). It's certainly possible to use monads in such languages, but it's often hard to justify their use, since there are always less-complex ways to implement particular examples, and without interfaces it's hard to relate the examples together. For example, here are a bunch of monad implementations ("return" and "bind", AKA ">>=") in Javascript, but it's not at all obvious why they are related to each other: function state_return(val) { return [null, val]; } function state_bind(x, f) { return f(x[0], x[1]); } function maybe_return(val) { return [val]; } function maybe_bind(x, f) { return (x.length > 0)? f(x[0]) : []; } function list_return(val) { return [val]; } function list_bind(x, f) { return [].concat.apply([], x.map(f)); } function read_return(val) { return function(x) { return val; }; } function read_bind(x, f) { return function(arg) { f(x(arg))(arg); }; } The problem is that in Javascript, the implementation details are there for all to see. I might want to give you a string which depends on some integer state, but you can always see that it's actually implemented as an array containing an int and a string. You're also free to mess up that array by adding or removing elements from it, which are perfectly valid array operations, but which makes no sense for "stateful values". Interfaces like monads are useful when we're not free to mess around with the implementation; when we must perform all actions through a limited API. When we're dealing with such concerns every day ("I'd like to allow X, but don't want anyone to abuse it and end up with Y") then monads (and functors and applicatives, which they're based on) are really useful as standard APIs for allowing arbitrary operations to be performed, under the control of the API. The only example above that even comes close to this idea is the "reader" monad, implemented with `read_return` and `read_bind`. This is because values in the reader monad lets us manipulate the return values of functions, and even in dynamic languages a first-class function is pretty much a black box, so there's little we can do to mess it up.
klibertp 12y ago
I think most monad tutorials would be quite ok if they didn't use words like "monad", "bind", "return" and so on. It's just stupid to insist on using names which mean nothing or when they mean something (return) it's actually opposite of what they're supposed to do. And no, there are no upsides to this: you math-inclined people may think so because you were trained to think that way, but it's simply not true. I suspected this for a long time, but recently I saw a talk from Gilad Bracha - http://www.infoq.com/presentations/functional-pros-cons http://www.infoq.com/presentations/functional-pros-cons - which convinced me that I was right. Scroll to ~22 minutes into the talk for relevant section. Ok, I finally said it. I feel better now, thanks ;)
- deleted 12y ago
  [deleted]
- abathologist 12y ago
  I find that talk really painful. I do not recommend it. It is mean spirited, full of misleading characterizations, and - I think - it misses the core point of functional programming. Gary Verhaegen's comment "this was a waste of time" addresses the many problems effectively. Brian Craft's "ugh" addresses others. Either of those comments are more worthwhile than the video itself.
  - klibertp 12y ago
    > I find that talk really painful. I suspect it may be painful in some cases, it's somewhat like a clash of different cultures. The guy is firmly rooted in Smalltalk and Lisp schools of thinking and everything he says is rather obvious for those who share the same background. On the other hand it may be obviously false for people following ML tradition and even more so for recent converts. Watching this talk calmed me down. It turns out that I'm not an idiot, that I know how to do FP (because I quite like it!) and that there's no need to change my ways just because some vocal minority proclaims me a heretic for preferring meaningful names or no-nonsense IO handling. On the whole I think it was an hour well-spent. YMMV ofc.
    - 12y ago
tel 12y ago
Almost everyone who "know monads well" agrees with you. Studying monads is silly. It's a pattern you'll eventually recognize and just so happens to have a syntactic trick. Study particular instances.
inglesp 12y ago
Sounds not-so-dissimilar to Tom Stuart's "Refactoring Ruby with Monads" (https://speakerdeck.com/tomstuart/refactoring-ruby-with-monads https://speakerdeck.com/tomstuart/refactoring-ruby-with-mona...) which is excellent.
antoaravinth 12y ago
What about monads in terms of JS over here: https://blog.jcoglan.com/2011/03/05/translation-from-haskell-to-javascript-of-selected-portions-of-the-best-introduction-to-monads-ive-ever-read/ https://blog.jcoglan.com/2011/03/05/translation-from-haskell...

kinofcain 12y ago

Further evidence for my hypothesis that everyone who has ever understood monads has gone on to write a blog post trying to explain them.

bad_user 12y ago
This is because monads are quite simple and effective abstractions, yet they've proven hard to explain effectively, because contrary to other well known abstractions (let's take as an example the Iterator), monads are more abstract and have been used to describe things that don't bear a resemblance to each other in the minds of beginners. Lets take the Iterator - which is simple to explain (an API that allows you to iterate over a collection of items only once, a collection of items which may be infinite), but that has on the other hand strong limitations in what you can implement under it (e.g. the API calls are synchronous and you can only get the items one by one, sequentially). An Iterator can be a Monad if you provide a flatMap / bind implementation with the right behavior and lo and behold, this operation doesn't care about how the items are produced (synchronously or asynchronously or in what order). In OOP terms, you could have Iterator be a subtype of Monad, with the Monad being the more generic interface. So it's hard to explain because it is very generic, can be applied to many things and everybody has an aha! moment once they spot the resemblance in the various monad implementations, hence the urge to write a blog post.
chocolateboy 12y ago
... and failed: > Once you understand what monads are, and why they exist, you lose the ability to explain them to anybody. -- Douglas Crockford [1] [1] http://www.youtube.com/watch?v=dkZFtimgAcM http://www.youtube.com/watch?v=dkZFtimgAcM
- marcosdumay 12y ago
  How can one lose it? Before understanding it, one also has no ability to explain.

antoaravinth 12y ago

Im not getting the idea of monads here. From my understanding monads does series of transformation( composition, unit , lift ) of a function to do its task. So does monad is similar to Adapter pattern in java? which does make two classes work even though they aren't meant to work. Because it does transform the class/ interface to work with other class, right? Am I missing anything here?

efnx 12y ago
I like to think of a Monad in terms of the Monad laws, it makes it much less abstract. https://www.haskell.org/haskellwiki/Monad_laws https://www.haskell.org/haskellwiki/Monad_laws Different monads can have drastically different implementations but they should all obey those laws.
- AnimalMuppet 12y ago
  And anything that obeys those laws is a monad (if I understand correctly). [Edit: And if the implementing pieces are named correctly.]
  - dllthomas 12y ago
    I think "fmap f m = (m >>= f >>> return)" also needs to obey the functor laws. I can quickly show that "fmap id = id" follows from the monad laws, but I don't know whether "fmap (p . q) = (fmap p) . (fmap q)" does.
    - dllthomas 12y ago
      Ah, it does seem to follow: M1: return a >>= f = f a M2: m >>= return = m M3: (m >>= f) >>= g = m >>= (\ x -> f x >>= g) (fmap f . fmap g) m = (fmap f . fmap g) m by defn of (.) = fmap f (fmap g m) by defn of fmap = fmap f (m >>= return . g) by defn of fmap = (m >>= return . g) >>= return . f by M3 = m >>= (\ x -> (return . g) x >>= return . f) by defn of (.) = m >>= (\ x -> return (g x) >>= return . f) by M1 = m >>= (\ x -> (return . f) (g x)) by defn of (.) = m >>= (\ x -> return (f (g x))) by defn of (.) = m >>= (\ x -> (return . (f . g)) x) eta reduction = m >>= return . (f . g) by defn of fmap = fmap (f . g) m (fmap f . fmap g) m = fmap (f . g) m

dllthomas 12y ago

'there’s no such thing as the “IO monad” or the “List monad”' I don't think I agree (depending on just what is meant by "such thing as")... I would say there is such thing as "the IO monad" in the same sense as there is such thing as "the rational field" or "the Z/5 group". It's a particular example of a more general algebraic structure, and you'd use the phrase when you're talking particularly about the structure as it occurs in that instance.

AnimalMuppet 12y ago

Monads, applicatives, functors, and monoids are different algebras. OK. That's really helpful, actually. (At least, I suspect it's going to be really helpful after I've thought about it for a few days.) But monads are the way to do sequencing? Only if you insist on putting yourself in a functional straight-jacket that's so tight that you cannot escape. Then, yes, you do sequencing via monads because you don't have any other way to do it. But if you're a pragmatist rather than an ideologue, it seems more reasonable to just do sequence by doing things in sequence, rather than forcing yourself to do unnatural contortions.

dllthomas 12y ago
"Monads, applicatives, functors, and monoids are different algebras. OK. That's really helpful, actually. (At least, I suspect it's going to be really helpful after I've thought about it for a few days.)" I think it's not quite accurate. They're all algebraic structures, but an "algebra" is a more specific thing and I don't think they are algebras specifically (except maybe monoid?). http://en.wikipedia.org/wiki/Algebraic_structure http://en.wikipedia.org/wiki/Algebraic_structure http://en.wikipedia.org/wiki/Algebra_%28ring_theory%29 http://en.wikipedia.org/wiki/Algebra_%28ring_theory%29 "But monads are the way to do sequencing? Only if you insist on putting yourself in a functional straight-jacket that's so tight that you cannot escape." "Chaining actions with bind is the only way to combine actions" in Haskell is more strongly motivated by keeping things sane in the face of non-strict semantics than by a "functional straight-jacket". In fact, it wasn't the way Haskell initially did IO. "Then, yes, you do sequencing via monads because you don't have any other way to do it. But if you're a pragmatist rather than an ideologue, it seems more reasonable to just do sequence by doing things in sequence, rather than forcing yourself to do unnatural contortions." "You have to do things my way, or you're not pragmatic!" seems to be your dogma. Reifying actions in a way that lets you talk about them in the same way you talk about the rest of your data is sometimes a very useful thing.
- AnimalMuppet 12y ago
  > "Chaining actions with bind is the only way to combine actions" in Haskell is more strongly motivated by keeping things sane in the face of non-strict semantics than by a "functional straight-jacket". OK, if you have non-strict semantics (by which I presume you mean non-sequential), then you need some way to make things sequential when they have to be, and you have no ordinary (non-jumping-through-hoops) way to make them so. > "You have to do things my way, or you're not pragmatic!" seems to be your dogma. Shoe's on the other foot. Haskell's the one that insists that I have to do it Haskell's way. I complain, and you accuse me of being dogmatic. Doesn't work that way. But I suppose you'd say that I have the choice to not use Haskell, so stop complaining. And in fact, I take that choice, precisely because I consider the language's dogmatism to be less pragmatic (and therefore useful) than a multi-paradigm approach.