My apologies, my space leak was in my implementation of runAuto. Ignore me!
b On Wed, Sep 1, 2010 at 3:01 PM, Ben <midfi...@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. > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
