Search code examples
haskelltypeclassarrowscategory-abstractions

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

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?

Solution

  • 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.