# Yet Another Haskell Tutorial/Monads/Solutions
## Common Monads

The first law is: return a >>= f ≡ f a. In the case of Maybe, we get:
The second law is: f >>= return ≡ f. Here, we get:
At this point, there are two cases depending on whether f is Nothing or not. In the first case, we get:
In the second case, f is Just a. Then, we get:
And the second law is shown. The third law states: f >>= (\x -> g x >>= h) ≡ (f >>= g) >>= h.
If f is Nothing, then the left-hand-side clearly reduces to Nothing. The right-hand-side reduces to Nothing >>= h which in turn reduces to Nothing, so they are the same.
Suppose f is Just a. Then the LHS reduces to g a >>= h and the RHS reduces to (Just a >>= \x -> g x) >>= h which in turn reduces to g a >>= h, so these two are the same.
The idea is that we wish to use the Left constructor to represent errors on the Right constructor to represent successes. This leads to an instance declaration like:
If we try to use this monad to do search, we get:
Example:
which is exactly what we want.

## MonadPlus

The order to mplus essentially determins the search order. When the recursive call to searchAll2 comes first, we are doing depth-first search. When the recursive call to search' comes first, we are doing breadth-first search. Thus, using the list monad, we expect the solutions to come in the other order:
Example:
Just as we expected.

## Monad Transformers

This is a very difficult problem; if you found that you were stuck immediately, please just read as much of this solution as you need to try it yourself.
First, we need to define a list transformer monad. This looks like:
The ListT constructor simply wraps a monadic action (in monad m) which returns a list.
We now need to make this a monad:
Here, success is designated by a monadic action which returns a singleton list. Failure (like in the standard list monad) is represented by an empty list: of course, it's actually an empty list returned from the enclosed monad. Binding happens essentially by running the action which will result in a list l. This has type [e]. We now need to apply k to each of these elements (which will result in something of type ListT m [e2]. We need to get rid of the ListTs around this (by using unListT) and then concatenate them to make a single list.
Now, we need to make it an instance of MonadPlus
Here, the zero element is a monadic action which returns an empty list. Addition is done by executing both actions and then concatenating the results.
Finally, we need to make it an instance of MonadTrans:
Lifting an action into ListT simply involves running it and getting the value (in this case, a) out and then returning the singleton list.
Once we have all this together, writing searchAll6 is fairly straightforward:
The only change (besides changing the recursive call to call searchAll6 instead of searchAll2) here is that we call putStrLn with appropriate arguments, lifted into the monad.
If we look at the type of searchAll6, we see that the result (i.e., after applying a graph and two ints) has type MonadTrans t, MonadPlus (t IO) => t IO [Int]). In theory, we could use this with any appropriate monad transformer; in our case, we want to use ListT. Thus, we can run this by:
Example:
This is precisely what we were looking for. This exercise is actually simpler than the previous one. All we need to do is incorporate the calls to putT and getT into searchAll6 and add an extra lift to the IO calls. This extra lift is required because now we're stacking two transformers on top of IO instead of just one.
The type of this has grown significantly. After applying the graph and two ints, this has type Monad (t IO), MonadTrans t, MonadPlus (StateT [Int] (t IO)) => StateT [Int] (t IO) [Int].
Essentially this means that we've got something that's a state transformer wrapped on top of some other arbitrary transformer (t) which itself sits on top of IO. In our case, t is going to be ListT. Thus, we run this beast by saying:
Example:
And it works, even on gr4.

## Parsing Monads
### A Simple Parsing Monad

First we write a function spaces which will parse out whitespaces:
Now, using this, we simply sprinkle calls to spaces through intList to get intListSpace:
We can test that this works:
Example:
=== Parsec ===
We do this by replacing the state functions with push and pop functions as follows:
The primary difference here is that instead of calling updateState, we use two local functions, pushBinding and popBinding. The pushBinding function takes a variable name and a value and adds the value onto the head of the list pointed to in the state FiniteMap. The popBinding function looks at the value and if there is only one element on the stack, it completely removes the stack from the FiniteMap; otherwise it just removes the first element. This means that if something is in the FiniteMap, the stack is never empty.
This enables us to modify only slightly the usage case; this time, we simply take the top element off the stack when we need to inspect the value of a variable.
We can test that this works:
Example: