[Haskell-cafe] Re: Incremental array updates

[Bulat Ziganshin]

Hello Eugene,

Thursday, February 26, 2009, 5:32:14 PM, you wrote:

look at http://haskell.org/haskellwiki/Library/ArrayRef
it contains reimplementation of arrays library according to Oleg&Simon idea:

- Unboxed arrays now can be used in polymorphic functions, they are defined
for every element type that belongs to the classes Unboxed and HasDefaultValue
(again, look at http://www.haskell.org/pipermail/haskell-cafe/2004-July/006400.html).
You can add new instances to these classes



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






-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com