[Haskell-beginners] Re: Space leak in a fold even after the usual fixes

[Heinrich Apfelmus]

Travis Erdman wrote:
> 
> I did not realize that the boxed arrays would have this extra-lazy behavior.
> The reason I chose boxed is because I needed to store these very large trees
> (custom data type) that I referenced in an earlier question.  Since D.V.Unboxed
> and Storable don't appear to support non-standard data types, is there another
> package that might better fit my needs?  Data.IntMap perhaps?  I originally
> chose an array over a map because I need fast random access to individual
> elements (and cheap modification).

Concerning your choice of data structure, take note that data structures
are *persistent* in Haskell, i.e. they cannot be mutated. So, while
arrays provide random access in O(1) time, they need O(n) time to update
because the whole array has to be copied (unless you ensure ephemeral
use with the ST or IO monad). Nonetheless, the Data.Vector library
provides functions like  map  that operate on the whole array and run in
O(n) time.

In comparison, Data.IntMap has O(size of Int in bits) lookup and O(size
of Int in bits) update.


Data.Vector is mainly about arrays of bytes, hence the prominence of
Unboxed and Storable. You could make your tree an instance of  Storable
, but I think that's only possible for fixed size types anyway.


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com