Cheat sheet for Monads in Haskell

Let M be a Type Constructor, Functor, and Monad.

As a Type Constructor, M can map a type a to the type M a.

As a Functor, M can also map a function f to the function M f, using M’s fmap function that we must provide.

As a Monad, M has a Natural Transformation μ :: M2 -> M, where M2 = M o M. We will see how this makes possible the composition of a function a – > M b and a function b -> M c.

If we have a function g :: a -> b and a function f :: b -> c, then we can compose these two functions. Their composition is the function f o g :: a -> c.

f o g is calculated as follows: a -> b -> c. In other words, the input of function g is the input of f o g, the output of function g is used as input to the function f, and the output of function f is the output of f o g.

But we cannot use “normal” composition when the functions g and f are of the following form:

g :: a -> M b
f :: b -> M c

In this case, to “compose” these two functions we need to define a “special” composition. Let us call this special composition “bind” and let its symbol be >>= so that g >>= f is this special composition. Thus, bind takes the output of function g, passes it function f, and produces as output the output of function f. Thus (>>=) :: M b -> (b -> M c) -> M c. Since b and c are any types, we can use a and b instead of b and c. Thus: ( >>=) :: M a -> (a -> M b) -> M b.

Thus, bind is defined as M a -> (a -> M b) -> M b. Now let us see what bind is equal to. Let:

g :: a -> M b
f :: b -> M c

Thus M f :: M b -> M2 c, where M2 = M o M.

In the previous line, M was used as a Functor. M f is also known as fmap f.

As a Monad, M has a Natural Transformation μ­­a :: M2 a -> M a. Since this holds true for any type, we use c instead of a, thus μ­­­c :: M2 c -> M c. μ is also known as join.

We can now find the result of the special composition between g and f and what bind is equal to.

g >>= f is calculated as follows: a -> M b -> M2 c -> M c.

Thus >>= is equal to μc o (M f) o g.

Thus bind = join o (fmap f) o g.

By using the special composition bind (>>=), we are able to compose two functions that are NOT of types a-> b and b -> c, but are of types a -> M b and b -> M c.

Advertisements

About Dimitrios Kalemis

I am a systems engineer specializing in Microsoft products and technologies. I am also an author. Please visit my blog to see the blog posts I have written, the books I have written and the applications I have created. I definitely recommend my blog posts under the category "Management", all my books and all my applications. I believe that you will find them interesting and useful. I am in the process of writing more blog posts and books, so please visit my blog from time to time to see what I come up with next. I am also active on other sites; links to those you can find in the "About me" page of my blog.
This entry was posted in Development. Bookmark the permalink.