Re: [Haskell-cafe] Re: Incremental array updates
It is, but they are still too slow. STArrays rock the world. 2009/2/28 Keith Sheppard : > I'm still learning haskell, so I may be missing something pretty > obvious, but isn't this the kind of thing that the diff array types > were created for. > > http://en.wikibooks.org/wiki/Haskell/Hierarchical_libraries/Arrays#DiffArray_.28module_Data.Array.Diff.29 > > -Keith > >>On Thu, Feb 26, 2009 at 06:45:27PM +, Ross Paterson wrote: >>> Yes, bucketing problems like this are a common case that the standard >>> functions cannot handle. Perhaps the libraries need a canned solution. >> >>Stratch that -- as Bulat points out, accumArray is such a canned solution. > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- Eugene Kirpichov Web IR developer, market.yandex.ru ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Incremental array updates
I'm still learning haskell, so I may be missing something pretty obvious, but isn't this the kind of thing that the diff array types were created for. http://en.wikibooks.org/wiki/Haskell/Hierarchical_libraries/Arrays#DiffArray_.28module_Data.Array.Diff.29 -Keith >On Thu, Feb 26, 2009 at 06:45:27PM +, Ross Paterson wrote: >> Yes, bucketing problems like this are a common case that the standard >> functions cannot handle. Perhaps the libraries need a canned solution. > >Stratch that -- as Bulat points out, accumArray is such a canned solution. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[6]: [Haskell-cafe] Re: Incremental array updates
2009/2/27 Bulat Ziganshin : > Hello Eugene, > > Friday, February 27, 2009, 4:42:03 PM, you wrote: > >> I'm exactly basing on them, but they don't have at least these things: > > "them" means Edison or Collections typeclasses? The EdisonAPI. > >> - Treatment for unboxed types (I don't know yet, whether it is >> needed; but why do STUArrays have special treatment then?) > > imho, this doesn't need its own typeclass I hope so :) > >> Actually, it started with me writing a monad-mutable hashtable and >> thinking about what its interface should be, so probably I should just >> upload the hashtable to hackage as is and look what comes next :) > > what are the differences against Data.Hashtable? > Support for ST monad and stuff like insertWith, mergeWith. > > -- > Best regards, > Bulat mailto:bulat.zigans...@gmail.com > > -- Eugene Kirpichov Web IR developer, market.yandex.ru ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[6]: [Haskell-cafe] Re: Incremental array updates
Hello Eugene, Friday, February 27, 2009, 4:42:03 PM, you wrote: > I'm exactly basing on them, but they don't have at least these things: "them" means Edison or Collections typeclasses? > - Treatment for unboxed types (I don't know yet, whether it is > needed; but why do STUArrays have special treatment then?) imho, this doesn't need its own typeclass > Actually, it started with me writing a monad-mutable hashtable and > thinking about what its interface should be, so probably I should just > upload the hashtable to hackage as is and look what comes next :) what are the differences against Data.Hashtable? -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[4]: [Haskell-cafe] Re: Incremental array updates
I'm exactly basing on them, but they don't have at least these things: - Monad-mutable collections like MArray - Instances of something like Assoc for arrays (arrays are collections in some sense, after all) - Treatment for unboxed types (I don't know yet, whether it is needed; but why do STUArrays have special treatment then?) It's not that I am in desperate need for these, but making the already-good collection API even better sounds like fun :) Actually, it started with me writing a monad-mutable hashtable and thinking about what its interface should be, so probably I should just upload the hashtable to hackage as is and look what comes next :) 2009/2/27 Bulat Ziganshin : > Hello Eugene, > > Thursday, February 26, 2009, 10:28:13 PM, you wrote: > >> 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 :-/ ). > > does this mean that type classes from Edison and Container (Collection?) > libraries are not good enough or you don't checked them? > > > -- > Best regards, > Bulat mailto:bulat.zigans...@gmail.com > > -- Eugene Kirpichov Web IR developer, market.yandex.ru ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[4]: [Haskell-cafe] Re: Incremental array updates
Hello Eugene, Thursday, February 26, 2009, 10:28:13 PM, you wrote: > 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 :-/ ). does this mean that type classes from Edison and Container (Collection?) libraries are not good enough or you don't checked them? -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Re: Incremental array updates
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 : > 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 = 10 > > 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.zigans...@gmail.com > > -- Eugene Kirpichov Web IR developer, market.yandex.ru ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
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 = 10 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, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Re: Incremental array updates
Hello Ross, Thursday, February 26, 2009, 9:54:23 PM, you wrote: >> the same loop using STArray, but accumArray provide you pure API for >> such computations > And accumArray can also be used with UArray if laziness is a problem. to be exact, for Array, STArray used internally for UArray - STUArray -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Incremental array updates
On Thu, Feb 26, 2009 at 09:36:17PM +0300, Bulat Ziganshin wrote: > Thursday, February 26, 2009, 9:27:10 PM, you wrote: > > It was about this: I needed to generate "all possibilities" for some > > combinations and each of those had a numeric property, say from 1 to > > 1; I then had to count how many of the possibilities were of a given > > "category". So I created this array, generated all combinations, and > > incremented the matching slot each time. > > it's histogram essentially? accumArray is doing so. internally, it's > the same loop using STArray, but accumArray provide you pure API for > such computations And accumArray can also be used with UArray if laziness is a problem. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Incremental array updates
On Thu, Feb 26, 2009 at 06:45:27PM +, Ross Paterson wrote: > Yes, bucketing problems like this are a common case that the standard > functions cannot handle. Perhaps the libraries need a canned solution. Stratch that -- as Bulat points out, accumArray is such a canned solution. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Incremental array updates
On Thu, Feb 26, 2009 at 07:27:10PM +0100, Daniel Kraft wrote: > It was about this: I needed to generate "all possibilities" for some > combinations and each of those had a numeric property, say from 1 to > 1; I then had to count how many of the possibilities were of a given > "category". So I created this array, generated all combinations, and > incremented the matching slot each time. > > I do not see how I could have done this another way, but I think it > should be a fairly common pattern, so if there are ideas, I'd welcome > them! Yes, bucketing problems like this are a common case that the standard functions cannot handle. Perhaps the libraries need a canned solution. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Incremental array updates
Hello Daniel, Thursday, February 26, 2009, 9:27:10 PM, you wrote: > It was about this: I needed to generate "all possibilities" for some > combinations and each of those had a numeric property, say from 1 to > 1; I then had to count how many of the possibilities were of a given > "category". So I created this array, generated all combinations, and > incremented the matching slot each time. it's histogram essentially? accumArray is doing so. internally, it's the same loop using STArray, but accumArray provide you pure API for such computations -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Incremental array updates
Ross Paterson wrote: On Thu, Feb 26, 2009 at 05:31:34PM +0100, Daniel Kraft wrote: Well, my main problem was the lazy evaluation... No, your main problem was that you were creating 100,000 arrays, each only a little different from the one before. Here I have to disagree (in my particular situation). Even with Data.Array but the strict evaluation the program took about 5m, where it before wouldn't even get far because of all that memory swapping... With STUArray it took 1m--much better, but the worst of all was the horrific memory usage. 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, unfortunately. Which does not mean it is impossible of course, but maybe just I need more experience in functional programming... :D Writing imperative programs in Haskell may not be the best way to gain that experience. What is the pattern of updates in your actual program? It was about this: I needed to generate "all possibilities" for some combinations and each of those had a numeric property, say from 1 to 1; I then had to count how many of the possibilities were of a given "category". So I created this array, generated all combinations, and incremented the matching slot each time. I do not see how I could have done this another way, but I think it should be a fairly common pattern, so if there are ideas, I'd welcome them! Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Incremental array updates
On Thu, Feb 26, 2009 at 05:31:34PM +0100, Daniel Kraft wrote: > Well, my main problem was the lazy evaluation... No, your main problem was that you were creating 100,000 arrays, each only a little different from the one before. > 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, unfortunately. Which does not mean it is impossible of > course, but maybe just I need more experience in functional > programming... :D Writing imperative programs in Haskell may not be the best way to gain that experience. What is the pattern of updates in your actual program? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Incremental array updates
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Incremental array updates
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 = 10 >>> >>> 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 > -- Eugene Kirpichov Web IR developer, market.yandex.ru ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Incremental array updates
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 = 10 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
[Haskell-cafe] Re: Incremental array updates
Eugene Kirpichov wrote: You need to use STUArray. The Data.Array completely-immutable-and-boxed arrays are ok only for tasks where you build an array once and don't modify it, and where you need array elements to be lazy. The // operation creates a copy of the whole array with one element modified. It should probably be called "turtleSlowCopyWholeArrayAndModifySingleElement". Thanks for the hint! However, I still don't see why this increments memory usage so much... Shouldn't even in this case the garbage collector remove the old, no longer needed versions of the array? My main point of concern is not that the program may run slowly, but that it uses that much memory. But of course for the real program this hint is surely very useful! I'll give it a try... Thanks, Daniel 2009/2/26 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. 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 = 10 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) main :: IO () main = do arr <- return $ procOne 0 emptyArray print $ arr ! 42 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
