6 ms·

A monad is any data structure which implements bind. Bind is a higher-order function with two parameters - one is the data structure to be transformed, the othe

A monad is any data structure which implements bind. Bind is a higher-order function with two parameters - one is the data structure to be transformed, the other is a function which maps over elements in the data structure. However, unlike a normal map, each result of "bind" sits in its own version of the original data structure, which then have to be combined back into a single data structure. The way in which the data structures are combined is what makes each monad different. For example, List is a monad. Suppose we had a List of Ints, such as [5,3,4]. If we were to run bind over this list, we would need a function that takes an Int and returns a List of something. We could use "show", the function which converts Ints to Strings (a String is technically a List of Char. Since this is a List, we're good). If we call bind using [5,3,4] and show, we get ["5","3","4"] which are then combined to "534". We can check with the interpreter (>>= is bind): Prelude> [5,3,4] >>= show "534"

jnordwick 10y ago
> each result of "bind" sits in its own version of the original data structure, which then have to be combined back into a single data structure That doesn't make sense to me. Let's say I have the list [5,3,4], to me that means each application returns a three element list [f(5),x,x], [x,f(3),x], and [x,x,f(4)] then the bind function takes these lists and turns them into [f(5),f(3),f(4)]. What makes this function a monad?
- scottmsul 10y ago
  It makes a List of Lists, then combines those into a List. [5,3,4] becomes [f(5), f(3), f(4)], but f(x) must return a List. Those inner Lists are then concatenated. When I say "original data structure", I mean the type of data structure is the same (in this case, List).
  - jnordwick 10y ago
    What is the data structures don't support a join operation, like a tree?
    - scottmsul 10y ago
      We would need a way to transform a Tree of Trees into a single Tree. The inner Trees would be at leaf nodes of the outer Tree, so they could be attached in place. Although I recall monads need to satisfy certain laws, and I don't recall if Trees satisfy them or not. Just because something is a data structure does not necessarily imply it is a monad.
      - dllthomas 10y ago
        A rose tree is a monad.
- gizmo686 10y ago
  In this case "data structure" refers to List, not a specific size or type of list. For example, suppose you have a list of ints, and want to bind a function, show. We have types: [5,3,4] :: List Int show :: Int -> List Char That is to say, [5,3,4] is a list of ints, and show is a function that takes an int and returns a list of characters. In this case, we would have [5,3,4] >>= show f(5) ++ f(3) ++ f(4) ['5'] ++ ['3'] ++ ['4'] ['5','3','4'] where "++" is list concatenation. The idea here is that when we apply show, we get back 3 different Lists, and want to combine them into a single list.
  - deleted 10y ago
    [deleted]
  - jnordwick 10y ago
    So bind is flat map in other languages? If join is a function that take a list and appends its elements together join ( [[1], [2], [3]] ) -> [1,2,3] then bind is join(map(f, x))? bind just seems like a terrible name. For some reason Haskell users try to make things sounds as academic as possible.
    - gizmo686 10y ago
      >For some reason Haskell users try to make things sounds as academic as possible. Probably because Haskell ended up being the language for academics. If you want to do programming language research in an ML-type language use Haskell. If you want to make a product, use OCaml. Not entirely true, but pretty close. >So bind is flat map in other languages. In the case of a List, yes, but there are other datastructures that implement Monad. This type of thing happens a fair amount in Haskell. It is not that uncommon to see code like: instance Monad List where (>>=) = flatMap That is to say, the implementation of the interface is just another function that has a more domain specific name. There are other monads with a bind that cannot be understood as flatMap. For example, the Maybe datatype is Haskell's version of Optional. For example, if a variable is of type `Maybe t`, it either contains a single value of type t, or no value. It is common to use Maybe without using it as a monad. However, Maybe does implement the Monad interface. In this case, bind is defined as follows: x.bind(f) = if (x.hasValue()) then { return Just(f(x.value)) } else { return Nothing() } where Just and Nothing are two constructors of Maybe. If we view 'no value' as analogous to null, then this bind function is null propogation.
- Tarean 10y ago
  I think an easier to understand definition uses fmap and join. Example: f x = [x, x*2] f =<< [5, 3, 4] join (fmap f [5, 3, 4]) join ([[5, 10], [3, 6], [4, 8]]) [5, 10, 3, 6, 4, 8] So the pattern is fmap a function `a -> f b`; this leaves us with `f (f b)` so we flatten. You might notice that we could bind as often as we want since we always get a list of integers!
  - StavrosK 10y ago
    I think if you already know fmap, join and Haskell syntax, you also already know monads, so I'm not sure whom this is easier for :P
alok-g 10y ago
I haven't read/understood your full comment as yet. I've gotten stuck on the first sentence itself: "A monad refers to a class of data structures which implement bind": Perhaps you mean that a data structure like a list which implements bind is a monad. Based on what I am reading in your overall comment, a monad is not a class of data structures which implement bind. I italicized keywords which I found problematic in your first statement, noting that you used refers to, and not is. (It is likely that I am confused, but have been missing a clear definition of a monad like "a monad is ...". If the definition involves more terms needing definitions, a topological sort would help. :-)
- scottmsul 10y ago
  Thanks, I changed the first sentence, hopefully it's less confusing.
- mrkgnao 10y ago
  Well, a monad is parameterized over a type (so Maybe is the monad, not Maybe a -- or State s, Writer w, and so on), so GP could be said to have a point: Monad (with a capital m) is the (type)class of datatypes which do all those things. But, honestly (my silly rules-lawyering aside), a monad "is" an endofunctor and two particular nice natural transformations that satisfy some coherence conditions. This is at the other extreme of the pedagogical utility/clarity scale, since it is the final (if opaque) answer to any definitional ambiguity. Functors and applicative functors precede monads in (pretentious cough) modern Haskell pedagogy, as championed by the (thankfully non-pretentious) Learn You A Haskell, as well as the Haskell Wikibook. Reading the relevant chapters is a good start. :) http://learnyouahaskell.com/ http://learnyouahaskell.com/ https://en.wikibooks.org/wiki/Haskell https://en.wikibooks.org/wiki/Haskell
