This is me recording some half-formed thoughts that have been rattling around
in my head for the last week. They concern haskell’s
typeclass; in particular it’s frustrating inability to be applied to types that
are in Category
but have no suitable implementation for
Consider something as simple as:
newtype Bij a b = Bij (a -> b) (b -> 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
&&&) 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
&&& above because there isn’t a reasonable way to define a general
:: (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)
example above, but the other methods
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.
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
(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
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
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
-- 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
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.
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
I hope the latter, and that a revised set of laws for Arrow-without-arr would
look simpler and more abstract, like
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
Categoryat 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
Arrowclass 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)
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.