obligatory monad tutorial

[xax]

so i wrote basically one good, general-purpose Haskell Code post on tumblr, so i figured i could fix it up a little and post it over here too. it is i guess somewhat monad tutorial fallacy-y, but it's not really about monads.

it's about the applicative hierarchy! this is a set of three typeclasses: Functor, Applicative, and Monad, in that order. each of these typeclasses has a lifting function, and all but Functor have a unit function.

(the unit function is a -> f a, so just something that takes an existing value and places it inside the functor. it's called pure in Applicative and return in Monad. specific Functors will generally have ways to put values inside them, of course -- List has : and Maybe has Just, for example -- but they're not considered essential to the typeclass as they are in Applicative or Monad. this is i think a quirk of haskell's history, and not really anything reflective of underlying category-theory gibberish.)

• Functor's lifting function is Functor f => (a -> b) -> f a -> f b and is called fmap
• Applicative's lifting function is Applicative f => f (a -> b) -> f a -> f b and is called <*> or ap
• Monad's lifting function is Monad f => (a -> f b) -> f a -> f b and is called =<< or bind

the big takeaway here is that you can (and should) think of these as variations on a theme: assuming you want a function f a -> f b, each one takes one function of varying power and turns it into a function across values of your functor.

it is like you are saying "hey, i want a f a -> f b function, but i don't really want to write all that context-handling code myself. isn't there an easier way?" and it turns out that there can be, if you don't actually care that much about the context!

the reason why this is a "hierarchy" rather than just being three typeclasses each doing a similar thing is that each of these classes is strictly more powerful than the ones that come before it, in a very precise sense: using each class's lifting function, you can recreate the lifting functions of the lower classes.

• fmap can be said in Applicative as (<*>) . pure
• <*> can be said in Monad as \mf mv -> (\f -> (\v -> return $ f v) =<< mv) =<< mf (there are more concise, less readable ways to put that)

---

practical applications:

• like it says, fmap only cares about the values in the functor, not the context itself. if you just want to change the values inside the functor, this is the lifting function to use. since this doesn't alter the functor context, there's generally a pretty clear correspondance between values before and after the function application (the values in a list will remain in the same order, for example)
• <*> is useful when you have a function that, itself, is inside a functor context. what this does is uses the functor context to inform the functor context and the value context to inform the values -- there's no crosstalk allowed: if you have Maybe a and Maybe (a -> b), the functor context depends entirely on whether they're both Just, and not at all on the actual values. and the values depend entirely on the function, and not at all on the functor context. having a function inside a context might not seem like a common occurance, but the big use is multi-argument functions. fmap is all well and good when you have a one argument function of the form a -> b, but if you try to fmap something with a type signature of a -> b -> c things get messy. you end up with something like f (b -> c), which is basically useless in Functor. except then <*> comes along and lets you transform that into a function f b -> f c, which is wayyy more useful. this works indefinitely, for as many arguments as you want -- fmap works on 1-argument functions, but fmap plus <*> works on n-argument functions. (fmap with an Applicative constraint is called <$>, and you usually see it in places like (*) <$> [1,2,3] <*> [4,5,6], or to construct a type with a constructor when your values are all inside some Applicative)
• =<< is useful when you care a little about the output functor context. maybe you're looking up values from a table, so you might want to have a Maybe a value on output. maybe you're splitting things into lists, so you want to have a [a] value on output. and then it turns out you're also using Maybe or [] values on input! using fmap would get you something like Maybe (Maybe a)) or [[a]], and you don't care about that extra layer of depth. On lists, =<< is a lot like \f -> concat . fmap f

---

some examples:

> fmap (* 2) [1..10]
[2,4,6,8,10,12,14,16,18,20]

the input and output lists are the same length: fmap is incapable of changing "functor context", which here means "list length".

> [(* 2), (+ 1)] <*> [1..10]
[2,4,6,8,10,12,14,16,18,20,2,3,4,5,6,7,8,9,10,11]

and here we see that the Applicative "context" for lists says to treat them like cartesian joins: each list item is applied to each list item in the other list. so we can alter the "functor context" (read: list length) of the result, but only in ways that naturally follow from the functor context of the arguments. in this case, 2 items * 10 items = 20 items.

> (\x -> replicate x x) =<< [1..10]
[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10]

and here, since we're creating a new "functor context", we can make the resulting list any length we want.

---

some minutiae:

• this is why the Functor-Applicative-Monad proposal exists, btw. when haskell came around, first there was Functor, and then there was Monad. it was only later that people realized Applicative was there and was useful, and so we ended up in this situation where instancing something to Monad required a Functor instance, but not an Applicative, despite every Monad also being an Applicative.
• i've been lying about bind: in haskell, bind is >>=, which has the arguments the other way around (so, f a -> (a -> f b) -> f b); i feel like this obscures the actual properties of the bind operation and so for that and other reasons i tend to use =<< instead. in practice, =<< composes "backwards", in that you have to read it from right-to-left to figure out how a value is transformed. to me, that's fine -- that's also the way function composition works, and it's better to always read right-to-left than to switch back and forth depending on whether you're using monads or not. but the do-notation uses >>= because it gets a left-to-right, top-to-bottom reading, and a lot of people use >>= generally for the same reason.
• each typeclass has renamed versions of the lower functions, just with different constraints. i already mentioned Applicative's version of fmap, <$>. Monad has liftM for fmap and ap for <*>. generally it's considered good practice to use whichever version carries the least constraints. if you only need to fmap something, it's preferred to just use fmap instead of liftM, unless you're already working under a Monad f => constraint
• everyone talks a lot about the IO monad, because that's the monad that gets the most use, and is the one everyone has to deal with first. IO is deeply magical for reasons i'm not going to get into, and that most 'monad tutorials' cover. Monad is just a typeclass, like any other typeclass, and it can be understood generally. in general one can only operate on a monadic value inside monadic code, but a lot of the time you can do things like pattern-match on a constructor, or use functions like fromMaybe to pull "monadic" values out into the rest of your code to, in essence, get a m a -> a function. this is fine. but not all monads let you do it; this depends less on "monads" and more on the specific type you're using (that happens to have a Monad instance)