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"
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...
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. :-)
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. :)
Why is that? Locked doors, headaches, and intellectual need: https://mkremins.github.io/blog/doors-headaches-intellectual... :-)
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?
Usually that "way" is a function called "bind" with signature:
(X[T], (T -> X[T]) -> X[T]
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, ...).
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?
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]
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
In this case, we would have
[5,3,4] >>= show
f(5) ++ f(3) ++ f(4)
['5'] ++ ['3'] ++ ['4']
['5','3','4']
[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).
Sometimes they even use Haskell as if you already know it to try to explain it.
I'm still looking for a basic article that describes monads well. My first few languages were all functional too, so that isn't the problem. I even still use APL derivatives.
Imagine two functions :
A -> k B B -> k C
Can you turn those into
A -> k C
Such that you can just think of it as functional composition? If you can, k is a monad.
The catch is, knowing what a Monad is is a bit like knowing what a saxophone is... the real problem is learning how to play it.
Just don't skip chapters and read from the beginning to the end.
I think half of people failing to understand monads are people failing to understand typeclasses or HKT while trying to learn about monads. Once you get those, all you need is the Monad typeclass definition and a huge pile of motivating examples.
Yes they are as simple as people claim they are, and if you've done any functional programming you may already know them.
1. Imagine a datastructure and a value. In this case we'll use "List" as the datastructure, and "Int" as the value. So [3,4,5]. It's type is List<Int>.
2. Next we'll take "f" as a function that converts a single value to a list of values (ie a datastructure of our values). In this case the function takes a value and outputs a list of 3 copies of the value.
ex. f(8) = [8,8,8] The type of f is: Int -> List<Int> // Takes in an int, and returns a list of ints.
Also imagine a function "g" that does the same thing but makes 5 copies of the data. ex. g(7) = [7,7,7,7,7]
It has the same type as f: Int -> List<Int>
3. How we apply the function to the data: Frequently when we have lists and functions over their values we will call map over them. _.map(f, [3,4,5]) = [[3,3,3],[4,4,4],[5,5,5]]
Notice that we don't get out a list of ints (type: List<Int>), instead we have a list of lists of Ints (type: List<List<Int>>).
We also often like to create/compose chains of these functions to create a pipeline to transform the data. So normally we would want to do something like: r1 = _.map(f, [3,4,5]) r2 = _.map(g, r1)
But we can't. r1 is of the wrong type to pass into the second map. r1 is a List<List<Int>>, but the g is expecting a List<Int>. So how do we fix this.
How do we turn [[3,3,3],[4,4,4],[5,5,5]] into a flattened list of ints? We append them.:
[3,3,3] ++ [4,4,4] ++ [5,5,5] // where ++ is list append in this language
the end result is [3,3,3,4,4,4,5,5,5]. Which is perfect. This is now something that we can pass into the _.map(g, ...) above.
We first 'mapped' transforming List<Int> -> List<List<Int>>. Then we "flattened" so that List<List<Int>> became just List<Int>. This allowed us to run map with g next.
This combination is bind.
Now the absurd part. If you've used something like C#'s linq there is a function that does this. It's called "SelectMany()". SelectMany is bind. It converts each element in a list to a new list, then flattens and appends the nested lists into a single list.
Bind is nothing more than SelectMany().
The only notable piece is that bind is abstract. There are different incarnations of bind for each datastructure. SelectMany is the bind for Lists. There is a different implementation of bind for "Maybe" type. Or other datastructures.
And a Monad is nothing more than a datastructure that supports SelectMany/bind. List is the one that you use all the time. The selectMany concept generalized to any datastructure is the concept of bind + a Monad.
What you described is flatMap in Java, or join() in other languages. Somebody above went into the CPS transform of a program. I'm so lost at how simple this is versus how complex all the descriptions are.
I really like this one: http://adit.io/posts/2013-04-17-functors,_applicatives,_and_...
> Monads are not complicated. They are implemented as a typeclass with two methods, return and (>>=) (pronounced "bind"). In order to implement a Monad instance, these two functions must be defined in accordance with the arity described in the typeclass definition:
This is a great example of what I just said: it uses complex Haskell code and functions to describe a monad. If you already know what it assumes you know, you most likely already know what a monad is.
"A monad is composed of three functions and encodes control flow which allows pure functions to be strung together."
Gibberish compared to claim that monads just execute functions in a specified order. Aka an imperative function or procedure by one definition I've seen a lot. Of course, that monad definition might be wrong, too.
"A recursive function is a function that calls itself inside its own definition."
That's a recursive definition lol. Must have been a joke.
"A monad transformer allows you to stack more than one monad for use in a function."
We've had composition of procedures for a long time. Perhaps Haskell could've called it a MonadComposer?
"Lift is an operation on a functor that uses fmap to operate on the data contained in the functor."
fmap-apply() or something like that?
"Optics(lens and prisms) allow you to get and set data in a data type."
Getters and setters. My early OOP/C++ books are finally more intuitive than something.
"Map applies a function to every element of a list."
foreach(function(), list)
"A predicate is a function that returns true or false."
A boolean function.
"Filter applies a predicate to a list and returns only elements which return true."
Syntactic sugar for a foreach(function, list()) where the function on each member is an If (Conditional) is TRUE Then AddElementToNewListThatsReturned(). Yeah, even the description of imperative version is getting long. This might be a productivity boost.
"A morphism is a transformation from any object to any other object."
A cast from one object to another? Or one with an actual conversion function and/or check? The functional name seems more accurate, though.
"Algebraic data types are a method to describe the structure of types."
Ahh, they're just structs. Wait, what is a type exactly? And therefore what is an abstract... oh darn...
"Free monads allow the transformation of functors to monads."
A functor is an object that can be fmaped over. We covered map. Maybe the same. A monad is either an ordering of functions or something composed of three functions and encodes control flow composed of pure functions. Free monads are apparently an unknown thing that can transform objects that can be fmaped over into something composed of three functions with encoded control flow of composed, pure functions. I heard a lot of good Masters and Ph.D. proposals before this one. This is good, though. Especially quantifying the unknown aspects with a lot of NSF-funded R&D.
"A lambda is an unnamed function."
"Types are an inherent characteristic of every Haskell expression."
"Currying uses partial application to return a function until all arguments are filled."
"A category is a collection of objects, morphisms, and the configuration of the morphisms."
Ok, I just have fun with that one. Author did good on a lot of them. I'm just going to leave these here as quotes to add to Free Monads in... The Advanced Course: Haskell in Two or More Sentences. They provide anywhere from no information at all to the uninitiated to extra confusion inspiring taking or avoiding Haskell courses. :)
a -> Maybe b
let a = tryRead
if isNothing a
then Nothing
else
let b = tryParse (unwrap a)
if isNothing b...
tryRead >>= tryParse >>= tryProcess
There are a lot of other things that we could encode in a generic type tacked onto the return value and which we want to chain like this.
Futures in async io, passing around config/state instead of having global variables or the order in which ffi/io is run (the use case you have heard of most) would be a couple examples. You can even abuse bind to add things like implicit backtracking on failure!
So the really cool thing about monads is that you can add new behavior to functions without implementation details leaking during composition!
The cool thing about lenses is that they enable getters/setters for things like entries in a hashmap or all string fields in a struct at once.
The cool thing about lenses is that they enable getters/setters for things like entries in a hashmap or all string fields in a struct at once."
Good reply. Yeah, I definitely see these as beneficial.
Maybe that's a shame. Take fmap, functor-map, for example. It's just map if you apply it to a List. But it's more general. You can apply it to a Tree or a List of Lists or any other Functor. They could have called Functor a Bag or a Box or a Container or a Listable. They could have called it an Fmapable, since Fmapable is the class of things fmap works on. Might have missed an opportunity.
Or take the monadic bind operator >>=. Another language calls it and_then. I can see how that's more friendly.
Ouch! But seriously, this page is just a someone's jotted out notes. Haskell Programming from First Principles and What I Wish I Knew When Learning Haskell (http://dev.stephendiehl.com/hask/) are the actual pinnacle of Haskell explanations. They have plenty of great examples.
Come now, you're not allowed to complain both that the names are confusing, and also that more terminology should be used.
"It's a conditional like what you evaluate in an If-Then statement."
"Oh yeah, I see what you're saying."
>That's a recursive definition lol.
No it isn't? I'm not really sure why you think it is?
"a type of function's whose definition is it calls itself in its own definition."
Most people's problem is they don't understand the concept. Such a definition just confuses them more as they try to wrap their head around what they visualize a circular or looping logic. It's the kind of thing best to define with examples. Even those usually don't teach why people would go through the trouble. The Thinking in Scheme people went further to write a whole book to teach the subject.
You start with a bunch of things, and some way of combining them two at a time.
Rule 1 (Closure): The result of combining two things is always another one of the things.
Rule 2 (Associativity): When combining more than two things, which pairwise combination you do first doesn't matter.
Rule 3 (Identity element): There is a special thing called "zero" such that when you combine any thing with "zero" you get the original thing back.
With these rules in place, we can come back to the definition of a monoid. A "monoid" is just a system that obeys all three rules. Simple!
You start with a bunch of transformations that either turn a thing into a (different) *useful* thing or into a *dead end*.
Rule 1 (Left Identity): Applying a transformation to a useful thing is the same as simply transforming a plain thing.
Rule 2 (Right Identity): A transformation that merely makes a thing useful has no effect when applied. Useful things stay the same, dead ends stay dead.
Rule 3 (Associativity): You can merge any two transformations into one, which behaves the same as if you applied the first transformation to something and then applied the second transformation to the result.Consider a monad m and a function, a -> m b. Frequently you want to feed another monadic value, m a, into that function.
A monad gives you a function, >>=, that lets you take m a and feed it into a -> m b.
So any function that does IO, that looks like a -> IO b, you can take an IO a and plug it into a -> IO b. Any function that manipulates a state, you can take State a and plug it into a -> State b. This is the heart of a monad: gluing monadic functions together.
The meaning of >>= depends on the monad you're in. You also need return :: a -> m a, which can take a thing and put it in a monadic value.
There are monad laws also. A lot of times there's several ways to manipulate monads to do something, and the laws are needed to make sure they're all equivalent. For everyday monad use the laws aren't terribly important to remember, and GHC's linter will helpfully point out when you can use them.
That's my attempt at a short explanation. The "monad tutorial problem" has been weighing on my mind. The only way I ever understood monads was by reading and rereading the definition and examples. Tutorials never taught me anything.
a -> m b
>>=
What is the third function? Did I misunderstand you?
Also, monad and monoid are orthogonal ideas in Haskell. Monad doesn't follow from monoid.
Personally, I would just think of Monad as "thing with bind & return." Basically all of the magic of any Monad happens in its bind function. What makes Monad interesting (imo) is that for any type that can be a Monad there are typically only one or two possible implementations of bind that fulfill the Monad laws.
I guess my advice would be to put getting an intuition for Monad on hold. The reason being that most Monads behave very differently from each other (this is a testament to the power of the concept, that it can tie together so many seemingly unrelated ideas.) Just read a bunch of Monad implementations and verify that they fulfill the laws (make sure to also have the typeclass definition in the back of your head.)
To get you started, I recommend you wrap your head around the Maybe, Either e, State, Reader and Writer monads in that order. Unfortunately, you won't be able to look at Haskell source to read these Monads, as their implementations now all use Monad Transformers if I'm not mistaken. You should still be able to find straightforward implementations of these Monads floating around in internet tutorials.
Also, if you intend to have a serious go at Haskell, I recommend the NICTA course as a no-bullshit approach. (Warning: not for the faint of heart. Especially if you're going it alone.)
https://www.youtube.com/watch?v=WsA7GtUQeB8
There are already a good number of people trying to explain Monads in this thread, so I won't attempt it. But I'll say this (in the context of Haskell):
In Haskell, like how Monoid is a typeclass, Monad is just another typeclass. So me mentioning "typeclass" twice in a sentence suggests that you probably have to first understand typeclasses and data types.
Also, I wouldn't recommend tackling Monad right after grasping Monoid. I'd recommend you read about and understand Functor and Applicative functors first, and that will ease you into understanding Monads and actually why you would want to have them.
So, you may want to read these pages from Wikibooks in this order:
https://en.wikibooks.org/wiki/Haskell/Classes_and_types
https://en.wikibooks.org/wiki/Haskell/The_Functor_class
https://en.wikibooks.org/wiki/Haskell/Applicative_functors
https://en.wikibooks.org/wiki/Haskell/Applicative_prologue
The last link is the first section of a chapter on Monads; so use the links on the sidebar to read the subsequent sections of the chapter.
Typeclassopedia is another great resource for the typeclasses I mentioned: https://wiki.haskell.org/Typeclassopedia
That's in the same way that (as the article says) monads are things you can bind together (in Haskell, binding will tell how code flows, so monads in Haskell are things with a defined kind of code flow between them), and functors are things you can map over.
A list is all three.
You can put anything in the box. It's TARDIS-like.
`return` replaces the thing that was in the box.
`bind` replaces the box.
Most monads have a number of functions that can only be executed over boxes. This is because the boxes have special metadata (for example, someone has been scribbling state underneath the box). The 'get' function from the State monad just tells you to read the gibberish on the box instead of unpacking the box. The 'set' function scribbles more stuff on the bottom of the box.
Useful monads then provide a function to put things into the box, work with the box and then throw the box away (or inspect it by itself). These are the functions called 'runWhatever' for example 'runState', which lets you put an apple in the box, put a shipping label onto the box and then eventually separate the apple and the shipping label into each hand, throwing the box in the bin.
You can put anything in a box. Even more boxes. And when you're inside the box, you can't really tell how deep you are. If you're in the bottom box you can't actually see that you're in 20 layers of boxes, and this is why Monads are so powerful for creating libraries and frameworks.
You have a box (one monad). Inside the box is a jar (one monad) and inside the jar is an apple.
You want to write on the jar, so you give it to your friend but he's a moron and doesn't know how to open the box. The `lift` function opens the box, gives him the jar so he can write on it, then puts it back in the same box.
`lift` is for executing monad stuff within other monads when you have jars in boxes and need to juggle them around a little bit, but all your friends are idiots.
`liftM` is the same thing actually, but can be used on the apple in the jar since the apple isn't already a monad. If you need to swap the apple for another apple, but it's inside the jar inside the box, you need to use the composition of `lift` and `liftM` to first take the jar out the box, and then the apple out of the jar (but it'll pack them all up when you're done).
I would be curious to get your thoughts.
Also I didn't understand the word TARDIS-like.
My explanation of Monads approaches them from a practical angle rather than a theoretical angle. It won't help you make your own, but it will help you appreciate why people make them.
class Functor f where
fmap :: (a -> b) -> f a -> f b
That's the precise and short definition. It assumes the following knowledge:
0. How partial application works and the . works.
1. How Haskell's type-classes work (`Functor`).
2. How Haskell's methods work (`fmap`).
3. How Haskell's higher-kinded types work (the `f`).
So good luck explaining `fmap` in one sentence unless you already know Haskell and understand its type system to a confident degree, which depending on your background can take weeks to months.
Haskell's Monad also has >> and >>= both defined as part of the typeclass itself; instead of making >> a normal function. The typeclass does provide a default implementation of >> in terms of >>=.
But you are correct. In general all you need for a monad is bind and return.
http://hackage.haskell.org/package/base-4.9.1.0/docs/Prelude...
join :: m(m a) -> m a
For instance, purely by "following the types",
f :: a -> m b
fmap f :: m a -> m (m b)
join (fmap f) :: m a -> m b
(>>=) :: m a -> (a -> m b) -> m b
ma >>= f = join (fmap f ma)
(>>) :: m a -> m b -> m b
There are two forms of bind.
The >> function is used when the function does not need the value produced by the first monadic operator.
My advice is to ignore these things. Don't read a million monad tutorials. Just play around and code something, you don't have to understand the monad-definition before you can use the do-notation. Try to ignore them. After a while you get an intuition and then the definitions will make sense.
It uses Javascript to explain everything from scratch. Pure-functions, currying, composition, functors, monads, applicatives and so on.
Its free, so check it out. Reading it and understanding the concepts completely changed my whole coding style in the last couple of month. I hope functional javascript becomes more mainstream and we will soon call this stuff 'standard'. Its just too convenient to stack a Future on top of a Reader and get dependency injection + async function handeling without any boilerplate code.
P.S. Since ES6, javascript is wonderful. Functional code often really looks like lisp. Pity that we don't have macros (yet, and actually there is a way (sweet.js).
P.P.S. If DrBoolean got you hooked. You might want to check Ramda and fantasy-land. The former is a more functional minded underscore/lodash, the latter a specification (and community) for algebraic data structures in javascript to which a lot of new libraries adhere to.
This page makes me wonder about monads in the same way.
Here are some suggestions on how you might close some of those gaps a bit (I think allowing yourself to go over a sentence here and there should be ok).
You use fmap more than once without having defined it.
Currying: You need to define partial application.
Map and filter, I'd use collection instead of list. There is more nuance but that is good enough at this level.
Morphisms generalize the concept of function. They can be thought of as capturing structure (such as a set equipped with + and 0) preserving maps (which is something analogies try to do).
lazy evaluation could do with mentioning thunk, then you'd have to define what a thunk is, of course.
Fold: Folds are a lot more interesting and it's not clear what you mean by your given definition. I suggest defining it in terms of structural recursion.
Category: It's worth defining what objects mean to a category. As well, explicitly mentioning the laws of identity, composition and associativity rather than just the nebulous wording of configuration would be beneficial.
Functor: A more useful foundation is in thinking of functors as morphisms between categories.
Types: There is much more to types than this. Wrong in the correct direction is to think of types in terms of sets. Better yet, as propositions.
Type Classes: Since you mention parametric polymorphism, you should also mention ad-hoc polymorphism and how type classes and interfaces are examples.
algebraic data types: There's a lot more to algebraic data types than this. After defining sum types and product types elsewhere, you can talk about why such types are called algebraic.
parametric polymorphism: what is a type variable?
monoid: Moniods also need an identity element, and giving examples is always useful: natural numbers: +,0 or strings: +,"". One reason monoids are of special interest to computing is because they possess associativity, which is useful when parallelizing.
Actually just two (bind and return). And three laws which are typically not captured in the type system and which must therefore be tested separately.
It may not cover all the nitty gritty about what is and isn't a monad. But it gets you a long way to understanding why you might use them.
For example, Lift is defined way before Functor, and fmap is never defined so I had no idea what Lift was about despite that nice concise sentence.
It isn't uncommon to see someone w̶i̶t̶h̶ ̶a̶ ̶f̶r̶a̶g̶i̶l̶e̶ ̶e̶g̶o̶ explain this stuff in a way that is needlessly complex and full of jargon that scares folks off.
Thanks for the great work here. We need more of this kind of thing in the FP world!
A monoid is a a type with an associative function and an identity function