[Haskell-cafe] Incremental array updates

[Ross Paterson]

On Thu, Feb 26, 2009 at 02:53:42PM +0100, Daniel Kraft wrote:
> 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 noted above, updating an array one element at a time is the problem.
But before writing an imperative program with STUArray, you might try
building a whole new Array, specifying a new value for each element,
using array or accumArray.  These are often enough.  In your simple
example:

procOne :: Int -> MyArray -> MyArray
procOne a cnt
   | a >= limit = cnt
   | otherwise =
       procOne (a + arraySize) $!
          array (0, arraySize - 1)
                [ (i, cnt!i + 1) | i <- [0 .. arraySize - 1] ]

If elements of the new array depend on previously computed elements of
the same array, you can define the array recursively.