xelxebar 10y ago
Well, you really do need the full Kleisli triple and commutation laws, otherwise bind becomes just a functor.
- scottmsul 10y ago
  That's not exactly true, since bind and fmap have different types. fmap :: (Functor f) => f a -> (a -> b) -> f b bind :: (Monad m) => m a -> (a -> m b) -> m b Functors simply map elements one-to-one, while monads map elements to new data structures, which have to be combined back to a single data structure. However, it's good you mention the laws - it's certainly possible to define bind with the correct type but incorrect behavior. An example would be defining the List bind in a way that doesn't concatenate the elements in order. The following is a really good reference for understanding not just the difference between functors, applicatives, and monads, but also why each is more powerful than the one before it. https://en.wikibooks.org/wiki/Haskell/Applicative_functors#A_sliding_scale_of_power https://en.wikibooks.org/wiki/Haskell/Applicative_functors#A...
jodooshi 10y ago
> monads aren’t actually all that complicated. In fact, most of the experienced functional programmers I’ve met consider them downright simple. It’s just that newcomers often have a really hard time trying to figure out what exactly monads even are... A lot of intermediate-to-advanced functional programmers have taken it upon themselves to write monad tutorials... But for the most part, these tutorials never seem to work. Why is that? Locked doors, headaches, and intellectual need: https://mkremins.github.io/blog/doors-headaches-intellectual-need/ https://mkremins.github.io/blog/doors-headaches-intellectual... :-)
- kaoD 10y ago
  The article is spot on. The problem with monads is not the what, is the why. Tutorials often explain the what, which is easy to understand (except where people get creative with similes... "monads are like tuna sausages, but you can build castles with them"). Not having used them, I'm still puzzled at _why_ I would need monads at all. At this point, tutorials use examples like "like flatMap and Maybe in other languages!" which is even more confusing. Why do I need a monad then, if there are similar constructs in other languages that don't need the understanding of monad? Why the complexity? What do I get from monads?
  - dack 10y ago
    It lets you model sequential operation and side effects in a pure functional language. You can usually write your code "manually" without monads, and see what it's like. For example, the State monad is basically a function that takes in a value and some state, and returns a new value and a new state. That's a pure function, but composing/chaining them together is pretty messy. If you do that manually once, you'll then get some intuition why the State monad is useful. Then you can expand to other types of monads and eventually have an intuition for their general value.
  - taesis 10y ago
    Edit: You don't really need monads any more than you need classes, interfaces, functions, procedures (just use goto!), etc. they just help bring a bunch of seemingly disparate functionality together into one standard (which is helpful in, e.g. Scala or Haskell where there's some syntactic sugar for dealing with monads). People complained for the longest time (amongst many, many other things) that Javascript lacked classes, even though you could totally hack it together with `new`, functions and prototypes. Similarly, FP people complain that everything else lacks monad support, even though they can hack it together with largely language independent features (typically without compile-time checking). I don't have an intuitive grasp of the formal definition of monads, but some examples of things that I _think_ are monads (in Java ... sorry :/ it's all I work with these days): * jOOQ [1]: you use it to build up a sequence of SQL statements with a pleasant chaining API, then execute the whole shebang * Promise/future chaining: you build up a sequence of promises that should apply in-order, then defer their execution until later (unless you use a language that performs a transformation at compile time which effectively does this for you). * Streams/optional mapping: you build up a sequence of functions that should apply in-order to every element in a potentially empty sequence (optional: a sequence of 0 or 1). * The builder pattern: you build up a sequence of property values, then (potentially) construct the entire object. [1]: https://www.jooq.org/ https://www.jooq.org/
