Haskell Arrow Delay Function

Question

I read John Hughes programming with arrows. There is code that I really can’t understand. The code is as follows:

import Control.Arrow.Operations import Control.Arrow import Control.Category import Prelude hiding ((.),id) newtype SF ab = SF {runSF :: [a] -> [b]} instance Category SF where id = SF id (.) (SF f) (SF g) = SF $ \x -> f (gx) (.*.) :: (a -> b) -> (c -> d) -> (a,c) -> (b,d) (.*.) fg (a,c) = (fa, gc) instance Arrow SF where arr f = SF (map f) first (SF f) = SF (uncurry zip . (f .*. id) . unzip) instance ArrowLoop SF where loop (SF f) = SF $ \as -> let (bs,cs) = unzip (f (zip as (stream cs))) in bs where stream ~(x:xs) = x:stream xs instance ArrowChoice SF where left (SF f) = SF (\xs -> combine xs (f [y | Left y <- xs])) where combine (Left y: xs) (z:zs) = Left z : combine xs zs combine (Right y :xs) zs = Right y : combine xs zs combine [] zs = [] instance ArrowCircuit SF where delay x = SF (x:) 

and then

 mapA :: ArrowChoice arr => arr ab -> arr [a] [b] listcase [] = Left () listcase (x:xs) = Right (x,xs) mapA f = arr listcase >>> arr (const []) ||| (f *** mapA f >>> arr (uncurry (:))) 

I dont understand what

 > runSF (mapA (delay 0)) [[1,2,3],[4,5],[6],[7,8],[9,10,11],[12,13,14,15]] [[0,0,0],[1,2],[4],[6,5],[7,8,3],[9,10,11,0]] 

I thought the result should be just adding 0 to the beginning of each list, since delay 0 is defined as SF (0:) .

And even weirder

 diag :: (ArrowCircuit a , ArrowChoice a) => a [b] [b] diag = arr listcase >>> arr (const []) ||| (arr id *** (diag >>> delay []) >>> arr (uncurry (:))) runSF diag [[1,2,3],[4,5,6],[7,8,9],[10,11,12]] [[1],[4,2],[7,5,3],[10,8,6]] 

I see what diag and mapA (delay 0) , but I cannot understand the calculation process with delay . Can someone just help? Thanks.

Answer 1

One way to think about arrows is to do something like a factory diagram. You would be right if your SF were just (->) . Go ahead and try; you should get:

 Prelude Control.Arrow> mapA (0 :) [[1,2,3],[4,5],[6],[7,8],[9,10,11],[12,13,14,15]] [[0,1,2,3],[0,4,5],[0,6],[0,7,8],[0,9,10,11],[0,12,13,14,15]] 

However, the machines in the factory can do something more complicated than just sending the converted -> how it works to their converted input. Your SF machines "take" a and "pull" a b , but they are supported by the function [a] -> [b] , which allows you to pass stream a , and then they can do something more complex than -> .

Thus, the delay 0 machine takes a stream of numbers and adds 0 to it, easy peasy, "delays" the source stream with one "time step" if you want to think about it.

Similarly, a1 &&& a2 will have to feed its input stream to both machines, and when they both matter, they can “pin” them together. He uses his sub machines [b] -> [c] and [b] -> [d] to create [b] -> [(c, d)] , after all.

Machine a1 ||| a2 a1 ||| a2 more complicated: it takes the similar machines [b] -> [d] and [c] -> [d] and uses them to form [Either bc] -> [d] . If it looked completely self-evident, look again! We did not have Either [b] [c] , which would be quite simple (and with which -> deals above), but rather [Either bc] . The obvious solution for this is:

• Take the left sub-list, put it on the left computer
• Take the right sub-list, put it on the right machine
• Returns the received [d] in some complex alternating order.

What order? The easiest way is to return to the original list, and when you see the left one, print d from the left list of machines; whenever you see Right, give d from the right list.

With all this background, we go to mapA :

 mapA f = arr listcase >>> arr (const []) ||| (f *** mapA f >>> arr (uncurry (:))) 

For SF , the listcase will accept an incoming list stream and create an Either () (x, [x]) stream, depending on whether this stream is empty. In the first pass through the list, none of the entries in your runSF empty, so each list is a Right branch that emits one valid value.

So, we have [Right (1, [2,3]), Right (4, [5]), Right (6, []), ...] , which is smoothed and divided into two lists: [1, 4, 6, ...] and [[2,3], [5], [], ...] .

This first list is fed into the delay function, so it is added to 0 . The second list gets recursively in mapA f , so the prefixes [2, 5] are also delayed; etc.

In the end, when you combine them, you will find that each level of nesting in the lists is delayed, so that the first emitted list is [0, 0, 0], and the second is [1, 2].