Пакет vector предлагает неизменяемые (и изменяемые) упакованные и распакованные векторы со всеми ожидаемыми сложностями времени.Изменяемые можно использовать как из IO, так и из ST, и вы можете иметь распакованный массив любого экземпляра Storable.Это намного лучше, чем стандартные модули массивов.
Однако, поскольку вы упомянули эффективные неизменяемые обновления, я бы предложил использовать структуру данных, подобную Map;возможно HashMap из неупорядоченных контейнеров .Возможно, даже стоило бы иметь карту с небольшими распакованными векторами на листьях, чтобы избежать некоторой дополнительной нагрузки на дерево.
В зависимости от вашего варианта использования, вас также может заинтересовать стандартный Data.Sequence., который имеет O (1) доступ к началу и концу и довольно хорошее время доступа к середине последовательности.