Categories that want to be Arrows

This is me recording some half-formed 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 Arrow-like 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/“read-only” 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 “identity-like” 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 sub-class 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 well-defined 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 Arrow-without-arr 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 re-written 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 Arrow-like things which have no suitable implementation for such a function (a bit of circular logic, I know)

Concluding remarks

Arrow fails as a generally-useful 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.