I'm trying to do Exercise 2.5.2 from John Hughes's "Programming with Arrows". It asks to make the type SP defined as (notation is slightly different)
data SP a b = Inp (a -> SP a b) | Out b (SP a b)
an instance of Arrow, ArrowChoice and ArrowLoop. Some parts of it are straightforward, e.g.
arr f = fix $ \sp -> Inp $ \x -> Out (f x) sp
Some are a bit tricky; for "first" I ended up with code
first = fix first' where first' f sp = Inp $ \(x,z) -> let g = firstL x h = firstR z in case sp of Inp _ -> (g . h) f sp Out _ _ -> (h . g) f sp firstL x f (Inp fsp) = f $ fsp x firstL x f sp = first' (firstL x f) sp firstR z f (Out y sp) = Out (y,z) $ f sp firstR z f sp = first' (firstR z f) sp
which is a bit funny. But the real problem I don't know how to deal with is "loop". My first attempt was somethig like this:
loop (Out (y,z) sp) = Out y $ loop' z loop sp where loop' z f (Inp fsp) = Inp $ \x -> f $ fsp (x,z) loop' z f (Out (y,z') sp) = Out y $ loop' z' (loop' z f) sp
since I thought it's pointless to make a loop that don't do any output. But then I ran into trouble: *StreamProc> process (loop returnA) [1..10] *** Exception: g:/StreamProc.hs:(26,4)-(28,90): Non-exhaustive patterns in function loop So I realized that both arr and first are doing input first and output second, and that causes this error. I've tried to fix this with
loop (Inp fsp) = Inp $ \x -> let Out (y,z) sp = fsp (x,z) in Out y $ loop sp
This works as desired: *StreamProc> process (loop returnA) [1..10] [1,2,3,4,5,6,7,8,9,10] But it seems to solve the problem by shifting it one step away from us. I'm not sure this is enough. Any advice/suggestions?
Miguel Mitrofanov, on 9 July [1]:
I'm trying to do Exercise 2.5.2 from John Hughes's "Programming with Arrows". [...]
Sorry for the delayed reply. I've only just started learning about arrow programming, and since no-one else has replied to you, here is what I've discovered so far... I think there are some problems with your implementation of "first". Here are some examples which don't behave the way I would expect:
delaySP = foldr Out returnA
skipSP n = if n > 0 then Inp (\_ -> skipSP (n-1)) else returnA
*Main> runSP (delaySP [-3,-2,-1] &&& returnA) [0..9] [(-3,0),(-2,1),(-1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9)] I would expect 0 and 1 to be present in the sequence in the first component. *Main> runSP (skipSP 2 &&& returnA) [0..9] [(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9)] The second component seems to have been skipped as well as the first. The "tricky point" referred to in the tutorial exercise [2] seems to be that the two components running through first will inevitably get out of sync, possibly by an arbitrary number of elements. My first attempt was to use explicit queues:
import Data.Sequence
data SP a b = Get (a -> SP a b) | Put b (SP a b)
instance Arrow SP where arr f = Get $ \x -> Put (f x) (arr f)
Put y f >>> Get g = f >>> g y Get f >>> Get g = Get (\x -> f x >>> Get g) f >>> Put z g = Put z (f >>> g)
first = step empty empty where -- Invariant: at least one of [qfst,qsnd] must be empty. step qfst qsnd (Put y sp) = case viewl qsnd of EmptyL -> Get $ \(x,z) -> Put (y,z) (step (qfst |> x) qsnd sp) z :< zs -> Put (y,z) (step qfst zs sp) step qfst qsnd (Get fsp) = case viewl qfst of EmptyL -> Get $ \(x,z) -> step qfst (qsnd |> z) (fsp x) x :< xs -> step xs qsnd (fsp x)
instance ArrowChoice SP where left (Get fsp) = Get $ either (left . fsp) (\z -> Put (Right z) (left $ Get fsp)) left (Put y sp) = Put (Left y) (left sp)
This produces something reasonably sensible for the examples above: *Main> runSP (delaySP [-3,-2,-1] &&& returnA) [0..9] [(-3,0),(-2,1),(-1,2),(0,3),(1,4),(2,5),(3,6),(4,7),(5,8),(6,9)] *Main> runSP (skipSP 2 &&& returnA) [0..9] [(2,0),(3,1),(4,2),(5,3),(6,4),(7,5),(8,6),(9,7)] However, if you think about it more closely, it is still not satisfactory: *Main> runSP (Put 42 returnA) [] [42] *Main> runSP (first (Put 42 returnA)) [] [] In the second case, I think the answer should really be [(42,_|_)]. A more severe problem is that because both runSP and the arrow combinators pattern-match on the SP constructors, it is impossible to use recursive arrow structures with this implementation of the SP arrow:
factorial :: (Num a, ArrowChoice arr) => arr a a factorial = arr (choose (==0)) >>> arr (const 1) ||| (returnA &&& (arr (flip (-) 1) >>> factorial) >>> arr (uncurry (*)))
choose c x | c x = Left x | otherwise = Right x
*Main> factorial 4 24 *Main> runSP factorial [3,4] *** Exception: stack overflow Same goes for mapA given in the tutorial [2]. This problem also prevented me from defining an instance of ArrowLoop. So, I don't think explicit queues are the answer. I suspect one needs to use the circular/lazy programming technique described in section 2.3 [2] to implement the basic Arrow combinators, as well as ArrowLoop. With some luck, that might solve both of the above problems. [1]http://www.haskell.org/pipermail/haskell-cafe/2007-July/028180.html [2]http://www.cs.chalmers.se/~rjmh/afp-arrows.pdf
MB> I think there are some problems with your implementation of MB> "first". Here are some examples which don't behave the way I would MB> expect: You are right. I have a problem and I need to think of it a bit more. MB> My first attempt was to use explicit queues: So was mine. But then I thought I can replace queues by function composition; seems that I took a wrong step somewhere. *Main>> runSP (Put 42 returnA) [] MB> [42] *Main>> runSP (first (Put 42 returnA)) [] MB> [] MB> In the second case, I think the answer should really be [(42,_|_)]. I think, your implementation handles this correctly. Stream processors are supposed to handle infinite lists, not finite ones; so, if we continue feeding (first (Put 42 returnA)) with data, it would be able to output (42,something) instead of (42,(_|_)). MB> Same goes for mapA given in the tutorial [2]. This problem also MB> prevented me from defining an instance of ArrowLoop. Seems to be the same problem I have. It was stated at the end of my posting. MB> So, I don't think explicit queues are the answer. I suspect one MB> needs to use the circular/lazy programming technique described in MB> section 2.3 [2] to implement the basic Arrow combinators, as well MB> as ArrowLoop. With some luck, that might solve both of the above MB> problems. Tried that, but failed. Seems that this technique works only for very lazy stream processors - such as SF - and SP are more strict. There is a presentation "Arrows for Fudgets" by Magnus Carlsson, which explains that stream processors (SP) are not Hughes' arrows, but more general ones, with (,) bifunctor replaced with Either.
participants (2)
-
Matthew Brecknell -
Miguel Mitrofanov