История изменений

Если это иммутабельные персистентные структуры данных, которые не нужно полностью копировать при каждом «изменении»

Тут одно из двух: или не нужно полностью копировать или быстрый доступ по индексу. Можешь попробовать отсортировать такой массив через алгоритм с попарной заменой элементов, а потом сравнить скорость чтения из того, что получилось.

На самом деле, хороший компилятор преобразует

(define (f ...)
  (define v (vector ...))
  ...
  (g (vector-insert v i e) ...))

(то есть, если есть гарантия, что после передачи в vector-insert оригинальный массив уже не нужен) в версию, в которой vector-split-at в качестве start вернёт оригинальный массив с ограничением длины, а vector-append попытается сделать расширение массива на месте.

Если это иммутабельные персистентные структуры данных, которые не нужно полностью копировать при каждом «изменении»

Тут одно из двух: или не нужно полностью копировать или быстрый доступ по индексу. Можешь попробовать отсортировать такой массив через алгоритм с попарной заменой элементов, а потом сравнить скорость чтения из того, что получилось.

На самом деле, хороший компилятор преобразует

(define (f ...)
  (define v (vector ...))
  ...
  (f (vector-insert v i e) ...))

(то есть, если есть гарантия, что после передачи в vector-insert оригинальный массив уже не нужен) в версию, в которой vector-split-at в качестве start вернёт оригинальный массив с ограничением длины, а vector-append попытается сделать расширение массива на месте.