Question about "Arrows and Computation" by Paterson
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
On Thu, Mar 23, 2006 at 09:20:10AM -0800, Reilly Hayes wrote:
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.
Try this picture: (s,(b,d)) | | unassoc v ((s,b), d) | | f | x | id v v ((s',c), d) | | assoc v (s',(c,d)) The state type is not changed, but its value can be. It is the second part of the input (d) that is passed through.
On Thu, 2006-03-23 at 17:37 +0000, Ross Paterson wrote:
Try this picture:
(s,(b,d)) | | unassoc v ((s,b), d) | | f | x | id v v ((s',c), d) | | assoc v (s',(c,d))
The state type is not changed, but its value can be. It is the second part of the input (d) that is passed through.
Thank you. Your diagram was very helpful. I was tracing the values correctly through unassoc and assoc but missing the point of the exercise. The problem was that I entirely misunderstood the statement, " ... while 'first' routes the state through f." I took it to mean that, in the State Arrow, you were using 'first' as a mechanism to provide access to State. Now I understand state *must* be threaded through whichever half of the input tuple is going to be acted on. In retrospect, it's obvious. -reilly hayes
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (2)
-
Reilly Hayes -
Ross Paterson