notebooks/12-a-fistful-of-monads.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A Fistful of Monads\n",
    "===================\n",
    "\n",
    "When we first talked about functors, we saw that they were a useful\n",
    "concept for values that can be mapped over. Then, we took that concept\n",
    "one step further by introducing applicative functors, which allow us to\n",
    "view values of certain data types as values with contexts and use normal\n",
    "functions on those values while preserving the meaning of those\n",
    "contexts."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __Jupyter Note:__ We'll turn off the [automatic linting for IHaskell](https://github.com/gibiansky/IHaskell/wiki#opt-no-lint) first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    ":opt no-lint"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this chapter, we'll learn about monads, which are just beefed up\n",
    "applicative functors, much like applicative functors are only beefed up\n",
    "functors."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/smugpig.png\" title=\"more cool than u\" style=\"float:right;margin-left:2em;\" />\n",
    "\n",
    "When we started off with functors, we saw that it's possible to map\n",
    "functions over various data types. We saw that for this purpose, the\n",
    "[`Functor`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Functor) type class was introduced and it had us asking the question:\n",
    "when we have a function of type `a -> b` and some data type `f a`, how do\n",
    "we map that function over the data type to end up with `f b`? We saw how\n",
    "to map something over a `Maybe a`, a list `[a]`, an `IO a` etc. We even saw\n",
    "how to map a function `a -> b` over other functions of type `r -> a` to\n",
    "get functions of type `r -> b`. To answer this question of how to map a\n",
    "function over some data type, all we had to do was look at the type of\n",
    "[`fmap`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:fmap):"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "fmap :: (Functor f) => (a -> b) -> f a -> f b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And then make it work for our data type by writing the appropriate\n",
    "[`Functor`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Functor) instance.\n",
    "\n",
    "Then we saw a possible improvement of functors and said, hey, what if\n",
    "that function `a -> b` is already wrapped inside a functor value? Like,\n",
    "what if we have `Just (*3)`, how do we apply that to `Just 5`? What if we\n",
    "don't want to apply it to `Just 5` but to a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) instead? Or if we have\n",
    "`[(*2),(+4)]`, how would we apply that to `[1,2,3]`? How would that work\n",
    "even? For this, the [`Applicative`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Applicative) type class was introduced, in which we\n",
    "wanted the answer to the following type:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also saw that we can take a normal value and wrap it inside a data\n",
    "type. For instance, we can take a `1` and wrap it so that it becomes a\n",
    "`Just 1`. Or we can make it into a `[1]`. Or an I/O action that does nothing\n",
    "and just yields `1`. The function that does this is called [`pure`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:pure).\n",
    "\n",
    "Like we said, an applicative value can be seen as a value with an added\n",
    "context. A *fancy* value, to put it in technical terms. For instance,\n",
    "the character `'a'` is just a normal character, whereas `Just 'a'` has some\n",
    "added context. Instead of a [`Char`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Char), we have a `Maybe Char`, which tells us\n",
    "that its value might be a character, but it could also be an absence of\n",
    "a character.\n",
    "\n",
    "It was neat to see how the [`Applicative`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Applicative) type class allowed us to use\n",
    "normal functions on these values with context and how that context was\n",
    "preserved. Observe:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just 16"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(*) <$> Just 2 <*> Just 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(++) <$> Just \"klingon\" <*> Nothing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,1,0,3,2,1]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(-) <$> [3,4] <*> [1,2,3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ah, cool, so now that we treat them as applicative values, `Maybe a`\n",
    "values represent computations that might have failed, `[a]` values\n",
    "represent computations that have several results (non-deterministic\n",
    "computations), `IO a` values represent values that have side-effects, etc.\n",
    "\n",
    "Monads are a natural extension of applicative functors and with them\n",
    "we're concerned with this: if you have a value with a context, `m a`, how\n",
    "do you apply to it a function that takes a normal `a` and returns a value\n",
    "with a context? That is, how do you apply a function of type `a -> m b`\n",
    "to a value of type `m a`? So essentially, we will want this function:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "(>>=) :: (Monad m) => m a -> (a -> m b) -> m b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**If we have a fancy value and a function that takes a normal value but\n",
    "returns a fancy value, how do we feed that fancy value into the\n",
    "function?** This is the main question that we will concern ourselves\n",
    "when dealing with monads. We write `m a` instead of `f a` because the `m`\n",
    "stands for [`Monad`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Monad), but monads are just applicative functors that support\n",
    "[`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-). The [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) function is pronounced as *bind*.\n",
    "\n",
    "When we have `a` normal value a and a normal function `a -> b` it's really\n",
    "easy to feed the value to the function — you just apply the function to\n",
    "the value normally and that's it. But when we're dealing with values\n",
    "that come with certain contexts, it takes a bit of thinking to see how\n",
    "these fancy values are fed to functions and how to take into account\n",
    "their behavior, but you'll see that it's easy as one two three.\n",
    "\n",
    "Getting our feet wet with Maybe\n",
    "-------------------------------\n",
    "\n",
    "<img src=\"img/buddha.png\" title=\"monads, grasshoppa\" style=\"float:left;margin-right:2em;\" />\n",
    "\n",
    "Now that we have a vague idea of what monads are about, let's see if we\n",
    "can make that idea a bit less vague.\n",
    "\n",
    "Much to no one's surprise, [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) is a monad, so let's explore it a bit\n",
    "more and see if we can combine it with what we know about monads.\n",
    "\n",
    "> Make sure you understand\n",
    "> [applicatives](http:https://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functors)\n",
    "> at this point. It's good if you have a feel for how the various\n",
    "> [`Applicative`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Applicative) instances work and what kind of computations they represent,\n",
    "> because monads are nothing more than taking our existing applicative\n",
    "> knowledge and upgrading it.\n",
    "\n",
    "A value of type `Maybe a` represents a value of type `a` with the context of\n",
    "possible failure attached. A value of `Just \"dharma\"` means that the\n",
    "string `\"dharma\"` is there whereas a value of [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) represents its\n",
    "absence, or if you look at the string as the result of a computation, it\n",
    "means that the computation has failed.\n",
    "\n",
    "When we looked at [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) as a functor, we saw that if we want to [`fmap`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:fmap) a\n",
    "function over it, it gets mapped over the insides if it's a [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just) value,\n",
    "otherwise the [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) is kept because there's nothing to map it over!\n",
    "\n",
    "Like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just \"wisdom!\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fmap (++\"!\") (Just \"wisdom\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fmap (++\"!\") Nothing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As an applicative functor, it functions similarly. However, applicatives\n",
    "also have the function wrapped. [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) is an applicative functor in such\n",
    "a way that when we use [`<*>`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-60--42--62-) to apply a function inside a [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) to a\n",
    "value that's inside a [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe), they both have to be [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just) values for the\n",
    "result to be a [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just) value, otherwise the result is [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing). It makes\n",
    "sense because if you're missing either the function or the thing you're\n",
    "applying it to, you can't make something up out of thin air, so you have\n",
    "to propagate the failure:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just 6"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Just (+3) <*> Just 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Nothing <*> Just \"greed\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "import Data.Char"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Just ord <*> Nothing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we use the applicative style to have normal functions act on [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe)\n",
    "values, it's similar. All the values have to be [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just) values, otherwise\n",
    "it's all for [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing)!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just 6"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "max <$> Just 3 <*> Just 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "max <$> Just 3 <*> Nothing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And now, let's think about how we would do [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) for [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe). Like we\n",
    "said, [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) takes a monadic value, and a function that takes a normal\n",
    "value and returns a monadic value and manages to apply that function to\n",
    "the monadic value. How does it do that, if the function takes a normal\n",
    "value? Well, to do that, it has to take into account the context of that\n",
    "monadic value.\n",
    "\n",
    "In this case, [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) would take a `Maybe a` value and a function of type\n",
    "`a -> Maybe b` and somehow apply the function to the `Maybe a`. To figure out\n",
    "how it does that, we can use the intuition that we have from [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) being\n",
    "an applicative functor. Let's say that we have a function `\\x -> Just (x+1)`.\n",
    "It takes a number, adds `1` to it and wraps it in a [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just 2"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(\\x -> Just (x+1)) 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just 101"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(\\x -> Just (x+1)) 100"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we feed it `1`, it evaluates to `Just 2`. If we give it the number `100`,\n",
    "the result is `Just 101`. Very straightforward. Now here's the kicker: how\n",
    "do we feed a [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) value to this function? If we think about how [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe)\n",
    "acts as an applicative functor, answering this is pretty easy. If we\n",
    "feed it a [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just) value, take what's inside the [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just) and apply the function\n",
    "to it. If give it a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing), hmm, well, then we're left with a function\n",
    "but [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) to apply it to. In that case, let's just do what we did\n",
    "before and say that the result is [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing).\n",
    "\n",
    "Instead of calling it [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-), let's call it `applyMaybe` for now. It takes\n",
    "a `Maybe a` and a function that returns a `Maybe b` and manages to apply\n",
    "that function to the `Maybe a`. Here it is in code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "applyMaybe :: Maybe a -> (a -> Maybe b) -> Maybe b\n",
    "applyMaybe Nothing f  = Nothing\n",
    "applyMaybe (Just x) f = f x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Okay, now let's play with it for a bit. We'll use it as an infix\n",
    "function so that the [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) value is on the left side and the function on\n",
    "the right:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just 4"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Just 3 `applyMaybe` \\x -> Just (x+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just \"smile :)\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Just \"smile\" `applyMaybe` \\x -> Just (x ++ \" :)\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Nothing `applyMaybe` \\x -> Just (x+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Nothing `applyMaybe` \\x -> Just (x ++ \" :)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the above example, we see that when we used `applyMaybe` with a [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just)\n",
    "value and a function, the function simply got applied to the value\n",
    "inside the [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just). When we tried to use it with a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing), the whole\n",
    "result was [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing). What about if the function returns a Nothing? Let's\n",
    "see:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just 3"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Just 3 `applyMaybe` \\x -> if x > 2 then Just x else Nothing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Just 1 `applyMaybe` \\x -> if x > 2 then Just x else Nothing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just what we expected. If the monadic value on the left is a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing),\n",
    "the whole thing is [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing). And if the function on the right returns a\n",
    "[`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing), the result is [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) again. This is very similar to when we\n",
    "used [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) as an applicative and we got a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) result if somewhere in\n",
    "there was a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing).\n",
    "\n",
    "It looks like that for [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe), we've figured out how to take a fancy\n",
    "value and feed it to a function that takes a normal value and returns a\n",
    "fancy one. We did this by keeping in mind that a [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) value represents\n",
    "a computation that might have failed.\n",
    "\n",
    "You might be asking yourself, how is this useful? It may seem like\n",
    "applicative functors are stronger than monads, since applicative\n",
    "functors allow us to take a normal function and make it operate on\n",
    "values with contexts. We'll see that monads can do that as well because\n",
    "they're an upgrade of applicative functors, and that they can also do\n",
    "some cool stuff that applicative functors can't.\n",
    "\n",
    "We'll come back to [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) in a minute, but first, let's check out the\n",
    "type class that belongs to monads.\n",
    "\n",
    "The Monad type class\n",
    "--------------------\n",
    "\n",
    "Just like functors have the [`Functor`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Functor) type class and applicative functors\n",
    "have the [`Applicative`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Applicative) type class, monads come with their own type class:\n",
    "[`Monad`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Monad)! Wow, who would have thought? This is what the type class looks\n",
    "like:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "class Monad m where\n",
    "    return :: a -> m a\n",
    "\n",
    "    (>>=) :: m a -> (a -> m b) -> m b\n",
    "\n",
    "    (>>) :: m a -> m b -> m b\n",
    "    x >> y = x >>= \\_ -> y\n",
    "\n",
    "    fail :: String -> m a\n",
    "    fail msg = error msg"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/kid.png\" title=\"this is you on monads\" style=\"float:right;margin-left:2em;\" />\n",
    "\n",
    "Let's start with the first line. It says `class Monad m where`. But wait,\n",
    "didn't we say that monads are just beefed up applicative functors?\n",
    "Shouldn't there be a class constraint in there along the lines of\n",
    "`class (Applicative m) => Monad m where` so that a type has to be an\n",
    "applicative functor first before it can be made a monad? Well, there\n",
    "should, but when Haskell was made, it hadn't occurred to people that\n",
    "applicative functors are a good fit for Haskell so they weren't in\n",
    "there. But rest assured, every monad is an applicative functor, even if\n",
    "the [`Monad`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Monad) class declaration doesn't say so.\n",
    "\n",
    "The first function that the [`Monad`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Monad) type class defines is [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return). It's the\n",
    "same as [`pure`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:pure), only with a different name. Its type is\n",
    "`(Monad m) => a -> m a`. It takes a value and puts it in a minimal default context that\n",
    "still holds that value. In other words, it takes something and wraps it\n",
    "in a monad. It always does the same thing as the [`pure`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:pure) function from the\n",
    "[`Applicative`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Applicative) type class, which means we're already acquainted with\n",
    "[`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return). We already used [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) when doing I/O. We used it to take a\n",
    "value and make a bogus I/O action that does nothing but yield that\n",
    "value. For [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) it takes a value and wraps it in a [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just).\n",
    "\n",
    "> Just a reminder: [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) is nothing like the [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) that's in most other\n",
    "> languages. It doesn't end function execution or anything, it just takes\n",
    "> a normal value and puts it in a context.\n",
    "\n",
    "<img src=\"img/tur2.png\" title=\"hmmm yaes\" style=\"float:left;margin-right:2em;\" />\n",
    "\n",
    "The next function is [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-), or bind. It's like function application,\n",
    "only instead of taking a normal value and feeding it to a normal\n",
    "function, it takes a monadic value (that is, a value with a context) and\n",
    "feeds it to a function that takes a normal value but returns a monadic\n",
    "value.\n",
    "\n",
    "Next up, we have [`>>`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62-). We won't pay too much attention to it for now\n",
    "because it comes with a default implementation and we pretty much never\n",
    "implement it when making [`Monad`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Monad) instances.\n",
    "\n",
    "The final function of the [`Monad`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Monad) type class is [`fail`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:fail). We never use it\n",
    "explicitly in our code. Instead, it's used by Haskell to enable failure\n",
    "in a special syntactic construct for monads that we'll meet later. We\n",
    "don't need to concern ourselves with [`fail`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:fail) too much for now.\n",
    "\n",
    "Now that we know what the [`Monad`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Monad) type class looks like, let's take a look\n",
    "at how [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) is an instance of [`Monad`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Monad)!"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "instance Monad Maybe where\n",
    "    return x = Just x\n",
    "    Nothing >>= f = Nothing\n",
    "    Just x >>= f  = f x\n",
    "    fail _ = Nothing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) is the same as [`pure`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:pure), so that one's a no-brainer. We do what we\n",
    "did in the [`Applicative`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Applicative) type class and wrap it in a [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just).\n",
    "\n",
    "The [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) function is the same as our `applyMaybe`. When feeding the\n",
    "`Maybe a` to our function, we keep in mind the context and return a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) if\n",
    "the value on the left is [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) because if there's no value then\n",
    "there's no way to apply our function to it. If it's a [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just) we take\n",
    "what's inside and apply `f` to it.\n",
    "\n",
    "We can play around with [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) as a monad:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just \"WHAT\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "return \"WHAT\" :: Maybe String"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just 90"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Just 9 >>= \\x -> return (x*10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Nothing >>= \\x -> return (x*10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nothing new or exciting on the first line since we already used [`pure`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:pure)\n",
    "with [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) and we know that [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) is just [`pure`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:pure) with a different name.\n",
    "The next two lines showcase [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) a bit more.\n",
    "\n",
    "Notice how when we fed `Just 9` to the function `\\x -> return (x*10)`,\n",
    "the `x` took on the value `9` inside the function. It seems as though we\n",
    "were able to extract the value from a [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) without pattern-matching.\n",
    "And we still didn't lose the context of our [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) value, because when\n",
    "it's [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing), the result of using [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) will be [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) as well.\n",
    "\n",
    "<a name=\"walk-the-line\"></a>\n",
    "\n",
    "Walk the line\n",
    "-------------\n",
    "\n",
    "<img src=\"img/pierre.png\" title=\"pierre\" style=\"float:left;margin-right:2em;\" />\n",
    "\n",
    "Now that we know how to feed a `Maybe a` value to a function of type\n",
    "`a -> Maybe b` while taking into account the context of possible failure, let's\n",
    "see how we can use [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) repeatedly to handle computations of several\n",
    "`Maybe a` values.\n",
    "\n",
    "Pierre has decided to take a break from his job at the fish farm and try\n",
    "tightrope walking. He's not that bad at it, but he does have one\n",
    "problem: birds keep landing on his balancing pole! They come and they\n",
    "take a short rest, chat with their avian friends and then take off in\n",
    "search of breadcrumbs. This wouldn't bother him so much if the number of\n",
    "birds on the left side of the pole was always equal to the number of\n",
    "birds on the right side. But sometimes, all the birds decide that they\n",
    "like one side better and so they throw him off balance, which results in\n",
    "an embarrassing tumble for Pierre (he's using a safety net).\n",
    "\n",
    "Let's say that he keeps his balance if the number of birds on the left\n",
    "side of the pole and on the right side of the pole is within three. So\n",
    "if there's one bird on the right side and four birds on the left side,\n",
    "he's okay. But if a fifth bird lands on the left side, then he loses his\n",
    "balance and takes a dive.\n",
    "\n",
    "We're going to simulate birds landing on and flying away from the pole\n",
    "and see if Pierre is still at it after a certain number of birdy\n",
    "arrivals and departures. For instance, we want to see what happens to\n",
    "Pierre if first one bird arrives on the left side, then four birds\n",
    "occupy the right side and then the bird that was on the left side\n",
    "decides to fly away.\n",
    "\n",
    "We can represent the pole with a simple pair of integers. The first\n",
    "component will signify the number of birds on the left side and the\n",
    "second component the number of birds on the right side:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "type Birds = Int\n",
    "type Pole = (Birds,Birds)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First we made a type synonym for [`Int`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Int), called `Birds`, because we're using\n",
    "integers to represent how many birds there are. And then we made a type\n",
    "synonym `(Birds,Birds)` and we called it `Pole` (not to be confused with a\n",
    "person of Polish descent).\n",
    "\n",
    "Next up, how about we make a function that takes a number of birds and\n",
    "lands them on one side of the pole. Here are the functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "landLeft :: Birds -> Pole -> Pole\n",
    "landLeft n (left,right) = (left + n,right)\n",
    "\n",
    "landRight :: Birds -> Pole -> Pole\n",
    "landRight n (left,right) = (left,right + n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pretty straightforward stuff. Let's try them out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2,0)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "landLeft 2 (0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1,3)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "landRight 1 (1,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1,1)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "landRight (-1) (1,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To make birds fly away we just had a negative number of birds land on\n",
    "one side. Because landing a bird on the `Pole` returns a `Pole`, we can\n",
    "chain applications of `landLeft` and `landRight`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3,1)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "landLeft 2 (landRight 1 (landLeft 1 (0,0)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we apply the function `landLeft 1` to `(0,0)` we get `(1,0)`. Then, we\n",
    "land a bird on the right side, resulting in `(1,1)`. Finally two birds\n",
    "land on the left side, resulting in `(3,1)`. We apply a function to\n",
    "something by first writing the function and then writing its parameter,\n",
    "but here it would be better if the pole went first and then the landing\n",
    "function. If we make a function like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "x -: f = f x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can apply functions by first writing the parameter and then the\n",
    "function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "300"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "100 -: (*3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "True -: not"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2,0)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(0,0) -: landLeft 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By using this, we can repeatedly land birds on the pole in a more\n",
    "readable manner:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3,1)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(0,0) -: landLeft 1 -: landRight 1 -: landLeft 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pretty cool! This example is equivalent to the one before where we\n",
    "repeatedly landed birds on the pole, only it looks neater. Here, it's\n",
    "more obvious that we start off with `(0,0)` and then land one bird one the\n",
    "left, then one on the right and finally two on the left.\n",
    "\n",
    "So far so good, but what happens if 10 birds land on one side?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10,3)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "landLeft 10 (0,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "10 birds on the left side and only 3 on the right? That's sure to send\n",
    "poor Pierre falling through the air! This is pretty obvious here but\n",
    "what if we had a sequence of landings like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0,2)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(0,0) -: landLeft 1 -: landRight 4 -: landLeft (-1) -: landRight (-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It might seem like everything is okay but if you follow the steps here,\n",
    "you'll see that at one time there are 4 birds on the right side and no\n",
    "birds on the left! To fix this, we have to take another look at our\n",
    "`landLeft` and `landRight` functions. From what we've seen, we want these\n",
    "functions to be able to fail. That is, we want them to return a new pole\n",
    "if the balance is okay but fail if the birds land in a lopsided manner.\n",
    "And what better way to add a context of failure to value than by using\n",
    "[`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe)! Let's rework these functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "landLeft :: Birds -> Pole -> Maybe Pole\n",
    "landLeft n (left,right)\n",
    "    | abs ((left + n) - right) < 4 = Just (left + n, right)\n",
    "    | otherwise                    = Nothing\n",
    "\n",
    "landRight :: Birds -> Pole -> Maybe Pole\n",
    "landRight n (left,right)\n",
    "    | abs (left - (right + n)) < 4 = Just (left, right + n)\n",
    "    | otherwise                    = Nothing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead of returning a `Pole` these functions now return a `Maybe Pole`.\n",
    "They still take the number of birds and the old pole as before, but then\n",
    "they check if landing that many birds on the pole would throw Pierre off\n",
    "balance. We use guards to check if the difference between the number of\n",
    "birds on the new pole is less than 4. If it is, we wrap the new pole in\n",
    "a [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just) and return that. If it isn't, we return a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing), indicating\n",
    "failure.\n",
    "\n",
    "Let's give these babies a go:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just (2,0)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "landLeft 2 (0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "landLeft 10 (0,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nice! When we land birds without throwing Pierre off balance, we get a\n",
    "new pole wrapped in a [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just). But when many more birds end up on one side\n",
    "of the pole, we get a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing). This is cool, but we seem to have lost\n",
    "the ability to repeatedly land birds on the pole. We can't do\n",
    "`landLeft 1 (landRight 1 (0,0))` anymore because when we apply `landRight 1` to `(0,0)`,\n",
    "we don't get a `Pole`, but a `Maybe Pole`. `landLeft 1` takes a `Pole` and not a\n",
    "`Maybe Pole`.\n",
    "\n",
    "We need a way of taking a `Maybe Pole` and feeding it to a function that\n",
    "takes a `Pole` and returns a `Maybe Pole`. Luckily, we have [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-), which\n",
    "does just that for [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe). Let's give it a go:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just (2,1)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "landRight 1 (0,0) >>= landLeft 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remember, `landLeft 2` has a type of `Pole -> Maybe Pole`. We couldn't just\n",
    "feed it the `Maybe Pole` that is the result of `landRight 1 (0,0)`, so we\n",
    "use [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) to take that value with a context and give it to `landLeft 2`.\n",
    "[`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) does indeed allow us to treat the [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) value as a value with\n",
    "context because if we feed a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) into `landLeft 2`, the result is\n",
    "[`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) and the failure is propagated:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Nothing >>= landLeft 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With this, we can now chain landings that may fail because [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) allows\n",
    "us to feed a monadic value to a function that takes a normal one.\n",
    "\n",
    "Here's a sequence of birdy landings:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just (2,4)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "return (0,0) >>= landRight 2 >>= landLeft 2 >>= landRight 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At the beginning, we used [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) to take a pole and wrap it in a [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just).\n",
    "We could have just applied `landRight 2` to `(0,0)`, it would have been the\n",
    "same, but this way we can be more consistent by using [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) for every\n",
    "function. `Just (0,0)` gets fed to `landRight 2`, resulting in `Just (0,2)`.\n",
    "This, in turn, gets fed to `landLeft 2`, resulting in `Just (2,2)`, and so\n",
    "on.\n",
    "\n",
    "Remember this example from before we introduced failure into Pierre's\n",
    "routine:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "(0,0) -: landLeft 1 -: landRight 4 -: landLeft (-1) -: landRight (-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It didn't simulate his interaction with birds very well because in the\n",
    "middle there his balance was off but the result didn't reflect that. But\n",
    "let's give that a go now by using monadic application ([`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-)) instead of\n",
    "normal application:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "return (0,0) >>= landLeft 1 >>= landRight 4 >>= landLeft (-1) >>= landRight (-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/banana.png\" title=\"iama banana\" style=\"float:right;margin-left:2em;\" />\n",
    "\n",
    "Awesome. The final result represents failure, which is what we expected.\n",
    "Let's see how this result was obtained. First, [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) puts `(0,0)` into a\n",
    "default context, making it a `Just (0,0)`. Then, `Just (0,0) >>= landLeft 1`\n",
    "happens. Since the `Just (0,0)` is a [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just) value, `landLeft 1` gets applied\n",
    "to `(0,0)`, resulting in a `Just (1,0)`, because the birds are still\n",
    "relatively balanced. Next, `Just (1,0) >>= landRight 4` takes place and\n",
    "the result is `Just (1,4)` as the balance of the birds is still intact,\n",
    "although just barely. Just (1,4) gets fed to `landLeft (-1)`. This means\n",
    "that `landLeft (-1) (1,4)` takes place. Now because of how `landLeft` works,\n",
    "this results in a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing), because the resulting pole is off balance.\n",
    "Now that we have a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing), it gets fed to `landRight (-2)`, but because\n",
    "it's a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing), the result is automatically [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing), as we have nothing\n",
    "to apply `landRight (-2)` to.\n",
    "\n",
    "We couldn't have achieved this by just using [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) as an applicative. If\n",
    "you try it, you'll get stuck, because applicative functors don't allow\n",
    "for the applicative values to interact with each other very much. They\n",
    "can, at best, be used as parameters to a function by using the\n",
    "applicative style. The applicative operators will fetch their results\n",
    "and feed them to the function in a manner appropriate for each\n",
    "applicative and then put the final applicative value together, but there\n",
    "isn't that much interaction going on between them. Here, however, each\n",
    "step relies on the previous one's result. On every landing, the possible\n",
    "result from the previous one is examined and the pole is checked for\n",
    "balance. This determines whether the landing will succeed or fail.\n",
    "\n",
    "We may also devise a function that ignores the current number of birds\n",
    "on the balancing pole and just makes Pierre slip and fall. We can call\n",
    "it `banana`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "banana :: Pole -> Maybe Pole\n",
    "banana _ = Nothing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can chain it together with our bird landings. It will always\n",
    "cause our walker to fall, because it ignores whatever's passed to it and\n",
    "always returns a failure. Check it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "return (0,0) >>= landLeft 1 >>= banana >>= landRight 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The value `Just (1,0)` gets fed to `banana`, but it produces a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing),\n",
    "which causes everything to result in a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing). How unfortunate!\n",
    "\n",
    "Instead of making functions that ignore their input and just return a\n",
    "predetermined monadic value, we can use the [`>>`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62-) function, whose default\n",
    "implementation is this:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "(>>) :: (Monad m) => m a -> m b -> m b\n",
    "m >> n = m >>= \\_ -> n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Normally, passing some value to a function that ignores its parameter\n",
    "and always just returns some predetermined value would always result in\n",
    "that predetermined value. With monads however, their context and meaning\n",
    "has to be considered as well. Here's how [`>>`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62-) acts with [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Nothing >> Just 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just 4"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Just 3 >> Just 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Just 3 >> Nothing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you replace [`>>`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62-) with `>>= \\_ ->`, it's easy to see why it acts\n",
    "like it does.\n",
    "\n",
    "We can replace our `banana` function in the chain with a [`>>`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62-) and then a\n",
    "[`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "return (0,0) >>= landLeft 1 >> Nothing >>= landRight 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There we go, guaranteed and obvious failure!\n",
    "\n",
    "It's also worth taking a look at what this would look like if we hadn't\n",
    "made the clever choice of treating [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) values as values with a failure\n",
    "context and feeding them to functions like we did. Here's how a series\n",
    "of bird landings would look like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "routine :: Maybe Pole\n",
    "routine = case landLeft 1 (0,0) of\n",
    "    Nothing -> Nothing\n",
    "    Just pole1 -> case landRight 4 pole1 of\n",
    "        Nothing -> Nothing\n",
    "        Just pole2 -> case landLeft 2 pole2 of\n",
    "            Nothing -> Nothing\n",
    "            Just pole3 -> landLeft 1 pole3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/centaur.png\" title=\"john joe glanton\" style=\"float:right;margin-left:2em;\" />\n",
    "\n",
    "We land a bird on the left and then we examine the possibility of\n",
    "failure and the possibility of success. In the case of failure, we\n",
    "return a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing). In the case of success, we land birds on the right and\n",
    "then do the same thing all over again. Converting this monstrosity into\n",
    "a neat chain of monadic applications with [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) is a classic example of\n",
    "how the [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) monad saves us a lot of time when we have to successively\n",
    "do computations that are based on computations that might have failed.\n",
    "\n",
    "Notice how the [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) implementation of [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) features exactly this logic\n",
    "of seeing if a value is [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) and if it is, returning a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) right\n",
    "away and if it isn't, going forward with what's inside the [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just).\n",
    "\n",
    "In this section, we took some functions that we had and saw that they\n",
    "would work better if the values that they returned supported failure. By\n",
    "turning those values into [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) values and replacing normal function\n",
    "application with [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-), we got a mechanism for handling failure pretty\n",
    "much for free, because [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) is supposed to preserve the context of the\n",
    "value to which it applies functions. In this case, the context was that\n",
    "our values were values with failure and so when we applied functions to\n",
    "such values, the possibility of failure was always taken into account.\n",
    "\n",
    "do notation\n",
    "-----------\n",
    "\n",
    "Monads in Haskell are so useful that they got their own special syntax\n",
    "called `do` notation. We've already encountered `do` notation when we were\n",
    "doing I/O and there we said that it was for gluing together several I/O\n",
    "actions into one. Well, as it turns out, `do` notation isn't just for [`IO`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:IO),\n",
    "but can be used for any monad. Its principle is still the same: gluing\n",
    "together monadic values in sequence. We're going to take a look at how\n",
    "`do` notation works and why it's useful.\n",
    "\n",
    "Consider this familiar example of monadic application:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just \"3!\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Just 3 >>= (\\x -> Just (show x ++ \"!\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Been there, done that. Feeding a monadic value to a function that\n",
    "returns one, no big deal. Notice how when we do this, `x` becomes `3` inside\n",
    "the lambda. Once we're inside that lambda, it's just a normal value\n",
    "rather than a monadic value. Now, what if we had another [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) inside\n",
    "that function? Check this out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just \"3!\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Just 3 >>= (\\x -> Just \"!\" >>= (\\y -> Just (show x ++ y)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ah, a nested use of [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-)! In the outermost lambda, we feed `Just \"!\"` to\n",
    "the lambda `\\y -> Just (show x ++ y)`. Inside this lambda, the `y` becomes\n",
    "`\"!\"`. `x` is still `3` because we got it from the outer lambda. All this sort\n",
    "of reminds me of the following expression:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"3!\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "let x = 3; y = \"!\" in show x ++ y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The main difference between these two is that the values in the former\n",
    "example are monadic. They're values with a failure context. We can\n",
    "replace any of them with a failure:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Nothing >>= (\\x -> Just \"!\" >>= (\\y -> Just (show x ++ y)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Just 3 >>= (\\x -> Nothing >>= (\\y -> Just (show x ++ y)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Just 3 >>= (\\x -> Just \"!\" >>= (\\y -> Nothing))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the first line, feeding a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) to a function naturally results in\n",
    "a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing). In the second line, we feed `Just 3` to a function and the `x`\n",
    "becomes `3`, but then we feed a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) to the inner lambda and the result\n",
    "of that is [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing), which causes the outer lambda to produce [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) as\n",
    "well. So this is sort of like assigning values to variables in `let`\n",
    "expressions, only that the values in question are monadic values.\n",
    "\n",
    "To further illustrate this point, let's write this in a script and have\n",
    "each [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) value take up its own line:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "foo :: Maybe String\n",
    "foo = Just 3   >>= (\\x ->\n",
    "      Just \"!\" >>= (\\y ->\n",
    "      Just (show x ++ y)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To save us from writing all these annoying lambdas, Haskell gives us `do`\n",
    "notation. It allows us to write the previous piece of code like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "foo :: Maybe String\n",
    "foo = do\n",
    "    x <- Just 3\n",
    "    y <- Just \"!\"\n",
    "    Just (show x ++ y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/owld.png\" title=\"90s owl\" style=\"float:right;margin-left:2em;\" />\n",
    "\n",
    "It would seem as though we've gained the ability to temporarily extract\n",
    "things from [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) values without having to check if the [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) values are\n",
    "[`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just) values or [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) values at every step. How cool! If any of the\n",
    "values that we try to extract from are [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing), the whole `do` expression\n",
    "will result in a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing). We're yanking out their (possibly existing)\n",
    "values and letting [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) worry about the context that comes with those\n",
    "values. It's important to remember that `do` expressions are just\n",
    "different syntax for chaining monadic values.\n",
    "\n",
    "In a `do` expression, every line is a monadic value. To inspect its\n",
    "result, we use `<-`. If we have a `Maybe String` and we bind it with `<-` to\n",
    "a variable, that variable will be a [`String`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:String), just like when we used [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-)\n",
    "to feed monadic values to lambdas. The last monadic value in a `do`\n",
    "expression, like `Just (show x ++ y)` here, can't be used with `<-` to bind\n",
    "its result, because that wouldn't make sense if we translated the `do`\n",
    "expression back to a chain of [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) applications. Rather, its result is\n",
    "the result of the whole glued up monadic value, taking into account the\n",
    "possible failure of any of the previous ones.\n",
    "\n",
    "For instance, examine the following line:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Just 9 >>= (\\x -> Just (x > 8))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Because the left parameter of [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) is a [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just) value, the lambda is\n",
    "applied to `9` and the result is a `Just True`. If we rewrite this in `do`\n",
    "notation, we get:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "marySue :: Maybe Bool\n",
    "marySue = do\n",
    "    x <- Just 9\n",
    "    Just (x > 8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we compare these two, it's easy to see why the result of the whole\n",
    "monadic value is the result of the last monadic value in the `do`\n",
    "expression with all the previous ones chained into it.\n",
    "\n",
    "Our tightwalker's routine can also be expressed with `do` notation.\n",
    "`landLeft` and `landRight` take a number of birds and a pole and produce a\n",
    "pole wrapped in a [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just), unless the tightwalker slips, in which case a\n",
    "[`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) is produced. We used [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) to chain successive steps because\n",
    "each one relied on the previous one and each one had an added context of\n",
    "possible failure. Here's two birds landing on the left side, then two\n",
    "birds landing on the right and then one bird landing on the left:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "routine :: Maybe Pole\n",
    "routine = do\n",
    "    start <- return (0,0)\n",
    "    first <- landLeft 2 start\n",
    "    second <- landRight 2 first\n",
    "    landLeft 1 second"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see if he succeeds:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just (3,2)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "routine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "He does! Great. When we were doing these routines by explicitly writing\n",
    "[`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-), we usually said something like `return (0,0) >>= landLeft 2`,\n",
    "because `landLeft 2` is a function that returns a [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) value. With `do`\n",
    "expressions however, each line must feature a monadic value. So we\n",
    "explicitly pass the previous `Pole` to the `landLeft` `landRight` functions.\n",
    "If we examined the variables to which we bound our [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) values, `start`\n",
    "would be `(0,0)`, first would be `(2,0)` and so on.\n",
    "\n",
    "Because `do` expressions are written line by line, they may look like\n",
    "imperative code to some people. But the thing is, they're just\n",
    "sequential, as each value in each line relies on the result of the\n",
    "previous ones, along with their contexts (in this case, whether they\n",
    "succeeded or failed).\n",
    "\n",
    "Again, let's take a look at what this piece of code would look like if\n",
    "we hadn't used the monadic aspects of [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "routine :: Maybe Pole\n",
    "routine =\n",
    "    case Just (0,0) of\n",
    "        Nothing -> Nothing\n",
    "        Just start -> case landLeft 2 start of\n",
    "            Nothing -> Nothing\n",
    "            Just first -> case landRight 2 first of\n",
    "                Nothing -> Nothing\n",
    "                Just second -> landLeft 1 second"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "See how in the case of success, the tuple inside `Just (0,0)` becomes\n",
    "`start`, the result of `landLeft 2 start` becomes [`first`](https://hackage.haskell.org/package/base/docs/Control-Arrow.html#v:first), etc.\n",
    "\n",
    "If we want to throw the Pierre a banana peel in `do` notation, we can do\n",
    "the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "routine :: Maybe Pole\n",
    "routine = do\n",
    "    start <- return (0,0)\n",
    "    first <- landLeft 2 start\n",
    "    Nothing\n",
    "    second <- landRight 2 first\n",
    "    landLeft 1 second"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we write a line in `do` notation without binding the monadic value\n",
    "with `<-`, it's just like putting [`>>`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62-) after the monadic value whose\n",
    "result we want to ignore. We sequence the monadic value but we ignore\n",
    "its result because we don't care what it is and it's prettier than\n",
    "writing `_ <- Nothing`, which is equivalent to the above.\n",
    "\n",
    "When to use `do` notation and when to explicitly use [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) is up to you. I\n",
    "think this example lends itself to explicitly writing [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) because each\n",
    "step relies specifically on the result of the previous one. With `do`\n",
    "notation, we had to specifically write on which pole the birds are\n",
    "landing, but every time we used that came directly before. But still, it\n",
    "gave us some insight into `do` notation.\n",
    "\n",
    "In `do` notation, when we bind monadic values to names, we can utilize\n",
    "pattern matching, just like in `let` expressions and function parameters.\n",
    "Here's an example of pattern matching in a `do` expression:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "justH :: Maybe Char\n",
    "justH = do\n",
    "    (x:xs) <- Just \"hello\"\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use pattern matching to get the first character of the string `\"hello\"`\n",
    "and then we present it as the result. So `justH` evaluates to `Just 'h'`.\n",
    "\n",
    "What if this pattern matching were to fail? When matching on a pattern\n",
    "in a function fails, the next pattern is matched. If the matching falls\n",
    "through all the patterns for a given function, an error is thrown and\n",
    "our program crashes. On the other hand, failed pattern matching in `let`\n",
    "expressions results in an error being produced right away, because the\n",
    "mechanism of falling through patterns isn't present in `let` expressions.\n",
    "When pattern matching fails in a `do` expression, the [`fail`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:fail) function is\n",
    "called. It's part of the [`Monad`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Monad) type class and it enables failed pattern\n",
    "matching to result in a failure in the context of the current monad\n",
    "instead of making our program crash. Its default implementation is this:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "fail :: (Monad m) => String -> m a\n",
    "fail msg = error msg"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So by default it does make our program crash, but monads that\n",
    "incorporate a context of possible failure (like [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe)) usually implement\n",
    "it on their own. For [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe), its implemented like so:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "fail _ = Nothing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It ignores the error message and makes a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing). So when pattern\n",
    "matching fails in a [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) value that's written in `do` notation, the whole\n",
    "value results in a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing). This is preferable to having our program\n",
    "crash. Here's a `do` expression with a pattern that's bound to fail:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "wopwop :: Maybe Char\n",
    "wopwop = do\n",
    "    (x:xs) <- Just \"\"\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The pattern matching fails, so the effect is the same as if the whole\n",
    "line with the pattern was replaced with a [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing). Let's try this out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "wopwop"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The failed pattern matching has caused a failure within the context of\n",
    "our monad instead of causing a program-wide failure, which is pretty\n",
    "neat.\n",
    "\n",
    "<a name=\"the-list-monad\"></a>\n",
    "\n",
    "The list monad\n",
    "--------------\n",
    "\n",
    "<img src=\"img/deadcat.png\" title=\"dead cat\" style=\"float:left;margin-right:2em;\" />\n",
    "\n",
    "So far, we've seen how [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) values can be viewed as values with a\n",
    "failure context and how we can incorporate failure handling into our\n",
    "code by using [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) to feed them to functions. In this section, we're\n",
    "going to take a look at how to use the monadic aspects of lists to bring\n",
    "non-determinism into our code in a clear and readable manner.\n",
    "\n",
    "We've already talked about how lists represent non-deterministic values\n",
    "when they're used as applicatives. A value like `5` is deterministic. It\n",
    "has only one result and we know exactly what it is. On the other hand, a\n",
    "value like `[3,8,9]` contains several results, so we can view it as one\n",
    "value that is actually many values at the same time. Using lists as\n",
    "applicative functors showcases this non-determinism nicely:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10,100,1000,20,200,2000,30,300,3000]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(*) <$> [1,2,3] <*> [10,100,1000]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All the possible combinations of multiplying elements from the left list\n",
    "with elements from the right list are included in the resulting list.\n",
    "When dealing with non-determinism, there are many choices that we can\n",
    "make, so we just try all of them, and so the result is a\n",
    "non-deterministic value as well, only it has many more results.\n",
    "\n",
    "This context of non-determinism translates to monads very nicely. Let's\n",
    "go ahead and see what the [`Monad`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Monad) instance for lists looks like:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "instance Monad [] where\n",
    "    return x = [x]\n",
    "    xs >>= f = concat (map f xs)\n",
    "    fail _ = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) does the same thing as [`pure`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:pure), so we should already be familiar\n",
    "with [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) for lists. It takes a value and puts it in a minimal default\n",
    "context that still yields that value. In other words, it makes a list\n",
    "that has only that one value as its result. This is useful for when we\n",
    "want to just wrap a normal value into a list so that it can interact\n",
    "with non-deterministic values.\n",
    "\n",
    "To understand how [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) works for lists, it's best if we take a look at\n",
    "it in action to gain some intuition first. [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) is about taking a value\n",
    "with a context (a monadic value) and feeding it to a function that takes\n",
    "a normal value and returns one that has context. If that function just\n",
    "produced a normal value instead of one with a context, [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) wouldn't be\n",
    "so useful because after one use, the context would be lost. Anyway,\n",
    "let's try feeding a non-deterministic value to a function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3,-3,4,-4,5,-5]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[3,4,5] >>= \\x -> [x,-x]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we used [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) with [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe), the monadic value was fed into the\n",
    "function while taking care of possible failures. Here, it takes care of\n",
    "non-determinism for us. `[3,4,5]` is a non-deterministic value and we feed\n",
    "it into a function that returns a non-deterministic value as well. The\n",
    "result is also non-deterministic, and it features all the possible\n",
    "results of taking elements from the list `[3,4,5]` and passing them to the\n",
    "function `\\x -> [x,-x]`. This function takes a number and produces two\n",
    "results: one negated and one that's unchanged. So when we use [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) to\n",
    "feed this list to the function, every number is negated and also kept\n",
    "unchanged. The `x` from the lambda takes on every value from the list\n",
    "that's fed to it.\n",
    "\n",
    "To see how this is achieved, we can just follow the implementation.\n",
    "First, we start off with the list `[3,4,5]`. Then, we map the lambda over\n",
    "it and the result is the following:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "[[3,-3],[4,-4],[5,-5]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The lambda is applied to every element and we get a list of lists.\n",
    "Finally, we just flatten the list and voila! We've applied a\n",
    "non-deterministic function to a non-deterministic value!\n",
    "\n",
    "Non-determinism also includes support for failure. The empty list `[]` is\n",
    "pretty much the equivalent of [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing), because it signifies the absence\n",
    "of a result. That's why failing is just defined as the empty list. The\n",
    "error message gets thrown away. Let's play around with lists that fail:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[] >>= \\x -> [\"bad\",\"mad\",\"rad\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[1,2,3] >>= \\x -> []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the first line, an empty list is fed into the lambda. Because the\n",
    "list has no elements, none of them can be passed to the function and so\n",
    "the result is an empty list. This is similar to feeding [`Nothing`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Nothing) to a\n",
    "function. In the second line, each element gets passed to the function,\n",
    "but the element is ignored and the function just returns an empty list.\n",
    "Because the function fails for every element that goes in it, the result\n",
    "is a failure.\n",
    "\n",
    "Just like with [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) values, we can chain several lists with [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-),\n",
    "propagating the non-determinism:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1,'a'),(1,'b'),(2,'a'),(2,'b')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[1,2] >>= \\n -> ['a','b'] >>= \\ch -> return (n,ch)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/concatmap.png\" title=\"concatmap\" style=\"float:left;margin-right:2em;\" />\n",
    "\n",
    "The list `[1,2]` gets bound to `n` and `['a','b']` gets bound to `ch`. Then, we\n",
    "do `return (n,ch)` (or `[(n,ch)]`), which means taking a pair of `(n,ch)` and\n",
    "putting it in a default minimal context. In this case, it's making the\n",
    "smallest possible list that still presents `(n,ch)` as the result and\n",
    "features as little non-determinism as possible. Its effect on the\n",
    "context is minimal. What we're saying here is this: for every element in\n",
    "`[1,2]`, go over every element in `['a','b']` and produce a tuple of one\n",
    "element from each list.\n",
    "\n",
    "Generally speaking, because [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) takes a value and wraps it in a\n",
    "minimal context, it doesn't have any extra effect (like failing in [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe)\n",
    "or resulting in more non-determinism for lists) but it does present\n",
    "something as its result.\n",
    "\n",
    "> When you have non-deterministic values interacting, you can view their\n",
    "> computation as a tree where every possible result in a list represents a\n",
    "> separate branch.\n",
    "\n",
    "Here's the previous expression rewritten in `do` notation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "listOfTuples :: [(Int,Char)]\n",
    "listOfTuples = do\n",
    "    n <- [1,2]\n",
    "    ch <- ['a','b']\n",
    "    return (n,ch)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This makes it a bit more obvious that `n` takes on every value from `[1,2]`\n",
    "and `ch` takes on every value from `['a','b']`. Just like with [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe), we're\n",
    "extracting the elements from the monadic values and treating them like\n",
    "normal values and [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) takes care of the context for us. The context in\n",
    "this case is non-determinism.\n",
    "\n",
    "Using lists with `do` notation really reminds me of something we've seen\n",
    "before. Check out the following piece of code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1,'a'),(1,'b'),(2,'a'),(2,'b')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[ (n,ch) | n <- [1,2], ch <- ['a','b'] ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yes! List comprehensions! In our `do` notation example, `n` became every\n",
    "result from `[1,2]` and for every such result, `ch` was assigned a result\n",
    "from `['a','b']` and then the final line put `(n,ch)` into a default context\n",
    "(a singleton list) to present it as the result without introducing any\n",
    "additional non-determinism. In this list comprehension, the same thing\n",
    "happened, only we didn't have to write [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) at the end to present\n",
    "`(n,ch)` as the result because the output part of a list comprehension did\n",
    "that for us.\n",
    "\n",
    "In fact, list comprehensions are just syntactic sugar for using lists as\n",
    "monads. In the end, list comprehensions and lists in `do` notation\n",
    "translate to using [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) to do computations that feature\n",
    "non-determinism.\n",
    "\n",
    "List comprehensions allow us to filter our output. For instance, we can\n",
    "filter a list of numbers to search only for that numbers whose digits\n",
    "contain a `7`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7,17,27,37,47]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[ x | x <- [1..50], '7' `elem` show x ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We apply [`show`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:show) to `x` to turn our number into a string and then we check if\n",
    "the character `'7'` is part of that string. Pretty clever. To see how\n",
    "filtering in list comprehensions translates to the list monad, we have\n",
    "to check out the [`guard`](https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:guard) function and the [`MonadPlus`](https://hackage.haskell.org/package/base/docs/Control-Monad.html#t:MonadPlus) type class. The\n",
    "[`MonadPlus`](https://hackage.haskell.org/package/base/docs/Control-Monad.html#t:MonadPlus) type class is for monads that can also act as monoids. Here's\n",
    "its definition:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "class Monad m => MonadPlus m where\n",
    "    mzero :: m a\n",
    "    mplus :: m a -> m a -> m a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[`mzero`](https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:mzero) is synonymous to [`mempty`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:mempty) from the [`Monoid`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Monoid) type class and [`mplus`](https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:mplus)\n",
    "corresponds to [`mappend`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:mappend). Because lists are monoids as well as monads,\n",
    "they can be made an instance of this type class:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "instance MonadPlus [] where\n",
    "    mzero = []\n",
    "    mplus = (++)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For lists [`mzero`](https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:mzero) represents a non-deterministic computation that has no\n",
    "results at all — a failed computation. [`mplus`](https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:mplus) joins two non-deterministic\n",
    "values into one. The [`guard`](https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:guard) function is defined like this:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "guard :: (MonadPlus m) => Bool -> m ()\n",
    "guard True = return ()\n",
    "guard False = mzero"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "import Control.Monad"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It takes a boolean value and if it's [`True`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:True), takes a `()` and puts it in a\n",
    "minimal default context that still succeeds. Otherwise, it makes a\n",
    "failed monadic value. Here it is in action:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just ()"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "guard (5 > 2) :: Maybe ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "guard (1 > 2) :: Maybe ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[()]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "guard (5 > 2) :: [()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "guard (1 > 2) :: [()]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looks interesting, but how is it useful? In the list monad, we use it to\n",
    "filter out non-deterministic computations. Observe:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7,17,27,37,47]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[1..50] >>= (\\x -> guard ('7' `elem` show x) >> return x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The result here is the same as the result of our previous list\n",
    "comprehension. How does [`guard`](https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:guard) achieve this? Let's first see how [`guard`](https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:guard)\n",
    "functions in conjunction with [`>>`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62-):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[\"cool\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "guard (5 > 2) >> return \"cool\" :: [String]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "guard (1 > 2) >> return \"cool\" :: [String]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If [`guard`](https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:guard) succeeds, the result contained within it is an empty tuple. So\n",
    "then, we use [`>>`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62-) to ignore that empty tuple and present something else\n",
    "as the result. However, if [`guard`](https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:guard) fails, then so will the [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) later\n",
    "on, because feeding an empty list to a function with [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) always\n",
    "results in an empty list. A [`guard`](https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:guard) basically says: if this boolean is\n",
    "[`False`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:False) then produce a failure right here, otherwise make a successful\n",
    "value that has a dummy result of `()` inside it. All this does is to allow\n",
    "the computation to continue.\n",
    "\n",
    "Here's the previous example rewritten in `do` notation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "sevensOnly :: [Int]\n",
    "sevensOnly = do\n",
    "    x <- [1..50]\n",
    "    guard ('7' `elem` show x)\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Had we forgotten to present `x` as the final result by using [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return), the\n",
    "resulting list would just be a list of empty tuples. Here's this again\n",
    "in the form of a list comprehension:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7,17,27,37,47]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[ x | x <- [1..50], '7' `elem` show x ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So filtering in list comprehensions is the same as using [`guard`](https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:guard).\n",
    "\n",
    "### A knight's quest\n",
    "\n",
    "Here's a problem that really lends itself to being solved with\n",
    "non-determinism. Say you have a chess board and only one knight piece on\n",
    "it. We want to find out if the knight can reach a certain position in\n",
    "three moves. We'll just use a pair of numbers to represent the knight's\n",
    "position on the chess board. The first number will determine the column\n",
    "he's in and the second number will determine the row.\n",
    "\n",
    "<img src=\"img/chess.png\" title=\"hee haw im a horse\" style=\"\" />\n",
    "\n",
    "Let's make a type synonym for the knight's current position on the chess\n",
    "board:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "type KnightPos = (Int,Int)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So let's say that the knight starts at `(6,2)`. Can he get to `(6,1)` in\n",
    "exactly three moves? Let's see. If we start off at `(6,2)` what's the best\n",
    "move to make next? I know, how about all of them! We have\n",
    "non-determinism at our disposal, so instead of picking one move, let's\n",
    "just pick all of them at once. Here's a function that takes the knight's\n",
    "position and returns all of its next moves:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "moveKnight :: KnightPos -> [KnightPos]\n",
    "moveKnight (c,r) = do\n",
    "    (c',r') <- [(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1)\n",
    "               ,(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2)\n",
    "               ]\n",
    "    guard (c' `elem` [1..8] && r' `elem` [1..8])\n",
    "    return (c',r')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The knight can always take one step horizontally or vertically and two\n",
    "steps horizontally or vertically but its movement has to be both\n",
    "horizontal and vertical. `(c',r')` takes on every value from the list of\n",
    "movements and then [`guard`](https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:guard) makes sure that the new move, `(c',r')` is still\n",
    "on the board. If it it's not, it produces an empty list, which causes a\n",
    "failure and `return (c',r')` isn't carried out for that position.\n",
    "\n",
    "This function can also be written without the use of lists as a monad,\n",
    "but we did it here just for kicks. Here is the same function done with\n",
    "[`filter`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:filter):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "moveKnight :: KnightPos -> [KnightPos]\n",
    "moveKnight (c,r) = filter onBoard\n",
    "    [(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1)\n",
    "    ,(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2)\n",
    "    ]\n",
    "    where onBoard (c,r) = c `elem` [1..8] && r `elem` [1..8]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Both of these do the same thing, so pick one that you think looks nicer.\n",
    "Let's give it a whirl:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(8,1),(8,3),(4,1),(4,3),(7,4),(5,4)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "moveKnight (6,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(6,2),(7,3)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "moveKnight (8,1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Works like a charm! We take one position and we just carry out all the\n",
    "possible moves at once, so to speak. So now that we have a\n",
    "non-deterministic next position, we just use [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) to feed it to\n",
    "`moveKnight`. Here's a function that takes a position and returns all the\n",
    "positions that you can reach from it in three moves:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "in3 :: KnightPos -> [KnightPos]\n",
    "in3 start = do\n",
    "    first <- moveKnight start\n",
    "    second <- moveKnight first\n",
    "    moveKnight second"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you pass it `(6,2)`, the resulting list is quite big, because if there\n",
    "are several ways to reach some position in three moves, it crops up in\n",
    "the list several times. The above without `do` notation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) once gives us all possible moves from the start and then\n",
    "when we use [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) the second time, for every possible first move, every\n",
    "possible next move is computed, and the same goes for the last move.\n",
    "\n",
    "Putting a value in a default context by applying [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) to it and then\n",
    "feeding it to a function with [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) is the same as just normally\n",
    "applying the function to that value, but we did it here anyway for\n",
    "style.\n",
    "\n",
    "Now, let's make a function that takes two positions and tells us if you\n",
    "can get from one to the other in exactly three steps:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [],
   "source": [
    "canReachIn3 :: KnightPos -> KnightPos -> Bool\n",
    "canReachIn3 start end = end `elem` in3 start"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We generate all the possible positions in three steps and then we see if\n",
    "the position we're looking for is among them. So let's see if we can get\n",
    "from `(6,2)` to `(6,1)` in three moves:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(6,2) `canReachIn3` (6,1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yes! How about from `(6,2)` to `(7,3)`?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(6,2) `canReachIn3` (7,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No! As an exercise, you can change this function so that when you can\n",
    "reach one position from the other, it tells you which moves to take.\n",
    "Later on, we'll see how to modify this function so that we also pass it\n",
    "the number of moves to take instead of that number being hardcoded like\n",
    "it is now.\n",
    "\n",
    "Monad laws\n",
    "----------\n",
    "\n",
    "<img src=\"img/judgedog.png\" title=\"the court finds you guilty of peeing all over everything\" style=\"float:right;margin-left:2em;\" />\n",
    "\n",
    "Just like applicative functors, and functors before them, monads come\n",
    "with a few laws that all monad instances must abide by. Just because\n",
    "something is made an instance of the [`Monad`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Monad) type class doesn't mean that\n",
    "it's a monad, it just means that it was made an instance of a type\n",
    "class. For a type to truly be a monad, the monad laws must hold for that\n",
    "type. These laws allow us to make reasonable assumptions about the type\n",
    "and its behavior.\n",
    "\n",
    "Haskell allows any type to be an instance of any type class as long as\n",
    "the types check out. It can't check if the monad laws hold for a type\n",
    "though, so if we're making a new instance of the [`Monad`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Monad) type class, we\n",
    "have to be reasonably sure that all is well with the monad laws for that\n",
    "type. We can rely on the types that come with the standard library to\n",
    "satisfy the laws, but later when we go about making our own monads,\n",
    "we're going to have to manually check the if the laws hold. But don't\n",
    "worry, they're not complicated.\n",
    "\n",
    "### Left identity\n",
    "\n",
    "The first monad law states that if we take a value, put it in a default\n",
    "context with [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) and then feed it to a function by using [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-), it's\n",
    "the same as just taking the value and applying the function to it. To\n",
    "put it formally:\n",
    "\n",
    "-   **`return x >>= f`** is the same damn thing as **`f x`**\n",
    "\n",
    "If you look at monadic values as values with a context and [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) as\n",
    "taking a value and putting it in a default minimal context that still\n",
    "presents that value as its result, it makes sense, because if that\n",
    "context is really minimal, feeding this monadic value to a function\n",
    "shouldn't be much different than just applying the function to the\n",
    "normal value, and indeed it isn't different at all.\n",
    "\n",
    "For the [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) monad [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) is defined as [`Just`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:Just). The [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) monad is all\n",
    "about possible failure, and if we have a value and want to put it in\n",
    "such a context, it makes sense that we treat it as a successful\n",
    "computation because, well, we know what the value is. Here's some [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return)\n",
    "usage with [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just 100003"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "return 3 >>= (\\x -> Just (x+100000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just 100003"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(\\x -> Just (x+100000)) 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the list monad [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) puts something in a singleton list. The [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-)\n",
    "implementation for lists goes over all the values in the list and\n",
    "applies the function to them, but since there's only one value in a\n",
    "singleton list, it's the same as applying the function to that value:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[\"WoM\",\"WoM\",\"WoM\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "return \"WoM\" >>= (\\x -> [x,x,x])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[\"WoM\",\"WoM\",\"WoM\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(\\x -> [x,x,x]) \"WoM\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We said that for [`IO`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:IO), using [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) makes an I/O action that has no\n",
    "side-effects but just presents a value as its result. So it makes sense\n",
    "that this law holds for [`IO`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:IO) as well.\n",
    "\n",
    "### Right identity\n",
    "\n",
    "The second law states that if we have a monadic value and we use [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-)\n",
    "to feed it to [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return), the result is our original monadic value.\n",
    "Formally:\n",
    "\n",
    "-   **`m >>= return`** is no different than just **`m`**\n",
    "\n",
    "This one might be a bit less obvious than the first one, but let's take\n",
    "a look at why it should hold. When we feed monadic values to functions\n",
    "by using [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-), those functions take normal values and [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) monadic\n",
    "ones. [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) is also one such function, if you consider its type. Like\n",
    "we said, return puts a value in a minimal context that still presents\n",
    "that value as its result. This means that, for instance, for [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe), it\n",
    "doesn't introduce any failure and for lists, it doesn't introduce any\n",
    "extra non-determinism. Here's a test run for a few monads:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just \"move on up\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Just \"move on up\" >>= (\\x -> return x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,2,3,4]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[1,2,3,4] >>= (\\x -> return x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Wah!"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "putStrLn \"Wah!\" >>= (\\x -> return x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we take a closer look at the list example, the implementation for\n",
    "[`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) is:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "xs >>= f = concat (map f xs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So when we feed `[1,2,3,4]` to [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return), first [`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) gets mapped over\n",
    "`[1,2,3,4]`, resulting in `[[1],[2],[3],[4]]` and then this gets\n",
    "concatenated and we have our original list.\n",
    "\n",
    "Left identity and right identity are basically laws that describe how\n",
    "[`return`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:return) should behave. It's an important function for making normal\n",
    "values into monadic ones and it wouldn't be good if the monadic value\n",
    "that it produced did a lot of other stuff.\n",
    "\n",
    "### Associativity\n",
    "\n",
    "The final monad law says that when we have a chain of monadic function\n",
    "applications with [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-), it shouldn't matter how they're nested.\n",
    "Formally written:\n",
    "\n",
    "-   Doing **`(m >>= f) >>= g`** is just like doing **`m >>= (\\x -> f x >>= g)`**\n",
    "\n",
    "Hmmm, now what's going on here? We have one monadic value, `m` and two\n",
    "monadic functions `f` and `g`. When we're doing `(m >>= f) >>= g`, we're\n",
    "feeding `m` to `f`, which results in a monadic value. Then, we feed that\n",
    "monadic value to `g`. In the expression `m >>= (\\x -> f x >>= g)`, we\n",
    "take a monadic value and we feed it to a function that feeds the result\n",
    "of `f x` to `g`. It's not easy to see how those two are equal, so let's take\n",
    "a look at an example that makes this equality a bit clearer.\n",
    "\n",
    "Remember when we had our tightrope walker Pierre walk a rope while birds\n",
    "landed on his balancing pole? To simulate birds landing on his balancing\n",
    "pole, we made a chain of several functions that might produce failure:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just (2,4)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "return (0,0) >>= landRight 2 >>= landLeft 2 >>= landRight 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We started with `Just (0,0)` and then bound that value to the next monadic\n",
    "function, `landRight 2`. The result of that was another monadic value\n",
    "which got bound into the next monadic function, and so on. If we were to\n",
    "explicitly parenthesize this, we'd write:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just (2,4)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "((return (0,0) >>= landRight 2) >>= landLeft 2) >>= landRight 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But we can also write the routine like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Just (2,4)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "return (0,0) >>= (\\x ->\n",
    "  landRight 2 x >>= (\\y ->\n",
    "    landLeft 2 y >>= (\\z ->\n",
    "      landRight 2 z)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`return (0,0)` is the same as `Just (0,0)` and when we feed it to the\n",
    "lambda, the `x` becomes `(0,0)`. `landRight` takes a number of birds and a\n",
    "pole (a tuple of numbers) and that's what it gets passed. This results\n",
    "in a `Just (0,2)` and when we feed this to the next lambda, `y` is `(0,2)`.\n",
    "This goes on until the final bird landing produces a `Just (2,4)`, which\n",
    "is indeed the result of the whole expression.\n",
    "\n",
    "So it doesn't matter how you nest feeding values to monadic functions,\n",
    "what matters is their meaning. Here's another way to look at this law:\n",
    "consider composing two functions, `f` and `g`. Composing two functions is\n",
    "implemented like so:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "(.) :: (b -> c) -> (a -> b) -> (a -> c)\n",
    "f . g = (\\x -> f (g x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If the type of `g` is `a -> b` and the type of `f` is `b -> c`, we arrange\n",
    "them into a new function which has a type of `a -> c`, so that its\n",
    "parameter is passed between those functions. Now what if those two\n",
    "functions were monadic, that is, what if the values they returned were\n",
    "monadic values? If we had a function of type `a -> m b`, we couldn't just\n",
    "pass its result to a function of type `b -> m c`, because that function\n",
    "accepts a normal `b`, not a monadic one. We could however, use [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-) to\n",
    "make that happen. So by using [`>>=`](https://hackage.haskell.org/package/base/docs/Prelude.html#v:-62--62--61-), we can compose two monadic\n",
    "functions:"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "source": [
    "(<=<) :: (Monad m) => (b -> m c) -> (a -> m b) -> (a -> m c)\n",
    "f <=< g = (\\x -> g x >>= f)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So now we can compose two monadic functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {
    "attributes": {
     "classes": [
      "haskell:hs"
     ],
     "id": "",
     "name": "\"code\""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[9,-9,6,-6]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "let f x = [x,-x]\n",
    "let g x = [x*3,x*2]\n",
    "let h = f <=< g\n",
    "h 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cool. So what does that have to do with the associativity law? Well,\n",
    "when we look at the law as a law of compositions, it states that\n",
    "**`f <=< (g <=< h)`** should be the same as **`(f <=< g) <=< h`**. This is just\n",
    "another way of saying that for monads, the nesting of operations\n",
    "shouldn't matter.\n",
    "\n",
    "If we translate the first two laws to use [`<=<`](https://hackage.haskell.org/package/base/docs/Control-Monad.html#v:-60--61--60-), then the left identity\n",
    "law states that for every monadic function f, **`f <=< return`** is the same\n",
    "as writing just **`f`** and the right identity law says that **`return <=< f`** is\n",
    "also no different from **`f`**.\n",
    "\n",
    "This is very similar to how if `f` is a normal function, `(f . g) . h` is\n",
    "the same as `f . (g . h)`, `f . id` is always the same as `f` and `id . f` is\n",
    "also just `f`.\n",
    "\n",
    "In this chapter, we took a look at the basics of monads and learned how\n",
    "the [`Maybe`](https://hackage.haskell.org/package/base/docs/Prelude.html#t:Maybe) monad and the list monad work. In the next chapter, we'll take\n",
    "a look at a whole bunch of other cool monads and we'll also learn how to\n",
    "make our own."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Haskell",
   "language": "haskell",
   "name": "haskell"
  },
  "language_info": {
   "codemirror_mode": "ihaskell",
   "file_extension": ".hs",
   "name": "haskell",
   "pygments_lexer": "Haskell",
   "version": "8.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}