On Thu, Feb 11, 2010 at 9:23 AM, Jason Dagit
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