3

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?

dbanas
  • 1,707
  • 14
  • 24
  • You appear to have the meaning of a superclass constraint backwards. e.g. there are `Applicative`s which are not `Monad`s, and we have `class Applicative f => Monad f`. (And see also [`distributeRep`](https://hackage.haskell.org/package/adjunctions-4.4/docs/Data-Functor-Rep.html#v:distributeRep) which witnesses the inclusion of `Representable` in `Distributive`.) – Daniel Wagner Mar 26 '18 at 17:50
  • I know it has been a while, but anyway: I have rewritten my answer into something that hopefully will be more informative. – duplode Jun 15 '19 at 00:04

1 Answers1

2

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).

Community
  • 1
  • 1
duplode
  • 33,731
  • 7
  • 79
  • 150
  • I never thought about the fact that the arrow is the wrong way around in a class declaration! Sounds like the Haskell committee made a mistake back in the day. – dfeuer Jun 15 '19 at 19:01
  • 2
    @dfeuer I feel both choices are defensible. Personally, I find `Applicative f <= Monad f` a little awkward because `<=` also suggests ordering, which might justify choosing to write it as `Monad f <= Applicative f` instead. It is interesting to note that [Wadler's original propsal for type classes](http://homepages.inf.ed.ac.uk/wadler/papers/class-letter/class-letter.txt) didn't actually use any sort of arrow to introduce subclassing in a class declaration. – duplode Jun 15 '19 at 20:23
  • 1
    Another option would have been to swap the positions: `class Integral a => (Real a, Enum a) where ...`. That's not too far from Wadler. – dfeuer Jun 15 '19 at 22:38