Proposal: Add Compositor class as superclass of Arrow

[Twan van Laarhoven]

apfelmus wrote:

> Twan van Laarhoven wrote:
> 
>> My proposal would be the following. The important things are that:
>>  1. It incorporates Conal's deep arrow,
>>  2. as well as everything that is needed for functional 
>> references/lenses and bijective/invertible functions.
> 
> 
> I'd opt for more research for that proposal to answer the following 
> essential questions

Indeed. I have started a project/library at
   http://code.haskell.org/category/
for this purpose.

It contains implementations of functional references and invertible 
functions as test subjects, and the laws are tested using quickcheck.

> - Do the classes correspond to already-known categories, i.e. are the 
> class names optimal?
> - What laws do we expect to hold?

I have found an example of a law you'd expect to hold, that doesn't. 
This is: left id == id. For functional references it is not too hard to 
implement 'left', but it does not satisfy that law, since for the set 
operation you need two values with the same 'side'. There is no way to 
get a 'left' value from
     set (left id) (Left 'a') (Right 'b') = Right 'b'
because a might differ from the result type for functions other than id, yet
     set id (Left 'a') (Right 'b') = Left 'a'


> - Are the signatures minimal, i.e. does there exist a smaller set of 
> combinators that still achieves the intended effect? Are the signatures 
> complete, i.e. can the intended effect always expressed with the given 
> combinators?

The big culprit here are the structural combinators: mirror, swap, 
assoc* and most of CategoryFun (and id). All of these can be written 
using 'arrInv'. So the questiong becomes: Are there arrows that allow 
structural manipulation of functions, products and sums, that do not 
support all bijections?

Similairly, injection (inl/inr) and selection (fst/snd) can be written 
using 'arrRef'. So again: Are there arrows that do not contain the 
functional references, that do allow inl/inr and fst/snd.

A likely candidate for both is Conal's DeepArrow.

Another thing I don't like about these functions is that they are 
specific to (,) and Either. This becomes important once you add 
syntactic sugar. Case expressions can only be desugared when you have 
'arrInv'.

Perhaps there can be a superclass of InvArrow with the same type 
signature, but with the additional requirement that it may only be used 
for structural isomorphisms.

> - Plenty and useful examples? At least enough examples that fit in the 
> fine grained hierarchy but cannot be fit into a coarser grained one so 
> as to demonstrate the necessity of a fine grained hierarchy.
> 
> These questions likely have nice answers for many of the classes, but 
> CategoryZero, CategoryPlus

CategoryZero and CategoryPlus just give a monoid structure, exactly the 
same as MonadZero and MonadPlus. They could be put into a single class 
like the current MonadPlus. The only reason we need these things are 
needed is because Haskell doesn't allow universaly quantified contexts
    f :: CategoryPlus cat => ...
    f :: (Category cat, forall a b. Monoid (cat a b)) => ...

 > .. CategoryChoice ..

As mentioned before, CategoryChoice is the dual to CategoryPair. So it 
is just as reasonable.

 > and in particular CategoryFun may be hard nuts.

(note: I am brainstorming here)

Asside from result, curry, uncurry and funR (aka flip) which can all be 
expressed with arrInv/arrIso, there are funF and funS which can not. I 
see no sane way to implement them in anything below ArrowFun. Perhaps 
these two functions can together form a class

   class CategoryPair cat => CategoryFunPair cat where
         funF :: cat (c -> a, b) (c -> (a, b))
         funS :: cat (a, c -> b) (c -> (a, b))

         funS = result swap . funF . swap

And dually

   class CategoryChoice cat => CategoryFunChoice cat where
         funL :: cat (Either (c -> a) b) (c -> (Either a b))
         funR :: cat (Either a (c -> b)) (c -> (Either a b))

I expect the problem with these classes comes from the fact that they 
use *two* categories, cat and (->), and a monad. Generalizing to other 
monads gives for instance

         funLst :: cat [c -> a] (c -> [a])

Alternatively, it's one category and two monads / applicative functors. 
Then we get:

         sequence :: cat (f (g a)) (g (f a))

Now the question becomes: does sequencing in a category cat ever differ 
from sequencing in (->)? Clearly it can be a subset, but is there 
anything other than the cases:
     - f and g commute (f . g = g . f), sequence can be done in IsoArrow
     - g only sequences through f, we may need a new class for this; 
otherwise Arrow will do. For some cases RefArrow might be enough.
     - f and g don't commute, nothing happens.

Again I look at Conal for a likely source of examples. Look at 
Data.Traversable.sequence for this function in (->).


> Also, the proposed subclass chain InvArrow => RefArrow => FunArrow may 
> be cumbersome in practice since it would mean to define three functions 
> instead of just  arr  when declaring an Arrow.

There are examples of all three, and I think it is important to ensure 
that the instances of the superclasses are available for the subclasses. 
Otherwise changing a function from, say, FunArrow to RefArrow does not 
make it more general.

Twan