Random questions after a long haskell coding day

Simon Marlow simonmar@microsoft.com
Tue, 29 Jan 2002 13:07:06 -0000

> "Simon Marlow" <simonmar@microsoft.com> writes:
> >> Can we also rely on destructive updates for the monadic arrays?
> > In GHC, yes :-)
> Goodie!
> One more question: I imagine arrays give an opportunity to optimize by
> unboxing the contained type -- any chance of that?  How much space
> would an array of Chars consume compared to a list of Chars?

Using GHC's overloaded array interfaces (IArray and MArray) you can get
unboxed arrays just by changing the type of the array.  For example, if
you have an array of type (Array Int Char), you can make it an unboxed
array by changing its type to (UArray Int Char) and using the overloaded
versions of the array operations from the IArray module.  There are
unboxed arrays provided for most of the primtive types.

The space saving is significant: in GHC a list of characters requires at
least 12 bytes per character, but a UArray of Char requires 4 bytes per
char (Char is 32 bits in GHC to accommodate Unicode).  You could save
even more by using a UArray of Word8 (1 byte per char) if you only want
to store Latin-1 chars.  PackedStrings also require only 1 byte per
char, but they aren't compatible with UArrays yet (I'm working on a
version of PackedString that uses UArray instead of the current hacky
MutableByteArray implementation).

> Meandering back to the original point of O(1) array access - my
> feeling is that this should be a specific requirement of the
> language.  I would like to be able to specify the asymptotic time
> comlexity of my programs, but without knowing how primitives behave, I
> can't.  Usually, I tend to avoid arrays, since I don't know how well
> they'll behave.=20
> Is there a good reason (i.e. not just allowing lazy implementors use
> lists) for *not* specifying it?

I wouldn't object, but I believe Hugs still has a list-based
implementation of arrays (Hugs hackers pls correct me if I'm wrong).