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

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.

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.