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")?
bidistribute
can't be implemented as such. Consider the trivial exampleThen we'd have the specialisation
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 justIt's defined in
adjunctions
(found using Hoogle).