[Haskell-cafe] Re: ArrowCircuit, delay and space leaks

[Ben]

My apologies, my space leak was in my implementation of runAuto.  Ignore me!

b

On Wed, Sep 1, 2010 at 3:01 PM, Ben <midfield at gmail.com> wrote:
> 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.
>