Categories that want to be Arrows
This is me recording some halfformed thoughts that have been rattling around
in my head for the last week. They concern haskell’s
Arrow
typeclass; in particular it’s frustrating inability to be applied to types that
are in Category
but have no suitable implementation for arr
.
Consider something as simple as:
newtype Bij a b = Bij (a > b) (b > a)
a Category
instance is trivial, but an Arrow
instance is impossible, since
we would need to supply a b > a
given only a a > b
.
And yet most of the Arrow
methods (except arr
and &&&
) would be useful
for, and can be implemented in a very reasonable way, for the type above:
(Bij bc cb) *** (Bij xy yx) = Bij (bc *** xy) (cb *** yx)
first b = b *** id
second b = id *** b
We omit &&&
above because there isn’t a reasonable way to define a general
function :: (c > b) > (c' > b) > ((c,c') > b
(Bij bc cb) &&& (Bij bc' c'b) = Bij (bc &&& bc') undefined
…without something like a “restricted Arrow” where b
is constrained to
Monoid
. (but I’m getting ahead of myself; more on why I don’t think &&&
belongs in Arrow anyway below).
Or as a reductio ad absurdum, consider simply the following type:
newtype Flipped a b = Flipped (b > a)
is there any reason we shouldn’t have an Arrowlike class for which the above can be an instance?
None of this is new; it is a common complaint about Arrow: that it is overly complex (to the point of feeling arbitrary), while being extremely limited.
Won’t someone think of the Lenses?
Anyone who has tried to write a lens library has wished they could use the Arrow abstraction and slammed their head into a wall for at least an hour before giving up (except probably Edward Kmett). They just really ought to be Arrows.
Consider this lens representation:
newtype Lens a b = Lens (a > (b > a, b))
&&&
will give us the same problems as the (admittedly very similar) Bij
example above, but the other methods (***)
,first
and second
have good
implementations that would even preserve the Lens Laws (they are what you
would expect, but also have some foundations in CT)
An ArrowChoice implementation should also be no problem to implement while also being practically useful for lenses.
Again though, arr
presents a problem. One might even try to implement it as a
getter combined with a const/“readonly” setter continuation like:
arr f = Lens $ \a> (const a, f a)
But this violates the first Arrow law arr id = id
.
What is the nature of the problem?
From the above, it is obvious that we have problems with types where the flow of the computation is reversed from the order of the type variables. We can also probably find types that are sort of composite categories with a natural Category instance but no way to lift a pure computation.
But here’s another slightly different type of example; a computation with an associated cost, perhaps defining the “energy required” for a certain transformation:
data Transformation a b = T Int (a > b)
instance Category Transformation where
id = T 0 id
(T n f) . (T n' g) = T (n+n') (f . g)
Again, this type lends itself well to the parallel composition operators in
Arrow. For instance &&&
can capture that composing two transformations into a
single one that “fans out” carries the cost of the sum of their energy
requirements:
(T n f) &&& (T n' g) = T (n+n') (f g)
But the only logical implementation for arr
that we can define,
arr f = T 0 f
, breaks the law arr (f >>> g) = arr f >>> arr g
.
I started to do a survey of types on hackage that are Category
but not
Arrow
, but got burnt out at the stage where I had to actually look through
the code. Still this would be a great thing to do.
Default implementations without arr
If we rip arr
out of the Arrow class, we lose a lot of the default methods,
which are implemented in terms of some primitive “identitylike” functions
lifted to Arrow
with arr
. Here are those functions from the main class:
 second in terms of first, and vice versa:
\(x,y) > (y,x)
 &&& in terms of ***:
\b > (b,b)
and these are the helpers from ArrowChoice
:
 right in terms of left:
either Right Left
  in terms of +++:
either id id
It’s useful to try to think of implementing these primitive helpers in a given
Category, e.g. for some Category c
can we implement swap :: c (x,y) (y,x)
?
And for any Category where we can define swap
does it follow that we should
always be able to define the corresponding ArrowChoice
helper
swapE :: c (Either a b) (Either b a)
? If so, then they should be in the same
new subclass of Category, etc., etc.
I think these primitive helpers would probably be a good basis for the methods in a new class or set of classes to act as an Arrow alternative.
what about all those laws?
Most of the invariants that should hold for an Arrow are defined in terms of
arr
, but I think there are probably reasonable replacements, especially since
there was never anything particularly rigorous about the original Arrow laws.
For example, here are some relationships which I think should be expected to hold:
first id = second id = id
f *** g = first f >>> second g
(straight from default implementation)
but I’m not very good at this.
I suspect arr
is either the anchor that allows for a welldefined Arrow
class, or that all the laws are necessary to deal with the inclusion of arr
.
I hope the latter, and that a revised set of laws for Arrowwithoutarr would
look simpler and more abstract, like
Monoid.
About &&&
While an arrow that can “fan out” is useful, this doesn’t belong in this class for a number of reasons:

It doesn’t depend on
Category
at all and doesn’t even require a type of kind* > * > *
; since any Arrow can be made an Applicative anyway, this could be rewritten as(&&&) :: Applicative a=> a c > a c' > a (c,c')

it appears only once in the entire implementation (in the
Arrow
class declaration). The Arrow laws don’t require it, nor do any of the default class implementations use it. 
because there are many Arrowlike things which have no suitable implementation for such a function (a bit of circular logic, I know)
Concluding remarks
Arrow fails as a generallyuseful and coherent class for composing Categories vertically or “in parallel”, which is I think what people are looking for.
Maybe I can come up with some code soon for a better Arrow. Such a set of classes would hopefully be simpler, more flexible, and take advantage of the Arrow = Category + Applicative correspondence.
Also as I was finishing this I just stumbled on Causal Commutative Arrows (PDF) which look interesting.
Let me know your thoughts.
Update 2/13
Thanks for all the feedback everyone. From the comments I was pointed to Adam Megacz’s work on “generalized arrows”, and there are also a few comments on the haskell subreddit.