[Haskell-cafe] Streamed creation of STArray from list?

[Ryan Ingram]

On Thu, Feb 11, 2010 at 9:23 AM, Jason Dagit <dagit at codersbase.com> wrote:
> If I know the length of the list, I might expect newListArray to have the
> memory behavior I want.  In my case, the code calls (length xs) to calculate
> the length of the list.  As I understand it, that will force the spine of
> the list into memory.  Can this be avoided?  The only trick that comes into
> mind is the one used by the C++ vector class where you dynamically resize
> the array and copy the values to the new array.  That's potentially a lot of
> copying, right?

Not really: as long as you grow the array exponentially the total
number of copies is linear in the size of the array.  On average you
will copy each element twice; the first element gets copied (log n)
times but the last half of the elements go directly into the final
array.

If you want to avoid putting any of the spine into memory you might do
a third copy where you shrink the array size at the end (or perhaps
there is an array type that has a 'shrink' operation that just reduces
the bounds without freeing any memory)

  -- ryan