2
$\begingroup$

Is there a translation between unit/bind and fmap/join in monads?

https://stackoverflow.com/questions/34398239/with-monads-can-join-be-defined-in-terms-of-bind

gives a partial one:

bind f m = join (fmap f m)

and

join x = bind x id

but can we express fmap in terms of unit and bind

and unit in terms of fmap and join?

$\endgroup$

2 Answers 2

3
$\begingroup$

You can express fmap in terms of unit and bind:

fmap f xs = bind xs (\x -> unit (f x))

You cannot express unit in terms of fmap and join. Intuitively, both fmap and join "take" a monad as one of their arguments, which means that neither of those functions, even in combination, give you a way to manufacture a monad from a non-monad.

$\endgroup$
3
$\begingroup$

Pseudonym's answer is correct, but it might be useful to some people to look at this from a categorical point of view so that we can give a proof using the monad rules.

The Haskell function bind, or >>=, has signature m a -> (a -> m b) -> m b, and the related Kleisli composition >=> is (a -> m b) -> (b -> m c) -> (a -> m c), where m is a monad. The relationships between these are that (f >=> g) x = (f x) >>= g) and (p >>= f) = (id >=> f) p.

The usual category-theoretical definition of monad is that it is an endofunctor equipped with natural transformations $\mu : T^2 \to T$ and $\eta : I \to T$ (the unit, or return in Haskell), satisfying associativity and unit conditions. The Kleisli composite of $f : a \to T b$ and $g : b \to T c$ is $$g \circ _K f := \mu_c \circ T(g) \circ f,$$ a morphism $a \to T c$. In this language it is more natural to swap the arguments of bind around so that it has signature (a -> m b) -> (m a -> m b), and on doing so given $f : a \to T b$ we would have $$\operatorname{bind}(f) := f \circ_K \operatorname{id}_{T a} = \mu_b \circ T(f)$$ and $$g \circ _K f = \operatorname{bind}(g) \circ f.$$

We then have, for $h : a \to b$, that $$\operatorname{bind}(\eta_b \circ h) = \mu_b \circ T(\eta_b h) = \mu_b \circ T(\eta_b) \circ T h$$ which is equal to $T h$ because $\mu_b \circ T(\eta_b) = \operatorname{id} _b$ by one of the unit laws for the monad $T$. This shows that the action of $T$ on morphisms, fmap in Haskell language, can be expressed using bind.

As an example, consider the list monad [] on the category Hask of Haskell types and programs. If $f : a \to b$ then $\eta_b \circ f : a \to [b]$ is $x \mapsto [f(x)]$. The multiplication $\mu$ for [] is concatenation of lists, so \begin{align*}\operatorname{bind}(\eta_b \circ f) ([x_1, x_2, \ldots]) &= \mu_b \circ [\eta_b \circ f] ([x_1, x_2, \ldots])\\ & = \operatorname{concat}([[f(x_1)], [f(x_2)], \ldots])\\ & = [f(x_1), f(x_2), \ldots]\end{align*} which is exactly $[f]([x_1, x_2, \ldots])$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.