[Haskell-cafe] Re: Go Haskell! -> array libraries

Andrew Coppin andrewcoppin at btinternet.com
Sat Nov 29 16:32:51 EST 2008

Henning Thielemann wrote:
> I suspect that this particular function is less useful than you think.
> It safes one allocation and might be faster since it uses less cache,
> but on the other hand, it cannot be fused.

If the array is "seriously large", you don't want to have five or six 
versions of it sitting in memory until the GC comes along to remove it. 
(OTOH, presumably an unboxed array can be allocated or freed quite 
quickly...) At a minimum, you've going to end up with two copies in 
memory - the existing one, and the one being built.

> I think in-place array
> updates are only sensible for writing array elements in really random
> order. As long as you can formulate your algorithm the way "read from
> random indices, but write a complete array from left to right", there is
> almost no need for mutable arrays.

Does quick-sort fit that pattern? (I'm guessing yes, since all you need 
to do is filtering and merging...)

Yeah, generally you only need arrays if you really want random access. 
Except in Haskell, where an array also happens to be the only way of 
storing large numbers of values unboxed. So sometimes you'll use an 
array because you want to save space. (E.g., parsing text is usually a 
sequential process with no random access, but you probably want to use 
ByteString all the same!) I sometimes also use unboxed arrays for the 
increase in strictness.

I guess the thing to do would be to measure the difference...

More information about the Haskell-Cafe mailing list