Monads with Join() instead of Bind()

Question

Monads are usually explained in turns of return and bind. However, I gather you can also implement bind in terms of join (and fmap?)

In programming languages lacking first-class functions, bind is excruciatingly awkward to use. join, on the other hand, looks quite easy.

I'm not completely sure I understand how join works, however. Obviously, it has the [Haskell] type

join :: Monad m => m (m x) -> m x

For the list monad, this is trivially and obviously concat. But for a general monad, what, operationally, does this method actually do? I see what it does to the type signatures, but I'm trying to figure out how I'd write something like this in, say, Java or similar.

(Actually, that's easy: I wouldn't. Because generics is broken. ;-) But in principle the question still stands...)

---

Oops. It looks like this has been asked before:

Monad join function

Could somebody sketch out some implementations of common monads using return, fmap and join? (I.e., not mentioning >>= at all.) I think perhaps that might help it to sink in to my dumb brain...

Answer 1

Without plumbing the depths of metaphor, might I suggest to read a typical monad m as "strategy to produce a", so the type m value is a first class "strategy to produce a value". Different notions of computation or external interaction require different types of strategy, but the general notion requires some regular structure to make sense:

• if you already have a value, then you have a strategy to produce a value (return :: v -> m v) consisting of nothing other than producing the value that you have;
• if you have a function which transforms one sort of value into another, you can lift it to strategies (fmap :: (v -> u) -> m v -> m u) just by waiting for the strategy to deliver its value, then transforming it;
• if you have a strategy to produce a strategy to produce a value, then you can construct a strategy to produce a value (join :: m (m v) -> m v) which follows the outer strategy until it produces the inner strategy, then follows that inner strategy all the way to a value.

Let's have an example: leaf-labelled binary trees...

data Tree v = Leaf v | Node (Tree v) (Tree v)

...represent strategies to produce stuff by tossing a coin. If the strategy is Leaf v, there's your v; if the strategy is Node h t, you toss a coin and continue by strategy h if the coin shows "heads", t if it's "tails".

instance Monad Tree where
  return = Leaf

A strategy-producing strategy is a tree with tree-labelled leaves: in place of each such leaf, we can just graft in the tree which labels it...

  join (Leaf tree) = tree
  join (Node h t)  = Node (join h) (join t)

...and of course we have fmap which just relabels leaves.

instance Functor Tree where
  fmap f (Leaf x)    = Leaf (f x)
  fmap f (Node h t)  = Node (fmap f h) (fmap f t)

Here's an strategy to produce a strategy to produce an Int.

Toss a coin: if it's "heads", toss another coin to decide between two strategies (producing, respectively, "toss a coin for producing 0 or producing 1" or "produce 2"); if it's "tails" produce a third ("toss a coin for producing 3 or tossing a coin for 4 or 5").

That clearly joins up to make a strategy producing an Int.

What we're making use of is the fact that a "strategy to produce a value" can itself be seen as a value. In Haskell, the embedding of strategies as values is silent, but in English, I use quotation marks to distinguish using a strategy from just talking about it. The join operator expresses the strategy "somehow produce then follow a strategy", or "if you are told a strategy, you may then use it".

(Meta. I'm not sure whether this "strategy" approach is a suitably generic way to think about monads and the value/computation distinction, or whether it's just another crummy metaphor. I do find leaf-labelled tree-like types a useful source of intuition, which is perhaps not a surprise as they're the free monads, with just enough structure to be monads at all, but no more.)

PS The type of "bind"

(>>=) :: m v -> (v -> m w) -> m w

says "if you have a strategy to produce a v, and for each v a follow-on strategy to produce a w, then you have a strategy to produce a w". How can we capture that in terms of join?

mv >>= v2mw = join (fmap v2mw mv)

We can relabel our v-producing strategy by v2mw, producing instead of each v value the w-producing strategy which follows on from it — ready to join!

Answer 2

join = concat -- []
join f = \x -> f x x -- (e ->)
join f = \s -> let (f', s') = f s in f' s' -- State
join (Just (Just a)) = Just a; join _ = Nothing -- Maybe
join (Identity (Identity a)) = Identity a -- Identity
join (Right (Right a)) = Right a; join (Right (Left e)) = Left e; 
                                  join (Left e) = Left e -- Either
join ((a, m), m') = (a, m' `mappend` m) -- Writer
-- N.B. there is a non-newtype-wrapped Monad instance for tuples that
-- behaves like the Writer instance, but with the tuple order swapped
join f = \k -> f (\f' -> f' k) -- Cont

Answer 3

Calling fmap (f :: a -> m b) (x ::ma) produces values (y ::m(m b)) so it is a very natural thing to use join to get back values (z :: m b).

Then bind is defined simply as bind ma f = join (fmap f ma), thus achieving the Kleisly compositionality of functions of (:: a -> m b) variety, which is what it is really all about:

ma `bind` (f >=> g) = (ma `bind` f) `bind` g              -- bind = (>>=)
                    = (`bind` g) . (`bind` f) $ ma 
                    = join . fmap g . join . fmap f $ ma

And so, with flip bind = (=<<), we have

    ((g <=< f) =<<)  =  (g =<<) . (f =<<)  =  join . (g <$>) . join . (f <$>)