[Haskell-cafe] Re: Incremental array updates

[Eugene Kirpichov]

Hello,
Thanks, I'll have a look at these. Treating unboxed stuff
polymorphically is anyways very interesting and would be good to use
in collections API that has been recently discussed (and which I
occasionally try to continue inventing with scarce success :-/ ).

2009/2/26 Bulat Ziganshin <bulat.ziganshin at gmail.com>:
> 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
>
>



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