norswap 10y ago
A monad is a "value" of a type X that depends on a type T: X[T]. It must have a "way" to take a function T -> X[T] and apply it to itself so as to get another X[T]. Usually that "way" is a function called "bind" with signature: (X[T], (T -> X[T]) -> X[T] And that's really all there is to it. Monads are fundamental only in the sense that there happens to be a lot of things for which these structures are useful (lists, optionals, effect wrappers, ...).

jnordwick 10y ago

> each result of "bind" sits in its own version of the original data structure, which then have to be combined back into a single data structure That doesn't make sense to me. Let's say I have the list [5,3,4], to me that means each application returns a three element list [f(5),x,x], [x,f(3),x], and [x,x,f(4)] then the bind function takes these lists and turns them into [f(5),f(3),f(4)]. What makes this function a monad?

scottmsul 10y ago
It makes a List of Lists, then combines those into a List. [5,3,4] becomes [f(5), f(3), f(4)], but f(x) must return a List. Those inner Lists are then concatenated. When I say "original data structure", I mean the type of data structure is the same (in this case, List).
- jnordwick 10y ago
  What is the data structures don't support a join operation, like a tree?
  - scottmsul 10y ago
    We would need a way to transform a Tree of Trees into a single Tree. The inner Trees would be at leaf nodes of the outer Tree, so they could be attached in place. Although I recall monads need to satisfy certain laws, and I don't recall if Trees satisfy them or not. Just because something is a data structure does not necessarily imply it is a monad.
    - dllthomas 10y ago
      A rose tree is a monad.
gizmo686 10y ago
In this case "data structure" refers to List, not a specific size or type of list. For example, suppose you have a list of ints, and want to bind a function, show. We have types: [5,3,4] :: List Int show :: Int -> List Char That is to say, [5,3,4] is a list of ints, and show is a function that takes an int and returns a list of characters. In this case, we would have [5,3,4] >>= show f(5) ++ f(3) ++ f(4) ['5'] ++ ['3'] ++ ['4'] ['5','3','4'] where "++" is list concatenation. The idea here is that when we apply show, we get back 3 different Lists, and want to combine them into a single list.
- deleted 10y ago
  [deleted]
- jnordwick 10y ago
  So bind is flat map in other languages? If join is a function that take a list and appends its elements together join ( [[1], [2], [3]] ) -> [1,2,3] then bind is join(map(f, x))? bind just seems like a terrible name. For some reason Haskell users try to make things sounds as academic as possible.
  - gizmo686 10y ago
    >For some reason Haskell users try to make things sounds as academic as possible. Probably because Haskell ended up being the language for academics. If you want to do programming language research in an ML-type language use Haskell. If you want to make a product, use OCaml. Not entirely true, but pretty close. >So bind is flat map in other languages. In the case of a List, yes, but there are other datastructures that implement Monad. This type of thing happens a fair amount in Haskell. It is not that uncommon to see code like: instance Monad List where (>>=) = flatMap That is to say, the implementation of the interface is just another function that has a more domain specific name. There are other monads with a bind that cannot be understood as flatMap. For example, the Maybe datatype is Haskell's version of Optional. For example, if a variable is of type `Maybe t`, it either contains a single value of type t, or no value. It is common to use Maybe without using it as a monad. However, Maybe does implement the Monad interface. In this case, bind is defined as follows: x.bind(f) = if (x.hasValue()) then { return Just(f(x.value)) } else { return Nothing() } where Just and Nothing are two constructors of Maybe. If we view 'no value' as analogous to null, then this bind function is null propogation.
Tarean 10y ago
I think an easier to understand definition uses fmap and join. Example: f x = [x, x*2] f =<< [5, 3, 4] join (fmap f [5, 3, 4]) join ([[5, 10], [3, 6], [4, 8]]) [5, 10, 3, 6, 4, 8] So the pattern is fmap a function `a -> f b`; this leaves us with `f (f b)` so we flatten. You might notice that we could bind as often as we want since we always get a list of integers!
- StavrosK 10y ago
  I think if you already know fmap, join and Haskell syntax, you also already know monads, so I'm not sure whom this is easier for :P

alok-g 10y ago

I haven't read/understood your full comment as yet. I've gotten stuck on the first sentence itself: "A monad refers to a class of data structures which implement bind": Perhaps you mean that a data structure like a list which implements bind is a monad. Based on what I am reading in your overall comment, a monad is not a class of data structures which implement bind. I italicized keywords which I found problematic in your first statement, noting that you used refers to, and not is. (It is likely that I am confused, but have been missing a clear definition of a monad like "a monad is ...". If the definition involves more terms needing definitions, a topological sort would help. :-)

scottmsul 10y ago
Thanks, I changed the first sentence, hopefully it's less confusing.
mrkgnao 10y ago
Well, a monad is parameterized over a type (so Maybe is the monad, not Maybe a -- or State s, Writer w, and so on), so GP could be said to have a point: Monad (with a capital m) is the (type)class of datatypes which do all those things. But, honestly (my silly rules-lawyering aside), a monad "is" an endofunctor and two particular nice natural transformations that satisfy some coherence conditions. This is at the other extreme of the pedagogical utility/clarity scale, since it is the final (if opaque) answer to any definitional ambiguity. Functors and applicative functors precede monads in (pretentious cough) modern Haskell pedagogy, as championed by the (thankfully non-pretentious) Learn You A Haskell, as well as the Haskell Wikibook. Reading the relevant chapters is a good start. :) http://learnyouahaskell.com/ http://learnyouahaskell.com/ https://en.wikibooks.org/wiki/Haskell https://en.wikibooks.org/wiki/Haskell

