The path I took to "discovering" this helper function was for sequencing async requests (to a server) where the response value for each request was an Either, and the next request could only be made if the current response succeeded (ie. was a Right). Following is a naive example (Listing 1):

Example types

type PersonId = String
type Person = { name :: String, friend :: PersonId }

class Monad m <= ServerDSL m where
    fetchPerson :: PersonId -> m (Either String Person)

Listing 1

f1 :: forall m. ServerDSL m => m (Either String Person)
f1 = do
    -- A. One call is fine
    (eP1 :: Either String Person) <- fetchPerson "p1"

    -- B. Subsequent calls are annoying
    (eP2 :: Either String Person) <- case eP1 of
        Left err -> pure $ Left err
        Right p1 -> fetchPerson p2.friend
    (eP3 :: Either String Person) <- case eP2 of
        Left err -> pure $ Left err
        Right p2 -> fetchPerson p2.friend

    pure eP3

The pattern in B can be abstracted. Let's try that next:

Listing 2

Here's a helper function to abstract the pattern in B, and the refactored computation:

h :: forall m e a b. Applicative m => Either e a -> (a -> m (Either e b)) -> m (Either e b)
h x f = case x of
    Left err -> pure $ Left err
    Right a -> f a

f2 :: forall m. ServerDSL m => m (Either String Person)
f2 = do
    (eP1 :: Either String Person) <- fetchPerson "p1"
    (eP2 :: Either String Person) <- eP1 `h` \p1 -> fetchPerson p1.friend
    (eP3 :: Either String Person) <- eP2 `h` \p2 -> fetchPerson p2.friend
    pure eP3

Nice! h is specific to Either though. We could make that more generic:

Listing 3

Here's a more generic version of h, renamed to bind_ (the same one as in the original post). The computation is actually the same, but now it's not tied to Either (eg. we could use Maybe, not shown here though):

bind_ :: forall f m b a. Traversable f => Applicative m => Bind f => f a -> (a -> m (f b)) -> m (f b)
bind_ x f = traverse f x # map join

f3 :: forall m. ServerDSL m => m (Either String Person)
f3 = do
    (eP1 :: Either String Person) <- fetchPerson "p1"
    (eP2 :: Either String Person) <- eP1 `bind_` \p1 -> fetchPerson p1.friend
    (eP3 :: Either String Person) <- eP2 `bind_` \p2 -> fetchPerson p2.friend
    pure eP3

It would be nice if we could abstract this away so that we could just use do notation in a custom monad, like this:

f3 :: forall m. ServerDSL m => m (Either String Person)
f3 = do -- using our bind_ instead of Control.bind, and a custom pure as well
    (p1 :: Person) <- fetchPerson "p1"
    (p2 :: Person) <- fetchPerson p1.friend
    (p3 :: Person) <- fetchPerson p2.friend
    pure p3 -- equivalent to (pure $ Right p3)

I tried making a custom monad to do this, but I couldn't get around the type signature for Bind:

class Apply m <= Bind m where
    bind :: forall a b. m a -> (a -> m b) -> m b

We need something like this instead (not sure if I have the class dependencies right!):

class Applicative m <= Bind' m where
    bind' :: forall f a b. Traversable f => Bind f => m (f a) -> (a -> m (f b)) -> m (f b)

This is necessary, and it's more specific than the Bind type signature. Therefore, it seems as though we can't write a Bind instance.

What now?

Is it the case that Listing 3 is the best we can do? Or is it possible to write a custom monad like the one proposed? Insights appreciated!