Thursday, November 14, 2013

Monads for the Slothful

What up Stranded in Halligan?  So, I haven’t posted on this blog years, but today I figured I might do something a little different from C++.  This tutorial is on the notorious concept of monads that makes Haskell so hard to learn.  I’m still pretty new to monads myself, but once I grasped the concept, I realized something.  Monads may look like a concept that you need to work hard at to understand, but really, monads are something you can understand even if you are more slothy.  And this tutorial demonstrates that if you know about sloths, it’s easy to get a sloth-clawed grasp of the concept of monads.

Now, if you came here looking for a monad tutorial, chances are you are learning them to use in Haskell or some other functional programming language, so I will be putting snippets of Haskell code in the tutorial, but if you don’t know Haskell, no worries.  The Haskell code I am writing is very intuitive, and I wrote the code to look like English.

With that being said, let the slothing begin!

Sloths have a lot of fur, and inside that fur is an ecosystem of its own.  Sloths can have organisms such as algae or sloth moths in their fur.

data OrganismInFur = Algae | SlothMoths

But if a sloth just took a bath, then the algae won’t grow on the sloth because the algae think hibiscus-scented shampoo smells gross.  And since there’s no algae on the sloth, no sloth moths will land in the sloth’s fur.  So a sloth can either be a clean sloth or a sloth with something on its fur.

data Sloth something = CleanSloth | SlothWith something

If sloth moths see a sloth full of algae, then they fly in and eat the algae.  If sloth moths leave the sloth to go find another sloth that has algae to chow down on, then the algae grows back.  This can be described with the `evicts` function

evicts :: OrganismInFur -> OrganismInFur -> OrganismInFur

Algae `evicts` SlothMoths = Algae

SlothMoths `evicts` Algae = SlothMoths

So algae can evict sloth moths and sloth moths can evict algae.  But the sloth moths and algae evicting each other only tells us who is leaving the fur and who is moving in.  So you can say that sloth moths evict algae, but we never mentioned that they are on a sloth’s fur, so we just have a bunch of sloth moths flying around the rainforest.  You can’t say that the sloth moths are evicting a sloth with algae because then the sloth moths are evicting the sloth from itself.  So SlothMoths `evicts` SlothWith Algae causes a type error because SlothWith Algae has a type “Sloth OrganismInFur” rather than just “OrganismInFur”

What we want to talk about is sloth moths that find a sloth with algae, evict the algae, and go into the sloth’s fur, and the end result is that there is a sloth with sloth moths.  Either that, or algae find a clean sloth, get grossed out by the smell of shampoo, and then leave with the sloth still clean.  In both cases, we start with a sloth, something goes on in the ecosystem of its fur, and we end with a sloth.  To be able to talk about this, this is where monads come in.

If a flock of sloth moths goes into the rainforest, finds a sloth, and climbs into the sloth’s fur, then what returns from a long day of slowly climbing trees is a sloth with sloth moths in its fur, which is described with the function “return“.

return something = SlothWith something

ex. return SlothMoths = SlothWith SlothMoths

If the sloth moths go into the rainforest, find a sloth with algae in its fur, end then evict them from the fur, then now we have a sloth with sloth moths in its fur.  This is described with the function “nowWeHave”, which takes in two organisms and gives us a sloth with the first organism in its fur.

nowWeHave :: OrganismInFur -> OrganismInFur -> SlothWith OrganismInFur

nowWeHave organism1 organism2 = return (organism1 `evicts` organism2)

ex. nowWeHave SlothMoths Algae = return SlothMoths `evicts` Algae

                               = return SlothMoths

                               = SlothWith SlothMoths

So when the sloth moths find the sloth, evict the algae, and enter the sloth’s fur, we start with a sloth and we end with a sloth.  This relation is described with the bind function, with the cool but intimidating operator >>=.  If this this function gets to be a tough branch to climb, just reach your claws over to the example and follow along and it will be smooth slothing from there.

SlothWith something >>= function = function something

ex. SlothWith Algae >>= nowWeHave SlothMoths =

                            nowWeHave SlothMoths Algae

                          = return (SlothMoths `evicts` Algae)

                          = return SlothMoths

                          = SlothWith SlothMoths

So, in the first line of the example, we see a SlothWith Algae on the left side of the >>=, which is the sloth we started with.  What we have on the right is nowWeHave SlothMoths, which is the nowWeHave function that took in one argument and needs one more argument.

