[Haskell-cafe] Re: Incremental array updates

[Daniel Kraft]

Daniel Fischer wrote:
> Am Donnerstag, 26. Februar 2009 14:53 schrieb Daniel Kraft:
>> Hi,
>>
>> I seem to be a little stuck with incremental array updates...  I've got
>> an array of "few" (some thousand) integers, but have to do a calculation
>> where I incrementally build up the array.  For sake of simplicity, for
>> now I don't use a State-Monad but simply pass the array as state down
>> the recursive calls.
>>
>> Unfortunatelly, I seem to experience problems with lazyness; when I run
>> my program, memory usage goes up to horrific values!  The simple program
>> below reproduces this; when run on my machine, it uses up about 300 MB
>> of real and 300 MB of virtual memory, and the system starts swapping
>> like mad!  I compiled with ghc --make -O3, ghc version 6.8.3 if that
>> matters.
> 
> As Eugene already said, use STUArray (STArray if you need some laziness).
> It's much much faster.

I'm just reading about it, but didn't find anything except the Haddock 
documentation...  This may need some time to work out :)

>> BTW, I tried to make the array update strict using the `seq` as below,
>> but with no effect...  What am I doing wrong here?
>>
>> Many thanks,
>> Daniel
>>
>>
>>
>>
>> import Data.Array;
>>
>>
>> arraySize = 1000
>> limit = 100000
>>
>> type MyArray = Array Int Int
>>
>> emptyArray :: MyArray
>> emptyArray = array (0, arraySize - 1) [ (i, 0) | i <- [0 .. arraySize - 1]
>> ]
>>
>>
>> procOne :: Int -> MyArray -> MyArray
>> procOne a cnt
>>
>>    | a > limit = cnt
>>    | otherwise =
>>
>>      let ind = a `mod` arraySize
>>          oldcnt = cnt ! ind
>>          newarr = cnt // [(ind, oldcnt + 1)]
>>      in
>>        procOne (a + 1) (newarr `seq` newarr)
> 
> Note that 
> 
> x `seq` x 
> 
> is exactly equivalent to just writing x, it will be evaluated if and only if x 
> is required to be evaluated by something else.
> 
> Try
> 	let ind = a `mod` arraySize
> 	    oldcnt = cnt ! ind
> 	    newarr = cnt // [(ind,oldcnt+1)]
> 	    newcnt = newarr ! ind
> 	in newcnt `seq` procOne (a+1) newarr
> 
> to force newarr to be evaluated, so the old array is eligible for garbage 
> collection.

This was my first attempt at using `seq` for forcing strict evaluation, 
and I seemingly did it wrong ;)

Thanks for all the quick answers!

Yours,
Daniel