Proposal: Add Compositor class as superclass of Arrow

[Cale Gibbard]

On 18/10/2007, Twan van Laarhoven <twanvl at gmail.com> wrote:
> Cale Gibbard wrote:
>
> > Hello, just thought I'd finally weigh in on this thread, having given
> > it a little thought.
> >
> > While there are a few nice examples of instances of Compositor, I
> > think I'd prefer to have (.) be what is currently fmap. Note that it
> > generalises ordinary function composition through the functor ((->)
> > e). Also you get a restricted form of the Arrow case through the
> > inclusion of an instance of Functor for ((~>) e) when (~>) is an
> > Arrow.
>
> The only argument for having (.) = fmap that I can think of is that the
> types happen to work out. Using (.)/(○) like this is, as far as I know,
> not standard usage in any way.

We're already not exactly like mathematics in many ways. Having (.) be
a symbol for functorial lifting is completely reasonable notationally.

>
> In category theory (.) is composition of morphisms, which is exactly
> what is proposed for the Category class. You have laws like
>  > id . f = f . id = f
> Of which only the first halve makes sense for fmap.
>
> Function composition forms a monoid, this is still true for composition
> of morphisms, not for functor application.

Well,  functor application is still a kind of monoid action, which is
basically what that associativity law says, and of course, you get an
analogue to f . id = f whenever your functor has an appropriate
analogue to id: the f on the right becomes something akin to pure f,
in the applicative or Hughes Arrow sense.

>
> Your argument for seeing (.) as composition on other functors such as
> lists is that these functors can all be considered a kind of
> 'functions'. For instance a list is a partial function from the
> naturals, a pair is a function from unit, etc. I don't think this holds
> for all functors. What about, say, State or STM?

Well, that part is slightly beside the point, but yeah, State and STM
are easy. It's just application of the function to the eventual result
of the computation, which is a kind of generalisation of what
composition does in the function case.

>
> > I've tried this out for a while, and it is actually rather nice to use
> > in many cases. Functor application is common enough that having a
> > one-character representation for it is great.
>
> Could you give an example where (.) = fmap actually makes sense for a
> non-reader functor, and has a clear advantage in readability and
> understandability over fmap/map/(<$>)?

Sure, it's useful almost anywhere you might make use of any one of
those. It's nice because it's visually quiet while still providing
some kind of notice that you're lifting the map in question using the
functor.

> With the Category definition you have for instance functional references:
>  > set (head . fst) :: a -> ([a],c) -> ([a],c)
>  > set (head . fst) 'a' ("dbc",123) == ("abc",123)

Clearly head and fst here are not the ones in the Prelude!

> And bijections:
>  > inverse (f . g) == inverse g . inverse f
>
>
> To summarize: fmap may generalize the type of (.), but that is about all
> it does. This usage is completely non-standard and, at least to me,
> unintuitive.

It becomes quite intuitive with a little use. You eventually just
regard it as being the same as fmap, but slightly nicer in that the
fusion law is made transparent by the notation. It's actually already
quite common to define notations in mathematics where application of a
function to a structure is functorially lifted. Probably the most
common case of this is with the powerset functor. f(S), where S is a
subset of the domain of f typically is used to mean the image of S
under f: {y : y = f(s), s in S}. Rather than redefining function
application polymorphically, this just uses a dot to identify that
lifting is taking place.

When I first noticed this back several months ago, I was a bit
hesitant to propose it. However, functorial application (especially
for lists) and function composition being arguably the two most
important operations in functional programming, it's rather nice to
see that they are really instances of the same thing, and to be able
to give them both the nicest possible operator symbol.

 - Cale