cscalfani · January 4, 2021 20:47 · Dec 19, 2017 · Dec 19, 2017 · Dec 19, 2017 · Dec 19, 2017
diff --git a/MonadsOfFunctions.md b/MonadsOfFunctions.md
@@ -201,7 +201,7 @@ I hope that this will help when you learn about `State`, `Reader`, `Writer` and
 
 ## Further Reading
 
-- [Monads] (https://en.wikibooks.org/wiki/Haskell/Understanding_monads)
+- [Monads](https://en.wikibooks.org/wiki/Haskell/Understanding_monads)
 - [State Monad](https://en.wikibooks.org/wiki/Haskell/Understanding_monads/State)
 - [Effective Haskell: IO, Monads, Functors](https://slpopejoy.github.io/posts/Effectful01.html)
-- [Effectful Haskell: Reader, Transformers, Typeclasses] (https://slpopejoy.github.io/posts/Effectful02.html)
+- [Effectful Haskell: Reader, Transformers, Typeclasses](https://slpopejoy.github.io/posts/Effectful02.html)
diff --git a/MonadsOfFunctions.md b/MonadsOfFunctions.md
@@ -199,3 +199,9 @@ So it's really a mindset change from our run of the mill Monads. We have to keep
 
 I hope that this will help when you learn about `State`, `Reader`, `Writer` and their brethren.
 
+## Further Reading
+
+- [Monads] (https://en.wikibooks.org/wiki/Haskell/Understanding_monads)
+- [State Monad](https://en.wikibooks.org/wiki/Haskell/Understanding_monads/State)
+- [Effective Haskell: IO, Monads, Functors](https://slpopejoy.github.io/posts/Effectful01.html)
+- [Effectful Haskell: Reader, Transformers, Typeclasses] (https://slpopejoy.github.io/posts/Effectful02.html)
diff --git a/MonadsOfFunctions.md b/MonadsOfFunctions.md
@@ -1,4 +1,4 @@
-# Monads of functions in Haskell
+# Monads of Functions in Haskell
 
 We're all pretty familiar with Monads that contain values, e.g. `Maybe a` and `Either e a`. Typically, these are value type, e.g. `Maybe String`, `Maybe Int`, `Either String Int`, `Either MyError MyResult`.
 

diff --git a/MonadsOfFunctions.md b/MonadsOfFunctions.md
@@ -0,0 +1,201 @@
+# Monads of functions in Haskell
+
+We're all pretty familiar with Monads that contain values, e.g. `Maybe a` and `Either e a`. Typically, these are value type, e.g. `Maybe String`, `Maybe Int`, `Either String Int`, `Either MyError MyResult`.
+
+When `fmap` is called on a `Maybe Int`, it is clear that the `Int` is going to be mapped to its new value when the `fmap` is evaluated, e.g.:
+
+```hs
+fmap (* 10) Just 1 === Just 10
+```
+
+But it's a real mind twist when the Monad contains a function. How does `fmap` work? It can only return a new function which means that its evaluated at some later date. That single fact is not always clear to the beginner (it wasn't to me which is why I'm writing this).
+
+## Why should we care?
+
+Turns out that there are some really useful Monads that contain functions, e.g. `Reader`, `Writer` and `State`. Before delving into those Monads with all of the their implied use cases, it may be helpful to just think of a simple case of a Monad with a function that needs to get evaluated to produce a final result.
+
+Hopefully, after doing so, those other Monads will be easier to understand.
+
+## Evaluator Monad
+
+Let's create a Monad that evaluates a computation with a single value as its input.
+
+```hs
+newtype Eval v r = Eval { eval :: v -> (r, v) }
+```
+
+Here `v` is the type of value passed into the evaluator and `r` is the result. Notice that, unlike `Maybe`, this type contains a function `v -> (r, v)`.
+
+Once we evaluate the function, we will get a tuple which has the result of the evaluation `r` and the value `v` that was used to produce that result.
+
+By the way, `Maybe` can take a function, but it's **NOT** designed to only take functions. And hence, the implementation of `Maybe` is not conducive to working with functions.
+
+Our implementation of `Eval` is going to make dealing with the function easier. We are already seeing this with the accessor function `eval`.
+
+### Functor and Applicative
+
+One nice thing about the Monad lineage is that Functor and Applicative can be generalized in terms of `bind` (`>>=`). `Control.Monad` allows us to do this.
+
+We also must ***fix*** the `v` type so that our type only has one parameter which Functor, Applicative and Monad all expect (kind \* -> \*). This is why we define the following instances with `Eval v` (kind \* -> \*) instead of `Eval` (kind \* -> \* -> \*). 
+
+```hs
+import qualified Control.Monad as CM
+
+instance Functor (Eval v) where
+  fmap = CM.liftM
+
+instance Applicative (Eval v) where
+  pure = return
+  (<*>) = CM.ap
+```
+
+Both `liftM` and `ap` rely on `Eval v` being a Monad. So at this point, the compiler will complain. It will also complain since we are setting `pure` equal to `return` which is a Monad function.
+
+### Monad definition
+
+Here's where the real work gets done.
+
+Let's start with `return`:
+
+```hs
+return r = Eval $ \v -> (r, v)
+```
+
+When we use `return`, the value of `v` is unchanged which works perfectly for our requirements.
+
+Before we move on to `>>=`, we should examine the implementation of `return` further. Notice how we pass a function to the data constructor. We're going to need to do that in `>>=` but not by using `return` for the aforementioned reasons.
+
+#### Bind
+
+Bind is a bit tricky. Let's first look at the definition of `>>=` to try to discern a reasonable strategy for implementing bind.
+
+```hs
+(>>=) :: Eval v a -> (a -> Eval v b) -> Eval v b
+  e >>= f = ...
+```
+
+Internally, we're going to have to crack open `e` so we can apply `f` to it. That can be done using the `eval` accessor.
+
+Notice that `f` wraps up the result in an `Eval` so after that it seems we are done.
+
+Let's give that a try:
+
+```hs
+  -- DOES NOT COMPILE !!!!
+  e >>= f = f $ fst $ eval e v
+```
+
+Well, that's not going to work, because where does the `v` come from? We need to wrap this in the same way we did with `return`.
+
+Let's try again:
+
+```hs
+  -- DOES NOT COMPILE
+  e >>= f = Eval $ \v -> f $ fst $ eval e v
+```
+
+This time we account for `v` but our lambda returns an `Eval v` not `(r, v)`. The way we fix that is by using `eval` again:
+
+```hs
+  e >>= f = Eval $ \v -> eval (f $ fst $ eval e v) v
+```
+
+The need to use `eval` twice is a common implementation pattern in Monads with functions because of the type of `f`, i.e. `a -> m b`. If it were simply, `a -> b` then this extra step would not be necessary but then the function wouldn't be `>>=`. It would be `fmap`.
+
+So now here is our final instance definition:
+
+```hs
+instance Monad (Eval v) where
+  return r = Eval $ \v -> (r, v)
+  e >>= f = Eval $ \v -> eval (f $ fst $ eval e v) v
+```
+
+One other thing to note here is that throughout all of the computations, `v` is unchanged. That's only because of the behavioral requirements we initially defined for our Monad.
+
+If this requirement was lifted, a very different implementation would have been needed for `>>=`:
+
+```hs
+instance Monad (Eval v) where
+  return r = Eval $ \v -> (r, v)
+  -- UNNECESSARILY COMPLEX FOR OUR REQUIREMENTS
+  e >>= f = Eval $ \v0 ->
+    let (r1, v1) = eval e v0
+    in eval (f r1) v1
+```
+
+In this unnecessarily complex implementation, we distinguish the different `v`s in `v0` and `v1` which is returned from the first `eval`.
+
+Turns out that this type of implementation is a necessary for the `State` monad.
+
+### Helpers
+
+Here is the full implementation, so far:
+
+```hs
+newtype Eval v r = Eval { eval :: v -> (r, v) }
+
+instance Functor (Eval v) where
+  fmap = CM.liftM
+
+instance Applicative (Eval v) where
+  pure = return
+  (<*>) = CM.ap
+
+instance Monad (Eval v) where
+  return r = Eval $ \v -> (r, v)
+  e >>= f = Eval $ \v -> eval (f $ fst $ eval e v) v
+```
+
+To use this in a program, we need a few helpers.
+
+First, we need a constructor, which we will call `createEval`:
+
+```hs
+createEval :: (v -> r) -> Eval v r
+createEval f = Eval $ \v -> (f v, v)
+```
+Here `f` is the initial function to be evaluated with different values of `v`.
+
+Next, we need a helper to just do the evaluation and return the result, which we will call `evaluate`:
+
+```hs
+evaluate :: Eval v r -> v -> r
+evaluate e v = fst $ eval e v
+```
+
+### Using Eval
+
+Let's define a test Evaluator:
+
+```hs
+test :: Eval Integer Integer
+test = (* 3) <$> createEval (* 10)
+```
+
+We first create an evaluator that takes its value and multiplies it by ten, `createEval (* 10)`.
+
+Next we map a multiply by 3 on it. (Remember that `<$>` is the infix of `fmap`.)
+
+Now we can our Eval monad:
+
+```hs
+evaluate test 10 === 300
+evaluate test 1 === 30
+eval test 10 === (300, 10)
+eval test 1 === (30, 1)
+```
+
+### Deferred Evaluation
+
+Notice, as stated at the beginning, that the effect of the `fmap` doesn't happen until we call `eval`, either directly or indirectly via `evaluate`.
+
+This is very different from an `fmap` on `[a]` or `Maybe a`. Granted Haskell is lazy and will only evaluate `fmap` when the result is needed.
+
+But with Monads of functions, an extra operation is your responsibility. You need to call (and someone needs to write) a function to do a final evaluation. All the operations before this step were just building an array or tree of functions that, when called, will produce the desired final result.
+
+In `Reader`, it's called `runReader`. In `State`, it's called `runState`.
+
+So it's really a mindset change from our run of the mill Monads. We have to keep in mind that we are creating a Deferred computation that we are responsible for performing.
+
+I hope that this will help when you learn about `State`, `Reader`, `Writer` and their brethren.
+
No results found