Ищу эффективную структуру, подобную массиву, которая поддерживает «замену одного члена» и «добавление»

В качестве упражнения я написал реализацию алгоритма самой длинной возрастающей подпоследовательности, первоначально на Python, но я хотел бы перевести это к Хаскелю. В двух словах, алгоритм включает в себя свертку списка целых чисел, где результатом каждой итерации является массив целых чисел, являющийся результатом либо изменения одного элемента , либо добавления одного элемента к предыдущий результат.

Конечно, в Python вы можете просто изменить один элемент массива. В Haskell вы можете перестроить массив, заменяя один элемент на каждой итерации, но это кажется расточительным (копирование большей части массива на каждой итерации).

Подводя итог, я ищу эффективную структуру данных Haskell, которая представляет собой упорядоченный набор «n» объектов и поддерживает операции: lookup i, replace i foo, а добавляют foo(где iнаходится в [0..n-1]). Предложения?