[Haskell-cafe] ArrowCircuit, delay and space leaks

Ben midfield at gmail.com
Wed Sep 1 18:01:38 EDT 2010

Hello Arrow-theorists --

In a previous email Maciej Piechotka showed me how to construct a
recursive function I wanted via ArrowCircuits.  This computes the
running sum of a stream of Ints.

rSum :: ArrowCircuit a => a Int Int
rSum = proc x -> do
 rec let next = out + x
     out <- delay 0 -< next
 returnA -< next

Although this arrow runs in linear time, it exhausts the stack (I've
compiled with ghc -02.)  The obvious strict non-arrow version runs in
linear time and constant space :

rSum :: [Int] -> [Int]
rSum = rSum' 0
  where rSum' _ [] = []
           rSum' n (x:xs) = let n' = x+n in n' `seq` n' : rSum n' xs

It is ironic because arrows were used in the past to plug space leaks.
 It seems that using delay here introduces a growing stack of thunks.
I have tried decorating everything I could think of with `seq` in the
pointfree and pointed versions, to no avail.

Is there a (pointed or point-free) version which runs in linear time
and constant space?

Best regards, Ben

PS I tried manually translating the ArrowCircuit into a
length-preserving stream function (SF in Hughes's paper) to try to
understand what was going on.  I ended up with

rSum :: [Int] -> [Int]
rSum xs = zipWith (+) xs $ 0 : rSum xs

which is not quite right as it is quadratic.  But I think it captures
the basic idea of the translation.

More information about the Haskell-Cafe mailing list