I did quite a deep dive into Monads and their laws, and I thought it might be useful to go into some of the stuff I found. Maybe it'll help you get it too!
Monads turn out to be pretty simple. They might look like Functors a little -- there's good reason for that! -- but I think a better place to start is to understand Monoids.
(I don't think they covered Monoids. I can't think why, they're simple and a great introduction into Monads.)
Monoids are a Typeclass which just impose some useful guarantees for how your data's going to behave. They provide two important definitions -- mempty and mappend -- and they obey a couple of rules to make sure mappend doesn't misbehave. mempty should be an identity -- so it'll do nothing if we involve it with mappend. mappend is just some function to combine two values in two Monoids, where the types are the same.
class Monoid a where
-- an "Identity"
mempty :: a
-- This has to obey some laws so it behaves!
mappend :: a -> a -> a
-- You can ignore mconcat -- the default defined is almost always used. mconcat is basically just a repeated mappend.
mconcat :: [a] -> a
mconcat = foldr mappend memptyNow because mempty is an identity, when we use it in another operation, it shouldn't affect the output. Particularly, mempty <> a === a, and also, a <> mempty === a. Here, we use <> as shorthand for mappend. These are the left and right identities. We care lots about them! (And they're useful for monads later, hint hintaroo)
There's one more thing we care about. The order that we apply <> in shouldn't matter. You could write this like (a <> b) <> c === a <> (b <> c). This is caled associativity, and it's useful also. For me, this is the one I particularly have to bear in mind when thinking about Monads later.
A neat example for this would be integers, where mempty = 0 and mappend = +. See how it obeys all three of those rules?
0 + a = a
a + 0 = 0
(a + b) + c = a + (b + c)
Gosh that's nice. If integers weren't guaranteed to work like that, we would be Up. Shit. Creek. That wouldn't make any sense! Code would break all of the time if we had to be careful about things like the order we added numbers up in.
To pick a more useful example for later explanations though, here's the same thing for the List:
instance Monoid [a] where
-- An empty list is a perfect example of an Identity.
-- If we use it in any operations, like adding it to another list, it'll change nothing!
mempty = []
-- We can append one list to another using mappend. And, it behaves *just like we want it to*!
mappend = (++)Ace! Lists are monoids too. That actually makes a lot of sense -- can you imagine if it was the case that we added an empty list to a regular one, and you just got back gibberish? Nobody wants lists that act like that. Or, if they didn't obey the last law, called associativity!
When you're happy with that, we'll table Monoids and come back to them later. Bear them in mind! But they're unrelated to Functors, and trying to put the two together will just break your brain. Better to put them to one side, and remember them when we discuss Monads.
Once you're satisfied that the Monoid laws make sense, let's move on to Functors!
A'ight. Let's put a pin in the monoid discussion.
Monoids are great for when we've got a bunch of values, and we want to combine them. But the types are the same! What if we want to apply an arbitrary function to our data -- not just mempty -- and that arbitrary function might change the type of our data too! Then, we've got nothing.
Except...
a_naughty_little_function :: a -> bThat would do for changing types, it's just a nightmare to get it inside our data and actually perform! Remember treezip? Remember how we'd write our tree functions, but we'd be deconstructing the trees in the pattern matching for our functions, and the code was always inelegant and ugly -- YUCK.
It would be better if we could, rather than deconstructing the trees, just chuck the function inside our datatypes and let Haskell just perform our calculations.
But we often write datatypes with lots of different bits! How would Haskell know how to apply some function a -> b to a whole tree, for something like treezip?
We make our trees Functors. This lets us tell the machine how to map a function across all of the data in our datatype. Got a list? We're basically just mapping across all of the list's contents, right? So...
instance Functor [a] where
fmap = map...but you could define your own, more complicated fmaps if you wanted to, also. That link's to my Treezip submission definition of functor for my Tree.
Fmapping lets us easily apply a function inside our datatypes. The list's a great example -- we can map over it, and operate on the list's contents, without having to do some awful clunky stuff!
We have an issue though... these are really hard to compose. It's not trivial to keep fmapping a whole bunch of functions on top of each other. Also, how do we know that they're safe? We don't have any guarantees like we did with Monoids about how that function might operate! For safe, easy composition of functions on our datastructures, we want some sort of lovechild that combines the safety of Monoids with a Functor's ability to actually do some computation, maybe change types, and be pretty useful.
A Monad is some sort of lovechild that combines the safety of Monoids with a Functor's ability to actually do some computation, maybe change types, and be pretty useful. Exactly what we wanted. It's like maths christmas.
How do Monads do that? They take the Monoid laws, and rewrite them to work for function application! That's basically it. We need a left identity, a right identity, and an associative law, just like before -- only now, like a Functor, we want to be able to change something's type.
The idea of an mempty doesn't really feel right when we're not talking about values to combine anymore, but about functions to apply. We'll define return instead.
return is actually quite like the identity function:
id :: a -> a
id x = xOnly now, we want to make sure our end product is monadic. So our identity function will take some value, and it'll just wrap it in our monad m:
return :: Monad m => a -> m aSweet! We have something like mempty, which is suitable for monads.
We also had something which operated on our values for Monoids, which just combined things together with mappend. Now, though, we want to apply a function! What does that look like?
Functions usually look like a -> b, but we're not that lucky here, because again, we want to make sure our output is monadic. So, our bind function needs a slightly different signature... the function we want to apply will look like return, raising something into our monad, but it'll also perform some computation, just like our functors did. So... it'l take an ma, apply something like the return but with the option to change type -- something like a -> m b -- and then return our lovely monadic value with come contents we've operated on:
>>= :: Monad m => m a -> (a -> m b) -> m bNOICE. We've got everything we need! RIGHT?! Now we just need to work out what our monadic laws are and WE. ARE. SET.
This is the final bit. If you're happy and you don't want to have to understand this and you want to quit while you're ahead, now is the time to do that.
We need three laws: the left identity, the right identity, and the associative law.
The left identity is pretty straightforward:
return a >>= f === f aWe can see that that's the case, because f :: a -> m b, and it's going to take the value from the first monadic value -- here return a -- and then compute on it.
I'd get comfortable with this idea before continuing -- if it looks a little strange, that's because it's a little strange! Get some paper and write out the types and play with the idea for a minute if you're unsure.
The second monad law is similar, but slightly different. We want to show that it doesn't matter which side we're running return on, right? So one way to do that would be the above. We can execute f a on one side, and it doesn't matter that return wraps our value up first. The end product is still f a.
...what if we've already got a monadic value on the left of bind, and we don't want to change it when applying return on the right instead? then we'd get:
m >>= return === mJust like before, if that feels weird, then play with it on paper for a minute and lay the types out for yourself.
The third law, associativity, was the strangest when we were working with our Monoids. So it'll look even weirder with our Monads! Saving the best until last.
m >>= f >>= g === m >>= (\x -> f >>= g)This is really just associativity in action. The left hand side one will feed our monadic value m to f first, then feed the result into g. The right hand side will do the opposite -- we make a lambda which effectively composes f with g, and then feed that lambda our monadic value. Notice the types:
m :: Monad m => m a
f :: Monad m => a -> m b
g :: Monad m => b -> m c
-- so, for the left hand side:
m >>= f :: Monad m => m b -- We computed some b value when we performed bind.
(m >>= f) >>= g :: Monad m => m c -- because we've computed on the earlier output, m b.
-- and, for the right hand side:
(\x -> f >>= g) :: Monad m => a -> m c -- Because we've composed f and g's types together!
m :: Monad m >>= m a -- by definition...
-- this gives us:
m >>= (\x -> f >>= g) :: Monad m => m c --- which is the same as the left hand side, meaning things which obey this law are associative, just like we saw in our Monoids.Now we have the final law. And we're done!
Monads are kind of like Functors which obey the Monoid laws. They get weird, because we need to adapt the Monoid laws to function application! But when you spend a little time with them, you can see that they're actually friendly little buggers. We've just got to understand why they got the way they are.
If you with Monads were weirder and began making Haskell's type system much more complicated, check out arrows, which show that God is dead.
Monads are really nice! But that's a lot of extra work just to be able to compose changes to things we trap inside our datatypes. Applicatives are also tasty, because they let us apply functions to our datatypes without the cruft of Monads, by trading off some of the safety they give us.
In particular, Applicatives define something like a Monadic return, which it calls pure, as well as something like a really basic bind, which is calls <*> (pronounced "apply").
class Functor f => Applicative f where
-- | Lift a value.
pure :: a -> f a
-- | Sequential application.
(<*>) :: f (a -> b) -> f a -> f bSo, we extend the Functor to allow for applying functions trapped in a datatype to values in the same datatype. We can raise a function into our Applicative using pure, and then apply that function to a value using <*>. This gives us a lot of what bind gives us in terms of things like composition. The only issue is that they're a little less rigorous with their safety -- so lots of people prefer Applicatives to Monads for writing things like parsers.
There's really not much more to them! (They also have to obey laws, but we don't care. They're not important, and frankly, I haven't looked into them much. We're already going deeper than Jeremy's ever going to ask!)
I'm not sure what else to write about them really, but I DID use these in my treezip exercise too, so here's the full submission -- heavily commented! -- if you want to see how applicatives can actually be used, and what they give us that Functors don't. I use <*> in my treezip function. When you're reading it, keep partial function application in mind...