mathr / blog / #

I was reading up on arrows, specifically A New Notation For Arrows, but ran into some trouble. Here's what I discovered.

Firstly, I started out with:

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

That is, I wanted to process lists. I implemented the Arrow instance as found in the above paper without too much difficulty:

instance Arrow SF where
  arr f = SF (map f)
  SF f >>> SF g = SF (g . f)
  first  (SF f) = SF (uncurry zip . (f *** id) . unzip)
  second (SF f) = SF (uncurry zip . (id *** f) . unzip)

But then the trouble arrived - I suddenly noticed that the paper was using infinite sequences, not the finite sequences I was using myself. Trying to implement an ArrowLoop as per the paper led to horrible grief:

-- instance ArrowLoop SF where
--  loop (SF f) = SF (loop (unzip . f . uncurry zip))

The problem is that this is far too strict - on non-empty input it caused stack overflow crashes, which isn't exactly what I wanted. I found the solution in Programming With Arrows (page 17), which involves some subtlety with lazy patterns:

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

Then a length-preserving delay function for ArrowCircuit (not sure yet why this might be necessary or otherwise desireable, but it seems sensible) completes the base code to build funky circuits with:

class ArrowLoop a => ArrowCircuit a where
  delay :: b -> a b b

instance ArrowCircuit SF where
  delay x = SF (init . (x:))

The counter is implemented exactly as in the Notation paper, and now it works!

counter :: ArrowCircuit a => a Bool Int
counter = proc reset -> do
  rec next <- delay 0 -< out + 1
      out <- returnA -< if reset then 0 else next
  returnA -< out

And if you need proof:

main :: IO ()
main = do
  let x = runSF counter
  print (x (map b "tfftfffftfftffttfttfff"))
  where
    b 't' = True
    b 'f' = False

-- outputs [0,1,2,0,1,2,3,4,0,1,2,0,1,2,0,0,1,0,0,1,2,3]

Should be fun to play around with this some more, now I've got the big headaches out of the way (I hope).