xelxebar 10y ago

Well, you really do need the full Kleisli triple and commutation laws, otherwise bind becomes just a functor.

scottmsul 10y ago
That's not exactly true, since bind and fmap have different types. fmap :: (Functor f) => f a -> (a -> b) -> f b bind :: (Monad m) => m a -> (a -> m b) -> m b Functors simply map elements one-to-one, while monads map elements to new data structures, which have to be combined back to a single data structure. However, it's good you mention the laws - it's certainly possible to define bind with the correct type but incorrect behavior. An example would be defining the List bind in a way that doesn't concatenate the elements in order. The following is a really good reference for understanding not just the difference between functors, applicatives, and monads, but also why each is more powerful than the one before it. https://en.wikibooks.org/wiki/Haskell/Applicative_functors#A_sliding_scale_of_power https://en.wikibooks.org/wiki/Haskell/Applicative_functors#A...

jodooshi 10y ago

> monads aren’t actually all that complicated. In fact, most of the experienced functional programmers I’ve met consider them downright simple. It’s just that newcomers often have a really hard time trying to figure out what exactly monads even are... A lot of intermediate-to-advanced functional programmers have taken it upon themselves to write monad tutorials... But for the most part, these tutorials never seem to work. Why is that? Locked doors, headaches, and intellectual need: https://mkremins.github.io/blog/doors-headaches-intellectual-need/ https://mkremins.github.io/blog/doors-headaches-intellectual... :-)

