Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the relationship between bind and join?

I got the impression that (>>=) (used by Haskell) and join (preferred by mathematicians) are "equal" since one can write one in terms of the other:

import Control.Monad (join)

join x = x >>= id
x >>= f = join (fmap f x)

Additionally every monad is a functor since bind can be used to replace fmap:

fmap f x = x >>= (return . f)

I have the following questions:

  1. Is there a (non-recursive) definition of fmap in terms of join? (fmap f x = join $ fmap (return . f) x follows from the equations above but is recursive.)

  2. Is "every monad is a functor" a conclusion when using bind (in the definition of a monad), but an assumption when using join?

  3. Is bind more "powerful" than join? And what would "more powerful" mean?

like image 612
Micha Wiedenmann Avatar asked May 31 '19 08:05

Micha Wiedenmann


1 Answers

A monad can be either defined in terms of:

  • return :: a -> m a
  • bind :: m a -> (a -> m b) -> m b

or alternatively in terms of:

  • return :: a -> m a
  • fmap :: (a -> b) -> m a -> m b
  • join :: m (m a) -> m a

To your questions:

  1. No, we cannot define fmap in terms of join, since otherwise we could remove fmap from the second list above.
  2. No, "every monad is a functor" is a statement about monads in general, regardless whether you define your specific monad in terms of bind or in terms of join and fmap. It is easier to understand the statement if you see the second definition, but that's it.
  3. Yes, bind is more "powerful" than join. It is exactly as "powerful" as join and fmap combined, if you mean with "powerful" that it has the capacity to define a monad (always in combination with return).

For an intuition, see e.g. this answer – bind allows you to combine or chain strategies/plans/computations (that are in a context) together. As an example, let's use the Maybe context (or Maybe monad):

λ: let plusOne x = Just (x + 1)
λ: Just 3 >>= plusOne
Just 4

fmap also let's you chain computations in a context together, but at the cost of increasing the nesting with every step.[1]

λ: fmap plusOne (Just 3)
Just (Just 4)

That's why you need join: to squash two levels of nesting into one. Remember:

join :: m (m a) -> m a

Having only the squashing step doesn't get you very far. You need also fmap to have a monad – and return, which is Just in the example above.

[1]: fmap and (>>=) don't take their two arguments in the same order, but don't let that confuse you.

like image 79
mb21 Avatar answered Nov 01 '22 12:11

mb21