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".
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.
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. :-)
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. :)
> 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.
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?
Monad, like any interface, is useful because we can abstract over it. Let's take an example from Java: both ArrayList and LinkedList implement List. This means I can write code that is agnostic to the implementation of List, and later I can drop in any implementation I want. Seen from the other direction: if I write something that resembles a list and I implement the List interface, all of the code that's compatible with List will also be compatible with my new implementation.
Similarly, if I define a new data type, and realize that it can implement Monad (or more precisely: that it has a monad instance), then I'll be rewarded with a giant library of code that's already compatible with my new data type [1]. Monad is an especially interesting interface because (1) it turns out many things conform to it [2] and (2) it comes with a set of algebraic laws. There is some controversy over how strict we need to be about the algebraic laws, but in some sense the algebraic laws are part of why such a general interface can be meaningful at all.
So yes, it's true that Monad allows us to sequence effects in a lazy pure language, and that's important, but I think a more down to earth reason to be interested is that it allows for more code reuse [3].
[3] It's also worth mentioning that Monad gets all the attention, but Haskell if flush with other mathematically inspired interfaces that are just as general.
>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?
Monads are a mathematical concept, like a ring. "Maybe" is a monad in whatever language you use it in, just like integers are a ring in whatever language you use them in. Pointing out that complex numbers, rational numbers, nxn matrices are all examples of rings and wrapping everything up into a type class doesn't add to the complexity of the language.
The 'why' question is my pet peeve too - often because the answer to
> Why do I need a monad then, if there are similar constructs in other languages that don't need the understanding of monad?
is that you usually don't.
Where I work, people use a handful of monads daily, but most people know the monad laws, nor do they need to.
But now that they know a few specific monads, the "why" of monads is really, well, we needed certain convenience methods (namely bind aka flatMap) to make using e.g. Maybe or promises not a huge pain. And we chose a uniform way to do it across different wrapper types, so that we minimize the cognitive overhead.
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.
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.
> 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?
They remove the need to type the same shit over and over again. With a list monad you avoid having to write the loop constructs, for the Option/Maybe monad (optional value) you avoid having to write if/then/else, for the Either/Choice monad you avoid having to write if/then/else and manually propagating an error value on failure, for the State monad you avoid having to pass a context value through as an argument to every function, for the Try monad you get exception handling and error propagation like the Either/Choice monad, with the Writer monad you are able to do logging without a global logging system or having to manually pass through a logging context, etc.
Ultimately they're there to reduce boilerplate and to help write more composable and reliable code. There are other benefits, but this encapsulation and abstraction of common patterns is what most programmers strive for, no matter what language they use, so I feel it's important to put them in that context.
Let me give you a very simple example. I'm going to use C# because it's been a long time since I've done any Haskell and I'll probably get it wrong.
I'm going to create a monad called NoNull. If at any point it sees a value that is null then it will stop the computation and return without completing. It's a slightly pointless example because C# has the null propagating operator, but conceptually it should be easy for any programmer to grasp that using null is bad, so being able to 'early out' of a computation when you get a null value is desirable.
First I'll define the type:
public class NoNull<A> where A : class
{
public readonly A Value;
public NoNull(A value) =>
Value = value;
public static NoNull<A> Return(A value) =>
new NoNull<A>(value);
public NoNull<B> Bind<B>(Func<A, NoNull<B>> bind) where B : class =>
Value is null
? NoNull<B>.Return(null)
: bind(Value);
public NoNull<B> Select<B>(Func<A, B> map) where B : class =>
Bind(a => NoNull<B>.Return(map(a)));
public NoNull<C> SelectMany<B, C>(Func<A, NoNull<B>> bind, Func<A, B, C> project)
where B : class
where C : class =>
Bind(bind).Select(b => project(Value, b));
}
It's a class that has a single field called Value. The two functions to care about are:
Return - Which constructs the NoNull monad
Bind - Which is the guts of the monad, bind does the work
Select and SelectMany are there to make it work with LINQ. I have implemented them in terms of Bind.
As you can probably see Bind is encapsulating the test for null, and if null is found then the result is Return(null), it doesn't run the `bind` delegate.
Next we'll create some NoNull monadic strings:
var w = NoNull<string>.Return("hello");
var x = NoNull<string>.Return(", ");
var y = NoNull<string>.Return("world");
var z = NoNull<string>.Return(null);
The last one contains null, the bad value.
I can now use those values like so:
var result = from a in w
from b in x
from c in y
select a + b + c;
Notice there's no checks for null, the monad does that work for us.
In this instance, result.Value is equal to "hello, world".
Now if I inject a bad value into our monadic computation:
var result = from a in w
from b in x
from c in y
from d in z // <--- this is null
select a + b + c + d;
Then result.Value is equal to null and the `a + b + c + d` didn't run at all.
The alternative is this:
string w = "hello";
string x = ", ";
string y = "world";
string z = null;
string result = null;
if (w != null)
{
if (x != null)
{
if (y != null)
{
if (z != null)
{
result = w + x + y + z;
}
}
}
}
Where the programmer constantly has to do the work that the monad will do for free. I've nested those if statements to try and give you the impression of what the series of 'from' expressions are in the example above (in Haskell it's known as 'do notation'). Each 'from' creates a context over the whole of the rest of the expression.
For the avoidance of doubt about the nesting, I could have written it thus:
var result = w.Bind(a =>
x.Bind(b =>
y.Bind(c =>
z.Bind(d =>
NoNull<string>.Return(a + b + c + d)))));
Here [1] is an example of a Parser monad in action in C# (it's part of a parser that parses C# source that I use to generate API reference docs for my github projects [2]). This runs code 'in the gaps' between each 'from' statement. What it does in those gaps is check if the parser above it failed, and if so it bails out with an appropriate error message based on what it expected. But you don't see any if(result.IsFaulted) ... code anywhere, or maintenance of the position of the parser in the input stream, because that is encapsulated in the Parser monad. It makes the code very clear (I think) in that it's not cluttered with the regular scaffolding of control structures that you usually see in imperative languages.
What's really quite beautiful about monads is the way they compose, and I think this is especially beautiful with parser combinators. A Parser<Char> which parses a single character has the same interface as a Parser<SourceFile> which parses an entire source file. Being able to build simple parsers and then combine them into more complex ones is just a joy to do. Clearly parsing isn't unique to monads, but there's an elegance to it (and monads in general) which I think is hard to resist.
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, ...).
> 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)].
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!
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.
>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.
I feel a bit dumb asking this, but your explanation doesn't make it clear to me why you can't think of a bind on Maybe as a flatMap on a List with 0 (Nothing) or 1 (Just) elements. Could you elaborate further on how thinking of a bind on Maybe as null propagation eliminates it also being interpreted as a flatMap on a restricted-size list?
You're right, maybe is equivalent to the type of lists with at most one element. There are however monad instances which are genuinely different.
For example the state monad is defined as
F(X) = S -> S*X
I.e., a value of type F(X) is a state transformer which takes a state argument of type S and produces the new state and a value of type X. In this case, bind is sequencing of state transformers.
Using the state monad you can write code that looks like it uses a global variable of type S, while being completely pure which makes testing and refactoring easier, and of course doesn't pollute the rest of the program.
Unfortunately, not all monads are list-like (though there are a lot that are). The most notorious example is probably Cont[1], the monad of delimited continuations. State, ST, and IO all struggle to be interpreted as lists as well.
Bind is flatmap in the case of lists. Bind is way more generic than just the list monad, and the name "flatmap" doesn't apply to most other monads -- most of which are not List.
Various people seem to be arguing that "flatMap" only makes sense for Lists and similar containers, but I don't really see why. Yes, you have to broaden your notion of "flattening" to understand it, but I think that's a lot easier for people to learn than a "new" operation called "bind".
I've been using Scala for a while after learning Haskell first (and understanding monads), and I've noticed how much more easily people understand flatMap, even for e.g. Futures.
Maybe it's just a difference of perspective, but I do not understand what is so intuitive about flatMap that makes it "easier". The name does not fully capture the idea of bind and requires mental gymnastics to apply to less concrete usecases, whereas bind is not so restricting, while still referring to the use of the abstraction as "glue" and hinting at its relation to composition.
I think the thing that makes it more intuitive is that it's really easy to see how "flatMap" relates to "flatten" and "map", whereas it's not immediately obvious how "bind" relates to "join" and "map".
And I think expanding a concept which someone already comfortably understands is a lot easier than asking them to learn a new one, even if you say it's kind of similar.
And FWIW, I don't think "flatten" is particularly unintuitive name, even for the more abstract cases, because it's still f (f a) -> f a. The mental gymnastics here is understanding how a Functor can be more than just a container, and you kind of need to learn that anyway.
Bind is a great name. When you have a function that takes a monadic value of type `m a` (e.g. List[A_] in scala I think) it becomes convenient to program with lambda functions. For list comprehension, you can program like this (python notation now, since everyone reads it):
That's a list comprehension. You bind the monadic values (list_of_xs) to element values (x). On lines 2 and 3, you can think of x as a bound variable that was assigned to one of the elements of list_of_xs on line 1. Then we "assign" y on line 2, and it's in scope on line 3. "Assign" would have also been a decent name for it. It's way more intuitive for me to think of those three lines as assigning/binding x and y to be summed together, rather than thinking of one flatmap of a lambda to flatmap of a final lambda to a function. The abstraction of variable binding just fits.
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.
My general problem with Haskell articles and such: they are written as if you already understand Haskell. They make total sense if you know the language, but if you are trying to learn are mostly useless if not more confusing. Or even worse, they devolve into dense academic prose even when writing introductory articles.
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.
A higher-level type (which is a function, if you allow functions in your type system). Examples:
List of a
One or zero of a
A randomly chosen a
A function that takes an s and returns an a and another s i.e. s -> (s, a) aka "a stateful computation returning a)
A routine that reads a file and returns an a.
In each case, the point is that you can a) write code that acts as if the k isn't there and hence b) re-use code between all of these things without changing it.
I'm going to take the opportunity to recommend http://www.cis.upenn.edu/~cis194/spring13/. Do all of the exercises, even the really basic ones. What you learn by the end will blow your mind.
Thanks, I'll try it out! Is it applicable for someone with zero Haskell experience? Am I supposed to join a class which starts somewhen or how this site works?
It's literally just Brent Yorgey's lecture notes. Read the notes for week 1, do the exercises, repeat. I learned Haskell from scratch using it. Use stack and a random text editor.
What it won't do is make you fluent in modern Haskell. That would be a much longer course.
However, I guarantee that if you work through it you will have some great "Wow" moments.
You advice here may be good; am not questioning that. However, question does come why can't there be a shorter explanation for people who already know programming. Most people are unable to explain it well, or at all, leading me towards a belief that they don't get it themselves as yet.
I'm not looking for a single sentence explanation or definition. I'm willing to read more, and the structure you suggest of showing precisely worded definitions along with positive and negative examples would be great! However, I would not want to start with reading how to install a compiler, how to add two numbers in Haskell, etc.
I have similar issues elsewhere when people start with hello worlds and getting started in introductions to projects and programming languages without spending enough time on what the thing is about.
> why can't there be a shorter explanation for people who already know programming.
Why can't you learn chinese very fast if you already know a handful of european languages ? The answer is the same : the underlying concepts are different.
Sadly, there is no easy shortcut to understand these concepts. The best that can be done (and it's hard enough already), is to make learning entertaining.
The line of reasoning you have is correct as such, however, I find the analogy to be less than perfect. I do not need to be taught how to setup my computer for Haskell compilation or how to add numbers in Haskell to understand what is a monad.
Eh, I think you can skip most of the chapters if you've learned functional programming before. The important things to learn are typeclasses and higher kinded types.
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.
I'm not saying you shouldn't use examples to learn, I'm saying you should probably learn X and Y (type classes and HKT) before you try to learn Z (monads). Use as many examples as you like to learn them, but if you don't understand type classes and HKT, you will probably struggle to understand monads.
I've noticed the same thing - Haskellers are terrible at describing them. I'm not at all a Haskell expert, but I think I understand enough of Monads to explain them.
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.
This seems too simple. Then what is all the business of using them to contain side effects, like the IO system? Others talk about controlling program flow.
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.
Just to expand a little bit upon the sibling comment.
Let's say you need a function that maintains internal state. Now, in non-pure languages, you could that by simply referring to some global variable, but let's agree that's bad. So how can you model internal state purely?
Simple, your function takes the current state and produces a new state, along with its result. So, a pure function like:
f(String) => Int
turns into the stateful function:
f(String) => (State => [Int, State])
I.e. a function that returns a function that takes in a state and produces a result and a new state.
Cool, but now let's say we have another function g:
g(Int) => (State => [Double, State])
Let's now say we want to compose those two functions:
let result = g(f("5"));
However, this won't work, becase f produces (State => [Int, State]) but g expects Int.
So, here's bind for the State monad (implementation is not important):
That at least gives me a base. I did wonder why you say flatmap is
> flatMap(List<a>, a => List<b>) => List<b>
but that isn't the same as bind, since bind took two functions and flatmap takes a list and a function.
However, I do kind of understand. Compare this to the (currently) 3 responses below that quickly turn into text mush simultaneously treating me like an idiot who has never understand abstraction before or treating me like I'm been programming Haskell for a decade.
At some point I'm just going to cut my losses and ignore Haskell. It isn't the language, but the less that elucidating community support.
bind(StatefulFunction<a>, a => StatefulFunction<b>) => StatefulFunction<b>
flatMap(List<a>, a => List<b>) => List<b>
Look at the structure. Don't pay attention to what List or StatefulFunction actually are, that's not important here. The thing to focus on is that if you can provide this kind of general function for something, then that something is probably a monad.
I.e. a function that takes in Something<a> and a function from a to Something<b> and produces Something<b>.
So why is this pattern so useful that everybody freaks out about it?
Well, that syntax sugar I showed you at the end, let's look at it again:
do
a <- f
b <- g a
h b
The general idea here is that "a <- f" is translated into bind(f, a => ...). The whole block would turn into
bind(f, a => bind(g(a), b => h(b)));
Bear with me. Now, let's look at one more example:
bind(Optional<a>, a => Optional<b>) => Optional<b>
Optional<a> is just a data type that maybe contains an <a>. Think of it as a safe replacement for null. So, bind for Optional looks at the first argumenta and passes it on to the function and returns its result, if the Optional is not empty. If it is, bind also returns an empty Optional.
Now let' say we have a bunch of Optional producing functions:
getUser(userId) => Optional<User> // user may not exist
getAddress(User) => Optional<Address> // user may not have entered an address
getStreet(Address) => Optional<Street> // address may be weird
Now ok, what would we do in a language without monads?
user = getUser(userId);
if (user.hasValue()) {
address = getAddress(user.getValue());
if (address.hasValue()) {
street = getStreet(address);
// do something
}
}
Well, that's not great. But because Optional is a monad and we have that nifty bind sugar, that's how that code would look like in Haskell:
do
user <- getUser userId
address <- getAddress user
street <- getStreet address
Much better.
More generally, it turns out monads are literally everywhere. The guy that talked about CPS transformed programs being monads is right - that's the continuation monad.
Let's look at that. If you know node.js, you know that its API is basically asynchronous:
fs.open(path, function(fd) {
fs.read(fd, ..., function(result) {
// do something with result
fs.close(fs, function() {
// file closed
}
}
}
Well, that's ridiculous. But becase we have the continuation monad, we can write exactly the same thing in Haskell:
do
fd <- open path
result <- read fd
// do something
close fd
So why are monads so useful? Because they are so general. They can be used to abstract over many many things that exhibit the basic pattern (S<a>, a => S<b>) => S<b>. Not to mention that when you write a function to generally work with monads, it will work for ANY monad. List, State, Maybe, Cont - doesn't matter.
There's not much more to it than recognizing that pattern. That's it. Once you see that that's literally it you'll start seeing monads everywhere :)
> Let's say you need a function that maintains internal state. Now, in non-pure languages, you could that by simply referring to some global variable, but let's agree that's bad.
Instead of Stone Age ideas like global variables, you could create a Lisp or Javascript closure, or use a C++ functino. Do monads offer a big enough advantage over those approaches to justify the endless trouble of learning them?
In Lisp, you should use a global variable when you need a persistent module-level state, and let your defun forms be top-level forms:
;; bad
(let ((s (make-state-thing)))
(defun function () ...)))
;; good
(defparameter *s* (make-state-thing))
(defun function () ...)
That defparameter might be defvar: it depends on whether you want to re-initialize the state variable when a new version of this module is loaded, or keep the old value.
Speaking of which, with the let, you don't get that decision. For the defun to have its effect, the form has to be evaluated. Every evaluation of the let instantiates a new binding for s in a new lexical environment, end of story.
Even if we have the defparameter, we can redefine function while keeping the same state.
It's also easy to inspect the state. A the REPL, just evaluate its name: there it is. You don't have to whip out a closure environment inspector.
defun is a "stone age" tool anyway, which destructively overwrites a global function binding. Wrapping it with a captured lexical environment is a form of situational irony in programming (if not indeed verbal).
Maintaining state was just one example. See my other comment [0] for others.
Regardless, you can't maintain state with closures in a pure language. You could close over some local "variable", but that variable would be immutable. In an impure language that would work, but then you're back to managing global state, even if that state is not defined at the top level (i.e. global in the sense that different closures could still have access to the same piece of state, concurrently).
That's the thing with powerful abstractions: they apply to so many things that seem unrelated, that it may be difficult to see the connection. But that's where all the power lies: being able to use a common abstraction across so many different problems gives you extremely powerful means to express generic operations.
Say you wanted to iterate over a list of image files and apply a transformation to them. In haskell, doing that work synchronously and doing it asynchronously can use the same function, just in a different monad, because the definition of bind determines the execution strategy.
The monad abstraction provides a way to encode a dependency between "operation 1" and "operation 2", or inject behaviour between "element 1" and "element 2" when processing a data structure.
The type signature of bind is "m a -> (a -> m b) -> m b". It might look complicated, but it states "given a monadic value with an inner type of a, and a function from a to a monadic value with inner type of b, you will get a monadic value with inner type of b"
This can be used to access data "inside" a type where you might not have direct access, in such a way that bind determines how the access happens so that it can enforce things like "The preceding IO must have been finished" or "The future must be completed" or "The list values must be concatenated" or "You must compose the continuations properly" or "If any operation results in Nothing, the result is Nothing"
Haskell IO is the usual example of this. Since the IO type is opaque, you cannot construct values of IO yourself directly. An IO String (such as getLine) represents an IO operation that results in a String value. Similarly, the "putStr" function (of type String -> IO ()) is a function that takes a string and results in an IO action that "does something and the value does not matter", or in this case, prints the string to the screen.
However, you can't just compose getLine and putStr directly, because the types don't match. You need to get the value "inside" getLine first.
This is what the bind function allows you to do. And it's defined for the IO type, in such a way that IO ordering is enforced. You can't not use bind, because you have no way of accessing the String value inside getLine without it.
I don't know if my explanation helps. The seeming "complexity" of monads arises from the fact that you can apply the same simple abstraction to so many different things, often in seemingly unintuitive ways.
The comment you are replying to is describing the concrete example of the List monad. To answer you direct questions, it is probably better to look at another example: the State monad.
The idea behind state is simple. Suppose you have a bunch of functions that you want to call in sequence. This is a simple enough problem; just do f(g(h(x))) or `h(x) |> g |> f` [0].
Now, suppose that, in addition to piping a value from one function to the next, we want to keep track of additional state. For example, maybe we want to use a psuedo-random number generator in some of the functions and have to keep track of its internal state. One way to do that would be to simply modify each function so that the returned value includes the state; but this quickly becomes unwieldy. The State monad provides a way to automatically thread the state through the functions. So we can do:
put initSeed >>= h >>= (get \currentSeed -> g currentSeed) >>= (get \nextSeed -> f nextSeed)
or (with a bit of syntactic sugar:
put initSeed
h
currentSeed <- get
g currentSeed
nextSeed <- get
f nextSeed
in this example g and f would be expected to call put to update the internal state.
Now, suppose you want to keep applying a function until some condition becomes true about the state. In this case, it makes sense to talk about a while loop:
while (get >>= \state -> state =/= 7) f
The above snippet will repeatadly bind f until the internal state is 7.
It turns out, that we can implement while in terms of only the Monad interface:
while condition action = do
x <- condition
if x then (action >> (while condition action))
else return ()
It turns out that most control structures can be encoded into monads in this way.
The IO system is a bit hacky. The idea is that the universe is a big state machine. So, when we do `println "Hello World"`, we are not causing a side effect, we are just updating our internal state to say that we printed "Hello World". Simmilarly, getLine just peaks into our internal state to see what the input at the current time has always been. Of course, for some reason, GHC does not give us the full get or put functions for the IO monad; but they could exist in theory, and that is enough to pretend that side effects do not exist.
[0] Not actual haskell because we can't agree on a name for the pipeline operator I am calling "|>" here.
So this is one example of a Monad. Go through the same process with different "datastructures" to see the power of it. First try with a "Maybe" monad, and then a "State" monad. The generalization of that idea is the monad.
The power comes not from the complexity, but from the realization that this simple idea applied in alternate contexts (ie on different datastructures) allows many powerfull solutions to problems.
The idea is fundamentally simple - applying that same simple idea in different contexts provides the value. It is a simple idea, it's just impressive how many different contexts it works in to solve problems. Problem domains that we normally would have felt have nothing in common.
> 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.
Monads are very simple. They just aren't easy because most people don't have the base of terminology. When you grok them you'll laugh because you'll realize how simple and powerful and obvious they seem in hindsight.
This is the reason so many people write monad tutorials after they learn them. It's actually really weird. Does anyone else have some examples of things they learned which seemed really difficult but turned out to be really simple in hindsight?
> Does anyone else have some examples of things they learned which seemed really difficult but turned out to be really simple in hindsight?
Sure: everything.
Everything is complicated until you learn it, and then it looks simple in hindsight.
You're just confirming what OP said: it's not easy to come across an article explaining monads or Haskell that doesn't implicitly rely on the fact that the reader already understands monads or Haskell.
Beautiful insight. I now realize that simple and complex are about the concept being learnt, and easy and and hard likely to be about the process of learning. There would be correlation in general, however, not always. :-)
I have seen many examples of things which are easy at the end, but the process of reaching there was hard, sometimes because of initial ignorance of my own or of mankind overall.
the latter phenomenon occurs at least three or four times over in good (rigorous, proof-based) math classes.
I've had this happen for
- everything from linear algebra (at least 20 things)
- all kinds of stuff from mathematical optimization
- inequalities, which are really difficult until something "clicks" and then when to apply them becomes obvious, cauchy-schwartz and jensen's in particular
- induction (this was a long time ago / early in my math career)
- diagram chases
- the entire typeclass stack from FP (functor applicative monad, then all the monad interfaces)
- huge chunks of axiomatic probability and measure theory (what do sigma algebras really mean, what is a good definition for integration, what is continuity of measure, dinkin's pi-lambda theorem)
- and so it goes on
I am still waiting on some of the following things to click so that I may abuse them productively as well:
- LLL
- yaos min-max theorem
- lots of results from logic
I surmise this happens for monads and freaks developers out because it's one of the few pieces of serious math (i.e. no handwaving, given as a rigorous construction, etc) most people come across, so the phenomenon catches people off-guard.
I do like this thing! I love math. I tutor young people in math at a local school. I've applied to an undergrad math program at Toronto and Waterloo as well. Hopefully I can get in...
things that are very similar to other things when expressed concretely, but actually exist at different levels of abstraction? things that are counter-intuitively awkward to express by way of examples, because too many things are examples, sometimes in multiple subtly different ways?
adjunctions (etc.) in category theory seem like 'above paragraph : the movie', but i can't claim to understand them in full generality so i'm unsure.
Lots of people already have. The problem is that those who try to read up on it haven't built the conceptual bridge to get there. Monads are a simple piece but they sit atop a tower of simple pieces, none of which can be skipped. People who hear about Haskell try to jump in and learn them without having the foundation they need. They see the superficial similarities between Haskell and other languages but fail to grasp the more significant differences: higher-kinded types and type classes.
>Lots of people already have. The problem is that those who try to read up on it haven't built the conceptual bridge to get there.
No, as someone who understands monads (and not thanks to the explanations usually given) the real problem is that most explanations are crap and needlessly complicate the matter. Including every one I've read thus far (well, up to when I made my comment) in this thread.
It's as if they can't lay off Haskell notation and concepts for a moment to give people the overall picture. People, stop mentioning "functors", "monoids", ">>=", "bind" etc in your Monad explanations. Also drop the Haskell function definitions.
Even fmap shouldn't be taken for granted (as something already known) in a Monads explanation. Just describe what it does, giving a simple example. And when talking to Javascript programers use types and names of types that they already know, such as "array", not List. Even such simple terminology distinctions like those matter.
>They see the superficial similarities between Haskell and other languages but fail to grasp the more significant differences: higher-kinded types and type classes.
The whole magic of explaining is to give an idea of the "significant differences" without requiring any foundation beyond what an average blub programmer already has.
The condescension bugs me a little: I must not have enough background, Haskell is too high-level for me, etc...
I'm a pretty good developer, and my language skills are all over the place. I did a lot of Scheme and Lisp early on. I used to try all the turing tarpit languages. I do mostly C++ and Java systems work now. And my current learning is Go and Rust. I've literally written my resume in PostScript years ago, and I still use APL-derived languages. I read and learned lambda calculus over a cross country business trip even.
And even with this background I find Haskell at times inscrutable, more often than not because somebody is trying to give me a description filled with unknown terminoligy and lines of Haskell itself I have no idea what it means.
There concepts aren't foreign to every other languages. Show them to me in pseudo-lisp, and I'm sure I'll do a pretty good job of picking them up. It looks like you could even describe monads in C by passing around opaque pointers, with some caveats.
> They just aren't easy because most people don't have the base of terminology
That's like saying a giant, complex library with a nice, tight API is 'simple'. It's not, the complexity is just hidden.
Same thing with monads. Once you understand some of the machinery of category theory, or really grok functional programming, then yes, monads are 'simple', but all the complexity lies in getting there.
I think you're confusing complexity with learning curve. Complex things can be made easy to learn, if, for example, you have "a nice, tight API." Monads are the opposite. They are simple things that are difficult to learn.
Because it is far away from what you already know.
Haskell is a fairly simple language, but it very difficult to learn compared to a language I would consider much more complex like Java, because you cannot reuse as much of what you have learned from other languages. All the monad implementations are just a few simple lines of code, and understanding monad is just a matter of reading a few, reading the rules, and doing enough with them until their utility clicks. However, the type of abstraction they are and the way they are used are very different from the programming you are used to that they seem harder to learn.
A simple thing can be difficult because understanding why it works may be nontrivial. However, it remains simple (by definition) if understanding is not affected by complecting factors such as side-effects or the global state of the system. A pure function is always simple, even if it implements a difficult algorithm.
I hold the opinion that complicated things can never be truly easy: they can only have the appearance of ease until there comes a time that you must understand all the complexity.
I'll provide an example in math. Linear algebra is much simpler than calculus. Yet we teach high school students calculus but not linear algebra. Why? Because a lot of the complexity in calculus can be hidden away behind some hand-wavy definition of a limit and consider basically only smooth functions. That way, we have engineered our math classes to avoid the complexity underneath, and we have high school students finding calculus to be easy to learn.
Well, you really should know the amount of Haskell it assumes you know (typeclasses, maybe infix functions, arity etc) before learning about Haskell monads. Otherwise you're learning multiple concepts at once - why not learn about those other concepts in other contexts first? The Stephen Diel article even lists the prerequisites explicitly.
I posted that because I think it's the best you're going to get.
Monads can be two things: (1) a concept in category theory, (2) a rough implementation of that concept in a programming language.
If you want to learn about monads from the category theory perspective, great! This is really hard though, I wouldn't recommend it for most people (and haven't really even succeeded myself).
If you want to learn about a specific programming language's implementation of monads, you will naturally have to know how that language works. This road is far easier than category theory, but still requires knowing (for Haskell) what a typeclass is, what a higher-kinded type is, etc.
It sounds like you want an explanation without prereqs from either category theory or Haskell. If you google for monad tutorials you will find dozens of quick explanations, but I personally don't think this is a good way to actually understand them.
Because these languages lack a way of discussing something at the right "higher order" as Monads. You can implement them, but there's no word for the kind of thing a monad is. There's not even a real word for a type.
You need types. Then you need "higher order types" or parameterized types. Then you need a way to discuss a common set of operations which appear repeatedly for some of these parameterized types and it can't be OO-like.
You can exemplify the operations in, e.g., Lisp, but you have a hard time "talking about" the thing.
---
In Scheme, monads are the answer to the following question:
The functions (define (pure a) (list a)) and (define (join ls) (foldl append (list) ls)) are related to lists in the same way that (define (pure a) (lambda (k) (k a))) and (define (join z) (lambda (k) ((z k) k))) is related to CPS-transformed programs. What is the commonality?
The issue is that Haskell is inherently a language in which you're not programming anything that maps particularly well to the machine you're actually running it on. As a result, Haskell developers never actually talk in terms of what a program does on the machine, they talk in terms of what it does in their abstract model of computation.
This is sort of what I'm getting at, though. Haskell gives you the language to talk fluently about everything I was writing. If you use it enough it becomes second nature and these kinds of higher order concepts are easy. Monads are easy.
In languages which lack the tools to make it easy to talk about this stuff it's hard to say these things without sounding like a loon.
The only reason I sound academic is that the simple language I'm used to using has been denied.
To understand monads one must first understand monads.
I'm not even saying that a bit sarcastically. I've read countless "tutorials" and even tried messing around with Haskell in an attempt to grok monads. According to the link shared by GP comment, my understanding is still completely wrong.
There is a reason there is a joke about it.
"A monad is just a monoid in the category of endofunctors, what's the probleⅿ?" - James Iry, taken from [0]
I consider that quote to be a demonstration of the simple/easy axes referenced in a relative of this comment. It demonstrates that monads are simple things, since endofunctors, categories and monoids are all simple concepts.
As a scala developer the thing which got me on my way was the explanation "something which has a flatMap method". That's not entirely true but it gets you in the right ballpark.
If I define this in c++ lingo words barely change.
You take a c++ parent class with two virtual methods. These methods are "return" and "bind". In order to implement a monad instance you must derive from this parents class and implement the virtual methods.
I was translating your quote to c++ lingo not defining functions.
return takes a value and returns an instance of your template class containing the value.
bind takes an instance of your (template class A) a function of (type a ) to (template class B) and produces a value of (template class B).
If you don't care about the "laws" your definitions are expected to follow thats it.
The idea bind is you take a value of a template class such as (std::vector<Int> type) the value {3}, then based on value either pass it to the next function or return it.
one definition of bind would be if the vector is empty return it, if its not empty pass it to this function and return the result of that function.
return is just a way of placing a value into your template container class.
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!
Long explanation overall in the article, but based on 6th grade math. I understood it, and it stuck. Could someone extend the monad explanation from here? Maybe I'll finally get it :)
This was way more difficult than I thought and still doesn't look right. But at least I get to strike write a monad tutorial off of the bucket list.
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.
Start with a functor--a parameterized type with fmap. Maybe t, Either e t, [t], IO t, State s t, and so on.
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.
The author is mistaken. There are only two functions necessary for a monad: >>= and return
Also, the type of return is `a -> m a`. The type you cite `a -> m b` is a parameter to >>= (which has type `m a -> (a -> m b) -> m b.
The author might be refering to a quirk of the Haskell monad interface, which has to additional functions:
">>" which can be easily defined in terms of >>=. I assume this is part of the interface so users can override it with a more efficient implementation, but every implementation I have seen just uses the default one.
"fail" which is an error handler. This is being depreciated as a function of Monads, and moved into its own MonadFail typeclass. This also has a default implementation that just throws an exception.
> The author is mistaken. There are only two functions necessary for a monad: >>= and return
Probably because monads are frequently described as triples -- two functions and a functor. The author seems to have reduced that to three functions (presumably fmap) without realizing that it isn't sufficient.
I suspect the third function is the one for running the monad. It's different for each one, so it's not part of the type class, but you do need it to use a given monad. (Except IO, though even it has unsafePerformIO)
You're probably over-thinking this. Monad is not a difficult concept, but it is very abstract. Because of that, it's hard to say specifically that "this" is what Monad "does."
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.)
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:
Shorter explanation: Monoids are things you can concatenate together.
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.
Monads are not complex. A monad is a box. Any monad has two functions (plus others, imagine this is a minimal interface): bind and return.
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.
Here's an extended explanation of how monad 'lift' works:
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).
Thanks for your explanation. I confused as to why so much discussion and blog posts surround the topic of monads as if they were very difficult to understand then?
The TARDIS is a box from doctor who that is bigger on the inside (holds a small pocket universe inside). You can put anything inside the TARDIS.
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.
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.
To everyone new to haskell and confused: Don't judge haskell based on these definitions. They appear strange and crazy, but when you actually do stuff most of them turn out to be quite intuitive.
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.
I've found parser combinators to be a fun and useful way to play around with monads, since it's pretty easy to implement your own monads this way, and what better way to understand something, than to actually make it?
This is a good start and might be useful to other beginners. From the vantage point of someone who already knows what the words mean, I can fill in the gaps in your definitions but unfortunately, a beginner might not be so able.
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.
In Haskell and PureScript, `fmap` is a method in the `Functor` class, which is defined by
class Functor f where
fmap :: (a -> b) -> f a -> f b
for which instances should satisfy `fmap id = id` (and you get `fmap (g . f) = fmap g . fmap f` for free). If you can find a type for which you can implement `fmap` and satisfy the laws, then you have an instance of `Functor`.
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.
Agree. Also, order can improve. You talk about pure functions on the first sentence. Later you explain what a pure function is. Explaining pure functions before monads can help. Same case for functors.
One simplistic but useful analogy I've found is that monads are a way to control program flow with functions. A monad is to functional programming what if/else is to imperative.
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.
Question to JS people using Redux. Are the middlewares used to control side effects in actions considered monads? The action returns a description of the side effect, and the middleware handles the actual doing, leaving the programmer to focus on the pure aspects.
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!
There is an adage that if you see a lot of advertising for a medicine (think hair regrowth formulas, or pills of reflux disease) you know that none of them are any good.
This page makes me wonder about monads in the same way.
Haskell does have "fail" as part of the Monad typeclass. But it is being depreciated and moved into the MonadFail class.
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.
Hmm. They certainly have a naming and explanation problem in Haskell land. Some impressions from a few of these better explanations.
"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. :)
Pure functional programming means that everything a function does has to be part of the return type. That means you often get functions like
a -> Maybe b
Instead of throwing an exception or returning null to make the possible failure part of the return type. Chaining failable functions would be incredibly annoying, though:
let a = tryRead
if isNothing a
then Nothing
else
let b = tryParse (unwrap a)
if isNothing b...
In imperative code you could flatten this with early returns but that still is a common pattern, so lets abstract this!
tryRead >>= tryParse >>= tryProcess
The magic sauce is in the >>= combinator, pronounced bind or andThen. It returns Nothing instantly if it receives Nothing, otherwise it unwraps it and calls the next function.
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.
I get why you think that, but the names are actually precise in the way that terminology in an academic paper is precise. It's just not helpful to outsiders. It's arguably pretentious to draw on category theory to describe types and functions but that's academia for you. Haskell has become the language that academia built, for better or worse.
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.
> My early OOP/C++ books are finally more intuitive than something.
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.
It's a quick impression and in jest. Don't take it too seriously. ;) I respect that the author is making an attempt to simplify these things. Thanks for the recommendations.
Almost every programmer will have learned what a boolean condition is. Hence me bringing it up as a default explanation for something that's true or false.
"It's a conditional like what you evaluate in an If-Then statement."
Let me change it slightly so you can see how some might see it if no background in recursion:
"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.
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"