[Haskell-cafe] Re: Incremental array updates

[Eugene Kirpichov]

STUArray is really a bit tricky to get used with: especially, if you
do something wrong, the type errors will be rather dreadful.
However, if you do everything right, it's OK and you sometimes even
don't need to write the types at all.
There are a couple of examples here
http://www.google.com/codesearch?q=runSTUArray
I also use them a bit in
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/jarfind
And here's one more small source where I used it:
http://hpaste.org/fastcgi/hpaste.fcgi/view?id=1791#a1791 That's
problem 87 from projecteuler.net.

2009/2/26 Daniel Kraft <d at domob.eu>:
> 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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
Eugene Kirpichov
Web IR developer, market.yandex.ru