[Haskell-cafe] Incremental array updates

[Daniel Fischer]

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.

>
> 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.

>
>
> main :: IO ()
> main =
>    do
>      arr <- return $ procOne 0 emptyArray
>      print $ arr ! 42
>

Cheers,
Daniel