Re[2]: [Haskell-cafe] Re: Incremental array updates

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 :

...

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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

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