Haskell Arrow delay function

Question

I am reading John Hughes's Programing with Arrows. There is a piece of code that I really cannot understand. The code is following:

import Control.Arrow.Operations 
import Control.Arrow
import Control.Category
import Prelude hiding ((.),id)

newtype SF a b = SF {runSF :: [a] -> [b]}

instance Category SF where
         id = SF id
         (.) (SF f) (SF g) = SF $ \x -> f (g x)

(.*.) :: (a -> b) -> (c -> d) -> (a,c) -> (b,d)
(.*.) f g (a,c) = (f a, g c)


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 a b -> arr [a] [b]

listcase []     = Left ()
listcase (x:xs) = Right (x,xs)

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

What I cannot understand is that

> 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 that the result should be just adding a 0 at the head of each list since delay 0 is defined as SF (0:).

And even more strange,

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 can see what are diag and mapA (delay 0) doing, but I cannot quite understand the computation process with using delay. Can someone just help? Thanks.

Answer 1

One way to think about arrows is as some sort of factory diagram. You would be right if your SF were just (->). Go ahead and try it; 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, machines at the factory can do things more complicated than simply sending on their transformed input, the way -> works. Your SF machines "take in" an a and "put out" a b, but they're backed by a function [a] -> [b] which lets you feed them a stream of as and then they can do something more sophisticated than -> does.

So the delay 0 machine takes a stream of numbers and prepends 0 to it, easy peasy, "lagging" the original stream by one "time step" if you want to think of it that way.

Similarly the a1 &&& a2 machine will have to feed its input stream to both of the sub-machines, and when they both have values, it can "zip" those together. It uses its sub-machines [b] -> [c] and [b] -> [d] to produces [b] -> [(c, d)], after all.

The a1 ||| a2 machine is trickier: it takes similar sub-machines [b] -> [d] and [c] -> [d] and uses them to form [Either b c] -> [d]. If that looked completely self-explanatory, look again! We didn't have Either [b] [c], which would have been totally straightforward (and which is what -> deals with above), but rather [Either b c]. The obvious solution for what to do here is:

1. Grab the left-sub-list, provide it to the left machine
2. Grab the right-sub-list, provide it to the right machine
3. Return the resulting [d]s in some complicated interleaved order.

What order? The easiest way is to go back through the original list and, whenever you see a Left, yield a d from the left machine's list; whenever you see a Right, yield a d from the right list.

With all of this background, we come to mapA:

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

For SF, the listcase will take the incoming stream of lists and produce a stream of Either () (x, [x]), depending on whether that stream is empty. In the first pass through the list, none of the entries in your runSF are empty, so each list is a Right branch emitting one right value.

So we have[Right (1, [2,3]), Right (4, [5]), Right (6, []), ...] which gets flattened and split into two lists: [1, 4, 6, ...] and [[2,3], [5], [], ...].

That first list gets fed into the delay function, so it gets prepended with 0. The second list gets fed recursively into mapA f, so then the [2, 5] prefixes also get delayed; and so on.

At the end when you join them together you find that each level of nesting in the lists has gotten delayed, so that the first emitted list is [0, 0, 0] and the second is [1, 2].