[Haskell-cafe] Re: Incremental array updates

[Daniel Kraft]

Ross Paterson wrote:
> 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:

Well, my main problem was the lazy evaluation...  And using STUArray did 
also speed it up notably, of course :)  I finally managed to get it 
working with it ;)

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

For this example program... yes of course :)  I'm trying to do so when 
possible, but for my real problem I couldn't figure out a nice way to do 
it like that, unfortunatelly.  Which does not mean it is impossible of 
course, but maybe just I need more experience in functional 
programming... :D

Daniel