<p>This is basically a transcript of the post I wrote on the subject which I host <a href="https://www.crvs.xyz/posts_haskeljoin.html">here</a> It has a bit more than what I talked about</p>
<h1 id="join-in-haskell">Join in Haskell</h1>
<p><code>join</code> is a monadic operation, instead of working only on lists, it works on monads and has the signature:</p>
<pre><code>   join :: Monad m =&gt; m ( m a ) -&gt; (m a)
</code></pre>
<p>In effect it <code>joins</code> or <code>merges</code> two successive monad applications into a single monad application. But join is not part of the canonical monad definition, which is given by:</p>
<pre><code>   return ::  Monad m =&gt; a -&gt; m a` ; and`
   (&gt;&gt;=) :: Monad m =&gt; m a -&gt; ( a -&gt; m b ) -&gt; m b
</code></pre>
<p>A good or rather trivial way to think of the relationship between <code>return</code> <code>join</code> and <code>(&gt;&gt;=)</code> is that in essence, since each monad is a functor, then what <code>(&gt;&gt;=)</code> does is that it maps the second argument over the first argument, and then uses <code>join</code> to merge the two applications of the monad constructor, i.e.:</p>
<pre><code>  (x &gt;&gt;= f) = join $ fmap f x
</code></pre>
<p>However, join needs to be constructed from <code>return</code> and <code>(&gt;&gt;=)</code>. The naive solution is that we want to <code>trick</code> <code>(&gt;&gt;=)</code> to let us apply a function that does not pile up yet another <code>m</code> onto our initial type <code>m (m a)</code> and surprisingly, this will actually work if we let</p>
<pre><code>   join x = (x &gt;&gt;= id)
</code></pre>
<p>Initially this is surprising since <code>id</code> has the signature <code>(c -&gt; c)</code> instead of the necessary <code>a -&gt; m b</code>! However, when <code>c</code> is not an atomic type, but rather of the form <code>m d</code> for some (maybe atomic) type <code>d</code>, then we actually have the signature <code>m d -&gt; m d</code>, and if we bind type <code>a</code> to <code>m d</code> and type <code>b</code> to <code>d</code>, we obtain <code>id</code> with actual type signatuare <code>a -&gt; m b</code>, and it can indeed be used as the second argument of <code>(&gt;&gt;=)</code>, and everything actually makes sense.</p>
<p>Now style is important and so we can do an eta reduction on this, to get a point-free implementation by simply binding the second argument of <code>&gt;&gt;=</code>:</p>
<pre><code>   join = (&gt;&gt;= id)
</code></pre>
<p>This is all fine and well for the type number, and it <em>does</em> work, but it's also important to understand how it works, so let's see it in a simple example, using the <code>Maybe</code> monad. So let's start by refreshing the implementation of the monad instance:</p>
<pre><code>instance Monad Maybe where

   (&gt;&gt;=) :: Maybe a -&gt; (a -&gt; Maybe b) -&gt; Maybe b
   (&gt;&gt;=) Nothing _ = Nothing
   (&gt;&gt;=) (Just x) f = f x

   return :: a -&gt; Maybe a
   return = Just
</code></pre>
<p>So let's now go through the successive bindings when performing <code>(&gt;&gt;=id)</code>:</p>
<pre><code>   Just x = Just (Just 2) =&gt; x = Just 2
   Just x &gt;&gt;= id = id x = x
   x = Just 2
</code></pre>
<p>This example is pretty much verbatim the same thing for the <code>Either</code> monad and many other monads that follow a similar principle, so let's look at a bit more of a complex example. Let's look at the <code>List</code> monad:</p>
<p>instance Monad List where</p>
<pre><code>   (&gt;&gt;=) :: [a] -&gt; (a -&gt; [b]) -&gt; [b]
   (&gt;&gt;=) [] _ = []
   (&gt;&gt;=) (x:xs) f = f x ++ (xs &gt;&gt;= f)

   return :: a -&gt; [a]
   return = (:[])
</code></pre>
<p>Following the bindings again we have</p>
<pre><code>   [[2,3],[4]] = (x:xs) =&gt; x = [2,3] ; xs = [[4]]
   (x:xs) &gt;&gt;= id = (id x) ++ (xs &gt;&gt;= id) = x ++ (xs &gt;&gt;= id)
   [[4]] = (y:ys) =&gt; y = [4] ; ys = []
   (y:ys) &gt;&gt;= id = y ++ (ys &gt;&gt;= id)
   ys = [] =&gt; (ys &gt;&gt;= id) = []
   =&gt; (y:ys) &gt;&gt;= id  =  [4] ++ [] = [4]
   =&gt; xs &gt;&gt;= id = [4]
   =&gt; (x:xs) &gt;&gt;= id = x ++ [4] = [2,3] ++ [4] = [2,3,4]
</code></pre>
<p>So all of this is to say that <code>join</code> actually does what one expects it to do on a list of lists. It joins them one by one into a single list.</p>
<h1 id="the-associativity-law">The Associativity Law</h1>
<p>The associativity law of a monad can be quite confusing, after all it takes the form:</p>
<pre><code>   (m &gt;&gt;= f) &gt;&gt;= g == m &gt;&gt;= ( x -&gt; f x &gt;&gt;= g )
</code></pre>
<p>While not too complicated to understand it is difficult to see how it relates to a usual associativity law, which follows the form <code>a * (b * c) = (a * b) * c</code>. To recover the associativity the usual explanation is that one has to see it in terms of the monadic function composition <code>(&gt;=&gt;)</code> and while this is a valid way of doing so, I like to decompose things in terms of <code>fmap</code>, <code>(&gt;&gt;=)</code> and <code>join</code>.</p>
<p>So let's use what we did previously on the associativity law, starting on the left side, and replacing the atomic-looking type <code>m</code> with the dependent type <code>M z</code>:</p>
<pre><code>   (M z &gt;&gt;= f) &gt;&gt;= g
   = join (fmap f (M z)) &gt;&gt;= g
   = join (fmap g $ join ( fmap f (M z)))
   = join (fmap g $ join ( M (f z) )
</code></pre>
<p>and the right-hand side:</p>
<pre><code>   M z &gt;&gt;= ( x -&gt; f x &gt;&gt;= g )
   = M z &gt;&gt;= ( x -&gt; join $ fmap g (f x))
   = join $ fmap ( x -&gt; join $ fmap g (f x)) (M z)
   = join $ M ( x -&gt; join $ fmap g (f x)) z
   = join $ M (join $ fmap g (f z))
</code></pre>
<p>And essentially what it says is that if I have two functions <code>f</code> and <code>g</code> I can either do it in an orderly fashion where I apply them sequentially with <code>join . fmap f</code> followed by <code>join . fmap g</code>, or I can apply them both within the constructor and then join once within the constructor and one outside the constructor, and I should get the same thing. In fact if you replace <code>f</code> and <code>g</code> with <code>id</code>; this is the associativity law for monads as usually presented in a standard category theory textbook such as Mac Lane's Categories for the Working Mathematician (and recovering this was the whole point of this exercise in the first place).</p>
