[Haskell-beginners] Constrained polymorphic functions as natural transformations

[Brent Yorgey]

Hi Matt,

On Fri, Dec 13, 2013 at 03:25:03PM +0000, Matt R wrote:
> 
> Note that you can't always characterize a type class by a single
> > function like this.  For example, consider class Foo ... There is no way
> > to pick functors f and g such that a Foo dictionary is
> > equivalent to  f a -> g a.
> >
> 
> I was wondering why the following wouldn't do the trick?
> 
> sig :: Foo a => Either Int a -> Either a Int
> sig (Left n) = Left (bar n)
> sig (Right a) = Right (baz a)

You have encoded a Foo dictionary as an Either Int a -> Either a Int
function, but that is very different than saying that having a Foo
dictionary is *equivalent* to having an Either Int a -> Either a Int
function.  They are not equivalent; in particular, you could have a
function which sends Left 5 to Right 6, which does not correpond to
anything in Foo.  Put another way, if you try to write a Foo instance
given only some unknown function of type (Either Int a -> Either a
Int), you will find that you cannot do it.  So my point stands that it
is not always possible to *characterize* a type class as a natural
transformation.

> > This doesn't really make sense.  If a natural transformation
> > consists of a family of arrows which all live in Hask_T,
> 
> 
> In this case, I think the family of arrows lives in Hask -- we can
> reinterpret our Hask endofunctors as instead being functors from Hask_T ->
> Hask. Then there's no requirement on our constrained polymorphic functions
> to commute with sig.
> 
> In your example function f, the two functors would be the identify functor
> "Id" and a constant functor "K Foo", and naturality is just saying that,
> for any function g: A -> B that satisfies show == show . f, then:
> 
> f = f . g
> 
> Which is clearly true for f.

Hmm, yes, this seems plausible.

> Am I still barking up the wrong tree? Apologies if so, but it *feels* like
> there should be something here, with the intuition that:
> 
> Functions that don't "inspect" their values ==> you can substitute values
> without fundamentally affecting the action of the function ==> natural
> transformations between Hask endofunctors.
> 
> Functions that don't inspect their values other than through a particular
> interface T ==> you can substitute values without fundamentally affecting
> the action of the function, providing your substitution is invisible
> through the interface T ==> Natural transformations between functors Hask_T
> -> Hask.

Yes, makes sense I think.

-Brent