kaoD 10y ago
The article is spot on. The problem with monads is not the what, is the why. Tutorials often explain the what, which is easy to understand (except where people get creative with similes... "monads are like tuna sausages, but you can build castles with them"). Not having used them, I'm still puzzled at _why_ I would need monads at all. At this point, tutorials use examples like "like flatMap and Maybe in other languages!" which is even more confusing. Why do I need a monad then, if there are similar constructs in other languages that don't need the understanding of monad? Why the complexity? What do I get from monads?
- dack 10y ago
  It lets you model sequential operation and side effects in a pure functional language. You can usually write your code "manually" without monads, and see what it's like. For example, the State monad is basically a function that takes in a value and some state, and returns a new value and a new state. That's a pure function, but composing/chaining them together is pretty messy. If you do that manually once, you'll then get some intuition why the State monad is useful. Then you can expand to other types of monads and eventually have an intuition for their general value.
- taesis 10y ago
  Edit: You don't really need monads any more than you need classes, interfaces, functions, procedures (just use goto!), etc. they just help bring a bunch of seemingly disparate functionality together into one standard (which is helpful in, e.g. Scala or Haskell where there's some syntactic sugar for dealing with monads). People complained for the longest time (amongst many, many other things) that Javascript lacked classes, even though you could totally hack it together with `new`, functions and prototypes. Similarly, FP people complain that everything else lacks monad support, even though they can hack it together with largely language independent features (typically without compile-time checking). I don't have an intuitive grasp of the formal definition of monads, but some examples of things that I _think_ are monads (in Java ... sorry :/ it's all I work with these days): * jOOQ [1]: you use it to build up a sequence of SQL statements with a pleasant chaining API, then execute the whole shebang * Promise/future chaining: you build up a sequence of promises that should apply in-order, then defer their execution until later (unless you use a language that performs a transformation at compile time which effectively does this for you). * Streams/optional mapping: you build up a sequence of functions that should apply in-order to every element in a potentially empty sequence (optional: a sequence of 0 or 1). * The builder pattern: you build up a sequence of property values, then (potentially) construct the entire object. [1]: https://www.jooq.org/ https://www.jooq.org/

norswap 10y ago

A monad is a "value" of a type X that depends on a type T: X[T]. It must have a "way" to take a function T -> X[T] and apply it to itself so as to get another X[T]. Usually that "way" is a function called "bind" with signature: (X[T], (T -> X[T]) -> X[T] And that's really all there is to it. Monads are fundamental only in the sense that there happens to be a lot of things for which these structures are useful (lists, optionals, effect wrappers, ...).