In the second line, nowWeHave takes in the Algae from the sloth, and the function nowWeHave is applied.  The end result, nowWeHave SlothMoths Algae gives us a SlothWith SlothMoths, so the end result is a sloth with sloth moths in its fur.

But if the sloth moths find a clean sloth, they don’t evict any algae and they have no reason to get into the sloth’s fur because there’s no algae to eat, so they leave the sloth alone and what we have is a clean sloth.  Once again, we start with a sloth and we end with a sloth.

CleanSloth >>= function = CleanSloth

ex. CleanSloth >>= nowWeHave SlothMoths = CleanSloth

So on the left of the >>= we have a clean sloth and on the right we have the function nowWeHave SlothMoths awaiting one more argument.  But instead of taking in another argument, the function is simply ignored and we get back a clean sloth.  So the sloth threw away that function like it throws away the pile of leaves it was eating before it saw some hibiscus flowers to eat.

Now, here’s the interesting thing about this.  You know how when we call >>= we start with a sloth and we end with a sloth?  Well, what that means is that the sloth we get back can be used in another >>= and we will still end with a sloth.  For example,

  SlothWith Algae >>= nowWeHave SlothMoths >>= nowWeHave Algae

= (SlothWith Algae >>= nowWeHave SlothMoths) >>= nowWeHave Algae

= SlothWith SlothMoths >>= nowWeHave Algae

= SlothWith Algae

So we can chain together >>=’s to make a sequence of events take place.  And a sequence of events sounds an awful lot like the way we do programming in languages like C, Java, and Python.  And that makes monads incredibly useful.  If you are a Haskell programmer, your first encounter with monads was probably when you were learning how to do more than one IO statement in a program in a purely functional language, and ultimately IO statements are themselves a kind of monad.  So monads make it possible to do a lot of real-world applications of Haskell, and they make it possible for you to be the classy math nerd at parties (note that the >>= operator turned sideways looks kinda like a funky wine glass.  That’s because monads are that classy)!

Now, for one more example, this doesn’t show much about the concept of monads but more the polymorphism of the >>= operator.  Though really I am just adding this example because baby sloths are so adorable!

So, the data type for a Sloth was Sloth a, so the a means that the sloth can have something of any data type on its fur.  So a sloth can have a baby sloth on its fur, as we are about to see.  Also, the type signature for the monadic >>= function is

>>= :: m a -> (a -> m b) -> m b

In other words the function that a monad can take in can replace what was originally on the monad with something of a different type, so while the nowWeHave function replaces an OrganismInFur with another OrganismInFur, another function, babySloth, replaces an OrganismInFur with a Sloth.

babySloth :: Sloth a -> b -> Sloth (Sloth a)

babySloth CleanSloth _            = return CleanSloth

babySloth (SlothWith something) _ = return (SlothWith something)

So, here’s a sequence of >>=’s to demonstrate that

SlothWith Algae >>= nowWeHave SlothMoths >>= nowWeHave Algae >>=

                    babySloth (SlothWith Algae)

So, what do we get here?  Well, we know that from the two nowWeHave’s, the result is that we start with a mother sloth with algae, she sloths a few feet up the tree and some sloth moths eat the algae, then she goes up the tree to go eat some leaves, and the sloth moths leave her fur so new algae grow, and then she goes over to sloth preschool to pick up her baby after a long day of learning how to sloth around the forest in search of tasty leaves and hibiscus flowers.  So now we have:

SlothWith Algae >>= babySloth (SlothWith Algae)

Which gives us:

babySloth (SlothWith Algae) Algae

Which gives us:

return (SlothWith Algae)

Which ultimately gives us the result

SlothWith (SlothWith Algae)

Which is a mother sloth with a baby sloth on her back.

If you understand all that, congratulations, you just took your first step into the world of monads!  To celebrate, go brew yourself a cup of hibiscus tea!  We’ve just scratched the surface of monads with our sloth claws, but from my experience, once you understand the material in this tutorial, the rest makes a lot of sense, so sloth on down to all the other great monad tutorials online.

I’d like to thank Learn You A Haskell for being the tutorial that ultimately helped me figure out monads and the Aviarios Del Caribe Sloth Sanctuary in Costa Rica for showing the world how adorable baby sloths are and ultimately being the inspiration for this tutorial!