Is there a name for this higher-level "bi" version of distribute in Haskell?

Question

I have a Bitraversable called t that supports this operation:

someName :: Monad m => (t (m a) (m b) -> c) -> m (t a b) -> c

In other words, it's possible to take a function that accepts two monads packaged into the bitraversable and turn it into a mapping that accepts a single monad containing a bitraversable without the monad layer. This is something like a bitraversable and higher-level version of distribute; the type signature is similar to this:

\f -> \x -> f (distribute x)
  :: (Distributive g, Functor f) => (g (f a) -> c) -> f (g a) -> c

My questions:

1. Is there a standard name for this "higher-level" version of distribute that works on functions that accept distributives rather than distributives themselves?

2. Is there a name for the bitraversable version?

3. Does it work with every bitraversable/functor/monad/whatever, or are there restrictions?

Answer 1

As per @Noughtmare, your "higher level" functions someName and distribute are just written in continuation passing style. These generally aren't worth additional names, because they are just right function compositions:

highLevelDistribute = (. distribute)

Practically speaking, anywhere you want to call highLevelDistribute on an argument:

highLevelDistribute f

this expression is equivalent to:

f . distribute

and even if you're using highLevelDistribute as a first-class value, it's just not that hard to write and understand the section (. distribute).

Note that traverse and sequenceA are a little different, since we have:

sequenceA = traverse id

You could make an argument that this difference doesn't really warrant separate names either, but that's an argument for another day.

Getting back to someName, it's a CPS version of:

someOtherName :: m (t a b) -> t (m a) (m b)

which looks like a bifunctor analogue of distribute:

distribute :: (Distributive g, Functor f) => f (g a) -> g (f a)

So, I'd suggest inventing a Bidistributive to reflect this, and someOtherName becomes bidistribute:

class Bifunctor g => Bidistributive g where
  {-# MINIMAL bidistribute | bicollect #-}
  bidistribute :: Functor f => f (g a b) -> g (f a) (f b)
  bidistribute = bicollect id
  bicollect :: Functor f  => (a -> g b c) -> f a -> g (f b) (f c)
  bicollect f = bidistribute . fmap f

Again, your "higher level" someName is just right-composition:

someName = (. bidistribute)

Reasonable laws for a Bidistributive would probably include the following. I'm not sure if these are sufficiently general and/or exhaustive:

-- naturality
bimap (fmap f) (fmap g) . bidistribute = bidistribute . fmap (bimap f g)

-- identity
bidistribute . Identity = bimap Identity Identity

-- composition
bimap Compose Compose . bidistribute . fmap bidistribute = bidistribute . Compose

For your question #3, not all Bitraversables are Bidistributive, for much the same reason that not all Traversables are Distributive. A Distributive allows you to "expose structure" under an arbitrary functor. So, for example, there's no Distributive instance for lists, because if there was, you could call:

distribute :: IO [a] -> [IO a]

which would allow you to determine if a list returned by an IO action was empty or not, without executing the IO action.

Similarly, Either is Bitraversable, but it can't be Bidistributive, because if it was, you'd be able to use:

bidistribute :: IO (Either a b) -> Either (IO a) (IO b)

to determine if the IO action returned a Left or Right without having to execute the IO action.

One interesting thing about bidistribute is that the "other functor" can be any Functor; it doesn't need to be an Applicative. So, just as we have:

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
distribute :: (Distributive g, Functor f) => f (g a) -> g (f a)

we have:

bisequence :: (Bitraversable t, Applicative f) => t (f a) (f b) -> f (t a b)
bidistribute :: (Bidistributive g, Functor f) => f (g a b) -> g (f a) (f b)

Intuitively, sequencing needs the power of an applicative functor f to be able to "build" the f (t a) from a traversal of its functorial f a "parts", while distribution only needs to take the f (g a) apart. In practical terms, this means that sequencing typically looks like this:

-- specialized to t ~ []
sequenceA :: [f a] -> f [a]
sequenceA (f:fs) = (:) <$> f <*> fs  -- need applicative operations

while distribution typically looks like this:

-- specialized to g ~ (->) r
distribute :: f (r -> a) -> (r -> f a)
distribute f r = fmap ($ r) f  -- only need fmap

(Technically, according to the documentation for Data.Distributive, the Distributive class only requires a Functor rather than some coapplicative class because of the lack of non-trivial comonoids in Haskell. See this SO answer.)