Is there such thing as a bidistributive? What function do I need here?

Question

I have code (in C# actually, but this question has nothing to do with C# specifically, so I will speak of all my types in Haskell-speak) where I am working inside of an Either a b. I then bind a function with a signature that in Haskell-speak is b -> (c, d), after which I want to pull c to the outside and default it in the left case, i.e. I want (c, Either a d). Now this pattern occurred many times one particular service I was writing so I pulled out a method to do it. However it bothers me whenever I just "make up" a method like this without understanding the correct theoretical underpinnings. In other words, what abstraction are we dealing with here?

I had a similar situation in some F# code where my pair and my either were reversed: (a, b) -> (b -> Either c d) -> Either c (a, d). I asked a friend what this was and he turned me on to traverse which made me very happy even though I have to make horrifically monomorphic implementations in F# due to the lack of typeclasses. (I wish I could remap my F1 in Visual Studio to Hackage; it is one of my primary resources for writing .NET code). The problem though is that traverse is:

class (Functor t, Foldable t) => Traversable t where
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

Which means it works great when you start with a pair and want to "bind" an either to it, but does not work when you start with an either and want to end up with a pair, because pair is not an Applicative.

However I thought about my first case more, the one that is not traverse, and realize that "defaulting c in the left case" can just be done with mapping over the left case, which changes the problem to having this shape: Either (c, a) (c, d) -> (c, Either a d) which I recognize as the pattern that we see in arithmetic with multiplication and addition: a(b + c) = ab + ac. I also remembered that the same pattern exists in Boolean algebra and in set theory (if memory serves, A intersect (B union C) = (A intersect B) union (A intersect C)). Clearly there is some abstract algebraic structure here. However, memory does not serve, and I could not remember what it was called. A little poking around on Wikipedia quickly solved this: these are the distributive laws. And joy, oh joy, Kmett has given us distribute:

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

It even has a cotraverse because it is dual to Travsersable! Lovely!! However, I noticed that there is no (,) instance. Uh oh. Because, yeah, where does the "default c value" come into all this? Then I realized, uh oh, I perhaps I need something like a bidistributive based on a bifunctor? perhaps dual to bitraversable? Conceptually:

class Bifunctor g => Bidistributive g where
    bidistribute :: Bifunctor f => f (g a b) (g a c) -> g a (f b c)

This seems to be the structure of the distributive law I am talking about. I can't find such a thing in Haskell which doesn't matter to me in and of itself since I am actually writing C#. However, the thing that is important to me is to not be coming up with bogus abstractions, and yet to recognize as many lawful abstractions in my code as possible, whether they are expressed as such or not, for my own understanding.

I currently have a .InsideOut(<default>) function (extension method) in my C# code (what a hack, right!). Would I be totally off-base to create a (yes, sadly monomorphic) .Bidistribute(...) function (extension method) to replace it and map the "default" for the left case into the left case before invoking it (or just recognize the "bidistributive" character of "inside out")?

Harmonious

I suspect you'll find Control.Lens.Prism interesting. The _Right prism represents a function Either a b -> Maybe b along with a function you don't really need, b -> Either a b. Once you have Either a (c,d), you can use the _Right . _1 Traversal to work with c. – Immemorial

Answer 1

bidistribute can't be implemented as such. Consider the trivial example

data Biconst c a b = Biconst c

instance Bifunctor (Biconst c) where
  bimap _ _ (Biconst c) = Biconst c

Then we'd have the specialisation

bidistribute :: Biconst () (Void, ()) (Void, ()) -> (Void, Biconst () () ())
bidistribute (Biconst ()) = ( ????, Biconst () )

There's clearly no way to fill in the gap, which would need to have type Void.

Actually, I think you really need Either there (or something isomorphic to it) rather than an arbitrary bifunctor. Then your function is just

uncozipL :: Functor f => Either (f a) (f b) -> f (Either a b)
uncozipL (Left l) = Left <$> l
uncozipL (Right r) = Right <$> l

It's defined in adjunctions (found using Hoogle).

Balancer

Is this a limitation of the category Hask, or of categories in general? – Harmonious

@KeithPinson it's a limitation of any category with an initial object. – Balancer

Sure, it's Bifunctor (Biconst c). – Balancer

Your Biconst needs three arguments. – Euphoria

So basically I have identified something that has the structure of the distributive laws, but only monomorphically to "and/pair" and "or/either", not categorically? – Harmonious

That's one way to put it. Though that doesn't mean it's “not categorical”. It's still pretty generic, just specific to the coproduct bifunctor. – Balancer

Answer 2

Based on @leftaroundabout's tip-off to look at adjunctions, in addition to uncozipL that he mentions in his answer, if we defer the "default the first value of the pair in the left case of either", we can also solve this with unzipR:

unzipR :: Functor u => u (a, b) -> (u a, u b)

Then it would still be necessary to map over the first element in the pair and pull out the value with something like either (const "default") id. The interesting thing about this is that it if you use uncozipL, you need to know that one of the things is a pair. If you use unzipR, you need to know that one is an either. In neither case do you use an abstract bifunctor.

Further, it seems that the pattern or abstraction that I'm looking for is a distributive lattice. Wikipedia says:

A lattice (L,∨,∧) is distributive if the following additional identity holds for all x, y, and z in L:

x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z).

which is exactly the property I have observed occuring in many different places.

Harmonious