How to write a Representable instance using only Distributive properties?

323 views Asked by At

Say I've got a Distributive instance written for some complex custom type, Foo. Is it possible to write Foo's Representable instance using only the properties available from its Distributive instance? And, if not, then why is Distributive a superclass of Representable?

1

There are 1 answers

3
duplode On

The superclass relationship between Distributive and Representable...

class Distributive f => Representable f where

... means that if f is a Representable, then it also must be a Distributive, and not the other way around. When used for subclassing, => should be read as "is a prerequisite of", rather than "implies". (This is, in fact, opposite to how it is when => is used for constraints in type signatures. Purescript uses <= for subclassing for this very reason.)

For most other pairs of superclass and subclass, the story would end here. Distributive and Representable, however, have a special relationship, in that Distributive functors are actually representable, as stated by the documentation of both Distributive...

Categorically every Distributive functor is actually a right adjoint, and so it must be Representable endofunctor and preserve all limits. This is a fancy way of saying it isomorphic to (->) x for some x.

... and Representable:

A Functor f is Representable if tabulate and index witness an isomorphism to (->) x.

Every Distributive Functor is actually Representable.

Every Representable Functor from Hask to Hask is a right adjoint.

The hierarchy is set up the way it is, with Distributive as the superclass, because Distributive is meant to have a simpler interface which is expressible in Haskell 98, unlike Representable (which uses a type family) and Adjunction (which is a multi-parameter type class). From a more conceptual point of view, while the distributive laws imply that every Distributive is representable, they are not enough for figuring out what the representation is. Getting our hands on the representation requires specifying it, either directly (as in Representable) or indirectly (as in Adjunction).