The great thing about Arrows is you can write code that works for morphisms in different categories. For example, you can write code for functions and later use monad actions, or Kleisli arrows, instead. This is useful for error handling, and of course, adding IO.

If the underlying category uses isomorphisms (things with inverses) exclusively then it is called a ${\sl groupoid}$. Groupoids cause cracks to show in the Arrow abstraction. ${\tt Arrow}$ assumes that you can lift any function into the category you are writing code for, by requiring a definition for $\text{\tt arr~\char58{}\char58{}~\char40{}b~\char45{}\char62{}~c\char41{}~\char45{}\char62{}~a~b~c}$ function. This is out for groupoids, because not all functions are isomorphisms.

To remedy this, among other issues, Adam Megacz came up with Generalized Arrows.

In Dagger Traced Symmetric Monoidal Categories and Reversible Programming the authors show how to construct an reversible language out of the sum and product types along with related combinators to form a commutative semiring, at the type level. Both approaches are similar.

Error handling and partial isomorphisms are possible with Generalized Arrows. However, I find the algebraic approach of DTSMCRP more elegant. So I am going to try to get the same combinators as DTSMCRP but for an arbitrary category, as I would with Generalized Arrows.

 -- |An endofunctor for combining two morphisms class Category k => Ctor k constr | constr -> k where selfmap :: k a b -> k c d -> k (constr a c) (constr b d) 
With Ctor I can write a generic first or left
 -- |construct a new morphism with identity promote :: Ctor k op => k a b -> k (op a c) (op b c) promote = flip selfmap id

 

-- |construct a new morphism with identity with the arguments reversed swap_promote :: Ctor k op => k a b -> k (op c a) (op c b) swap_promote = selfmap id 

It is probably not clear at this point but depending on the type of {\sl op} we can get either the Arrow *** or ArrowChoice ||| function. If we make a semiring we can get them both. That’s what we are going to do.

I use type classes to encode the algebraic laws of semirings, with a class per law.
 -- |The absorbtion law => $x+0\leftrightarrow x$ class Ctor k op => Absorbs k op id | op -> k, op -> id where absorb :: k (op id a) a unabsorb :: k a (op id a)

 -- |The commutative law => $x+y \leftrightarrow y+x$ class Ctor k op => Commutative k op | op -> k where commute :: k (op a b) (op b a) -- |The assocative law => $(x + y) + z \leftrightarrow x + (y + z)$ class Ctor k op => Assocative k op | op -> k where assoc :: k (op (op a b) c) (op a (op b c)) unassoc :: k (op a (op b c)) (op (op a b) c) -- |The annihilation law => $0 * x \leftrightarrow 0$ class Ctor k op => Annihilates k op zero | op zero -> k where annihilates :: k (op zero a) zero 

-- |The distribution law => $(a + b) * c \leftrightarrow (a * c) + (b * c)$ class (Ctor k add, Ctor k multi) => Distributes k add multi | add multi -> k where distribute :: k (multi (add a b) c) (add (multi a c) (multi b c)) undistribute :: k (add (multi a c) (multi b c)) (multi (add a b) c) 

I collect these into groups of laws to make different algebraic structures.
 -- |Monoidial Category class class (Assocative k dot, Absorbs k dot id) => Monoidial k dot id | dot id -> k where

 -- |Commutative Monoidial Category class class (Monoidial k dot id, Commutative k dot) => CommutativeMonoidial k dot id | dot id -> k where 

-- |Semiring Category class class (CommutativeMonoidial k add zero, CommutativeMonoidial k multi one, Annihilates k multi zero, Distributes k add multi) => Semiring k add zero multi one | add zero multi one -> k where 

From which I regain Arrow and ArrowChoice functionality. Although, because of promote, I already had this capability.

 -- |Apply the multi monoid operator to the morphism and identity| first :: Semiring a add zero multi one => a b c -> a (multi b d) (multi c d) first = promote -- |Apply the multi monoid operator to identity and the morphism| second :: Semiring a add zero multi one => a b c -> a (multi d b) (multi d c) second = swap_promote -- |Apply the add monoid operator to the morphism and identity| left :: Semiring a add zero multi one => a b c -> a (add b d) (add c d) left = promote -- |Apply the add monoid operator to identity and the morphism| right :: Semiring a add zero multi one => a b c -> a (add d b) (add d c) right = swap_promote 

Many of the Generic Arrow functions can be included through absorption ( cancel, uncancel) and commutativity (swap). I’m not interested in adding looping at this point.

This also makes clear the relationship between Arrow and ArrowChoice as has been noted else where. Basically the same thing with a different endofunctor or constructor (Arrow uses product types, ArrowChoice uses sum types) as the monoid operator of a type level commutative monoid.

Making instances is a little onerous because of the use of multiparameter classes and the functional dependencies I have chosen. When I begin actually using these classes, it could result in massive changes. I am open to any suggestions on better designs.

The code was pulled from a literate haskell file Semiring.lhs. Here is a link on hackage.

Here is a link to a pretty latexed pdf of the source which includes some boring instances. semiring pdf