A newbie question about Arrows.

Ross Paterson ross@soi.city.ac.uk
Mon, 6 Jan 2003 11:14:36 +0000


On Mon, Jan 06, 2003 at 11:02:32AM +0100, Nicolas Oury wrote:
> * Why is made the choice to use (,) as Cartesian in first?

It's certainly possible to define a more general interface, and the
theoretical work does.  However the arrow interface is already very
general, and the question is whether any programs can be written to
the more general interface.  Magnus Carlsson has some ideas along
these lines (see http://www.cse.ogi.edu/~magnus/ProdArrows/).

I will quibble with some of the details, though:

> Can't we write something like :
> 
> class Cartesian p where
>     pair :: a -> b -> (p a b)
>     projLeft :: (p a b) -> a
>     projRight :: (p a b) -> b
> 
> class Cartesian pair => Arrow ar where
> 	arr ::( ar pair a b) -> (ar pair a b)
> 	(>>>) :: (ar pair a b) -> (ar pair b c) -> (ar pair a c)
> 	first :: (ar pair a b) -> (ar (pair a d) (pair b d))

First, you don't need pair for the first two, so one might define

class PreArrow ar where
	arr :: (a -> b) -> ar a b
	(>>>) :: ar a b -> ar b c -> ar a c

Second, we don't really need pair to be quite as product-like.  What we
really want is for it to be "monoidal", i.e. a binary functor with a
unit type u and isomorphisms

	type Iso a b = (a -> b, b -> a)

	class Monoidal pair u | pair -> u where
		unitl :: Iso (pair u a) a
		unitr :: Iso (pair a u) a
		assoc :: Iso (pair a (pair b c)) (pair (pair a b) c)

satisfying a few axioms.  For products (pretending that Haskell has
products), we use pair = (,), u = (), unitl = fst and unitr = snd.
For sums (useful for asynchronous event streams), pair = Either and
u = an empty type.

Then one could define

	class (PreArrow ar, Monoidal p u) => GenArrow ar p u where
		first :: ar a b -> ar (p a c) (p b c)

which would subsume Arrow and ArrowChoice.  Some of the "Theoretical
Aside"s in the Arrow Notation paper discuss this possibility.

> * Why is made the choice of first as being a base function?
> 
> We have
> 
> first f = f *** (arr id)
> 
> second f = (arr id) *** f
> 
> So they could be define from (***).
> 
> Moreover,  the definition of f *** with first and second creates an 
> order in the use of the f and g (first f >>> second g) whereas it seems 
> that (***) is a "parallel"  operator.

This is discussed in John Hughes's paper (end of 4.1).  The essential
point is that the appearance of symmetry is illusory.  For many arrows,
including Kleisli arrows of common monads, the ordering is there, even
though the notation *** hides it.