Would a type class "between" Category and Arrow make sense?

Question

Often you have something like an Applicative without pure, or something like a Monad, but without return. The semigroupoid package covers these cases with Apply and Bind. Now I'm in a similar situation concerning Arrow, where I can't define a meaningful arr function, but I think the other functions would make perfect sense.

I defined a type that holds a function and it's reverse function:

import Control.Category

data Rev a b = Rev (a -> b) (b -> a)

reverse (Rev f g) = Rev g f
apply (Rev f _) x = f x
applyReverse (Rev _ g) y = g y
compose (Rev f f') (Rev g g') = Rev ((Prelude..) f g) ((Prelude..) g' f') 

instance Category Rev where
  id = Rev Prelude.id Prelude.id
  (.) x y = compose x y 

Now I can't implement Arrow, but something weaker:

--"Ow" is an "Arrow" without "arr"
class Category a => Ow a where
  first :: a b c -> a (b,d) (c,d)
  first f = stars f Control.Category.id

  second :: a b c -> a (d,b) (d,c)
  second f = stars Control.Category.id f

  --same as (***)
  stars :: a b c -> a b' c' -> a (b,b') (c,c')

 ...
 import Control.Arrow 

 instance Ow Rev where
    stars (Rev f f') (Rev g g') = Rev (f *** g) (f' *** g')  

I think I can't implement the equivalent of &&&, as it is defined as f &&& g = arr (\b -> (b,b)) >>> f *** g, and (\b -> (b,b)) isn't reversable. Still, do you think this weaker type class could be useful? Does it even make sense from a theoretical point of view?

Answer 1

This approach was explored in "There and Back Again: Arrows for invertible programming": http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.153.9383

For precisely the reasons you're running into, this turned out to be a bad approach that wasn't picked up more widely. More recently, Tillmann Rendel produced a delightful approach to invertible syntax that substituted partial isomorphisms for biarrows ( http://www.informatik.uni-marburg.de/~rendel/rendel10invertible.pdf ) . This has been packaged up on hackage for folks to use and play with: http://hackage.haskell.org/package/invertible-syntax

That said, I think an arrow without arr makes a certain amount of sense. I just don't think that such a thing is an appropriate vehicle to capture invertible functions.

Edit: There's also Adam Megacz's Generalized Arrows (http://www.cs.berkeley.edu/~megacz/garrows/). These are maybe not useful for invertible programming either (though the basic typeclass does seem to be inveritble), but they do have uses in other situations where arr is too strong, but other arrow operations may make sense.

Answer 2

From a Category Theory standpoint, the Category type class describes any category whose arrows can be describedn straightforwardly in Haskell by a type constructor. Almost any additional feature you want to build on top of this, in the form of new primitive arrows or arrow-building functions, will make sense to some extent if you can implement it using total functions. The only caveat is that adding expressive power can break other requirements, as often happens with arr.

Your specific example of invertible functions describes a category where all arrows are isomorphisms. In a shocking twist of the completely and utterly expected, Edward Kmett already has an implementation of this on Hackage.

The arr function roughly amounts to a functor (in the category theory sense) from Haskell functions to the Arrow instance, leaving objects the same (i.e., the type parameters). Simply removing arr from Arrow gives you... something else, which is probably not very useful on its own, without at least adding the equivalents of arr fst and arr snd as primitives.

I believe that adding primitives for fst and snd, along with (&&&) to build a new arrow from two inputs, should give you a category with products, which is absolutely sensible from a theoretical point of view, as well as not being compatible with the invertible arrows you're using for the reasons you've found.