Reilly Hayes rfh at reillyhayes.com
Thu Mar 23 12:20:10 EST 2006

```I've been taking a close look at the paper "Arrows and Computation" by
Ross Paterson.  It's not relevant to my question, but I'm doing this
because I think that Arrows may be a useful abstraction for a problem I
have (I need to both construct a computational pipeline AND perform a
computation over the pipeline itself).

The paper is published as Chapter 10 in "The fun of Programming" and is
also available here: http://www.soi.city.ac.uk/~ross/papers/fop.html

My question originates with the statement at the bottom of page 205 (the
5th page of the paper) regarding the behavior of the function 'first':
" ... while 'first' routes the state through f:".  My problem is that
this statement appears to be erroneous.  My reading of the code would
indicate that 'first' does not do this at all.  The state portion of the
Arrow remains unaltered.  Nor does it even seem desirable for 'first' to
have an impact on the state portion of the Arrow, as I would think that
this would preclude using 'first' and 'second' to lift binary operators
into the Arrow.  So what is it that am I missing?

The relevant code is as follows.  Paterson used Greek letters where I
have used Latin.  I represented his product operator with the letter x,
requiring surrounding backquotes.  If there are other changes to his
code I am unaware of them and they are an error on my part.

class Arrow a where
pure :: (b -> c) -> a b c
(>>>) :: a b c -> a c d -> a b d
first :: a b c -> a (b,d) (c,d)

x :: (a -> a') -> (b -> b') -> (a,b) -> (a',b')
(f `x` g) ~(a,b) = (f a, g b)

assoc :: ((a,b),c) -> (a,(b,c))
assoc ~(~(a,b),c) = (a,(b,c))

unassoc :: (a,(b,c)) -> ((a,b),c)
unassoc ~(a,~(b,c)) = ((a,b),c)

newtype State s i o = ST ((s,i) -> (s,o))

instance Arrow (State s) where
pure f  = ST (id `x` f)
(ST f) >>> (ST g) = ST (g . f)
first (ST f) = ST (assoc . (f `x` id) . unassoc)

-Reilly Hayes

```