Closed tomjaguarpaw closed 5 years ago
@tomjaguarpaw: The names distribute
/distributive
come from "distributive law" in category theory
In Haskell terms, a the general notion of a distributive law is a function of type forall a . f (g a) -> g (f a)
where f
and g
are usually Monad
s and this function has to obey certain rules.
The Distributive
type-class from the distributive
package is a special case of that general concept and the distribute
function from pipes
is another special case of that general concept, but neither descends from the other. In other words, they are siblings of each other.
I see. Is sequence :: (Traversable t, Applicative f) => t (f a) -> f (t a)
also an example of a distributive law?
@tomjaguarpaw: So to satisfy all of the laws for a distributive law then technically both t
and f
have to also be Monad
s. I will actually replace f
with s
for consistency with the Wikipedia article.
In Haskell terms, if sequenceA
were a distributive law and t
and s
were both Monad
s then the laws it would need to satisfy are:
-- using: sequenceA :: (Traversable t, Applicative s) => t (s a) -> s (t a)
join . fmap sequenceA . sequenceA = sequenceA . fmap join
:: (Traversable t, Monad s) => t (s (s a)) -> s (t a)
fmap join . sequenceA . fmap sequenceA = sequenceA . join
:: (Traversable t, Monad t, Applicative s) => t (t (s a)) -> s (t a)
pure = sequenceA . fmap pure
:: (Traversable t, Applicative s) => t a -> s (t a)
fmap pure = sequenceA . pure
:: (Traversable t, Applicative t, Applicative s) => s a -> s (t a)
Indeed, some of these laws match the laws for the Traversable
class. For example, the third law above is a generalization of the following law for sequenceA
:
sequenceA . fmap Identity = Identity
If you replace Identity
with pure
and swap both sides you get:
pure = sequenceA . fmap pure
Similarly, for this law for sequenceA
:
sequenceA . fmap Compose = Compose . fmap sequenceA . sequenceA
... if you swap both sides and replace Compose
with join
, you get:
join . fmap sequenceA . sequenceA = sequenceA . fmap join
... which is the first distributive law. I'm guessing with some effort you could relate the two laws more precisely.
I haven't actually sat down and checked if all Traversable
instances must satisfy the distributive laws, but my hypothesis is that sequenceA
is probably a distributive law for the cases where s
and t
and are both Monad
s.
Interesting. Thanks very much for the explanation. So it sounds like there are two different specific uses of this same general notion of "distributive" floating around.
@tomjaguarpaw: You're welcome! 🙂
pipes
hasdistribute
with typeThat is, we can push a
Proxy
in through anMFunctor
. As far as I can tell this name was introduced by @Gabriel439 in a post in 2013, appealing to the concept of "distributive functor in the category of monads". I can't find any references to such a thing that I can understand. The best I've found is Linearly Distributive Functors which doesn't help much.The name
distribute
has made its way intostreaming
andhedgehog
where it retains the meaning of pushing something in through anMFunctor
.On the other hand we have a
distributive
package with a (*
-level)distribute
operation. It has typeThat is, we can pull any
Distributive
out through aFunctor
. This package does not provide any references for the name either.At this point I'm wondering whether pipes got the name wrong at the outset. It's also possible that
distributive
got the name wrong. Without a reference to the original category theory terminology I can't tell. However,distributive
as been around for a couple more years thandistribute
in pipes so it feels more likely to be correct. I have opened an issue ondistributive
for clarification.