[racket] Immutable vectors

On 09/04/2013 10:28 AM, Konrad Hinsen wrote:
> For the kind of data I am working with, immutable vectors look like
> just the right choice: immutable and O(1) element access. However, I
> am discovering that they are a real pain to work with.
>
> Pretty much any vector operation returns a mutable vector: vector-map,
> vector-drop, vector-split-at, etc. I have to use
> vector->immutable-vector afterwards to get what I want.  That's a lot
> of code clutter, and a lot of unnecessary object generation.
> Getting data from a stream into an immutable vector is the worst: it
> requires two intermediates: sequence->list, list->vector,
> vector->immutable-vector.
>
> So I am beginning to wonder if immutable vectors are some obsolete
> feature that is being discouraged. Is there a better choice for an
> immutable sequence with O(1) element access?

Racket's language design philosophy encourages immutability, so I don't 
see them going away any time soon. Immutable vectors is one area the 
standard library doesn't (currently) meet its design goals, IMO.

FWIW, `vector->immutable-vector' is pretty fast. It's usually the least 
significant part of an O(n) operation. Its two biggest problems are that 
it allocates memory and annoys people.

If you're working in Typed Racket, you might consider using the 
`math/array' library. It provides multidimensional arrays with O(1) 
access, a lot of ways to slice and dice them, and less memory allocation 
(especially if you use nonstrict arrays). They're not necessarily faster 
than vectors, though. Strict immutable arrays are backed by a mutable 
vector, so they allow element access only via a getter, which introduces 
an extra function call.

If you're not in Typed Racket, don't use `math/array' because the 
contract barrier makes element access very slow. But you might be able 
to do something similar: have library functions operate on mutable 
vectors, with user-facing functions accepting and receiving immutable 
vectors, or some more abstract wrapper data type. The `math/matrix' 
library does this, and it works out well enough. A lot of matrix 
operations are fastest when done in-place (e.g. Gaussian elimination), 
but *composing* matrix operations is easiest to reason about when 
matrices are immutable. Many matrix functions copy their arguments' 
elements to a vector, operate destructively on it, and return the result 
wrapped in an array.

Neil ⊥