Ищете эффективную массивоподобную структуру, которая поддерживает «replace-one-member» и «append»

Question

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

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

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

Answer 1

Возможно стандартный Seq тип из Data.Sequence.Это не совсем O (1), но довольно хорошо:

• index (ваш lookup) и adjust(ваши replace) - O (log (мин. ( индекс , длина - индекс )))

• (><) (ваш append) равен O (log (мин ( длина1 , длина2 )))

Он основан на древовидной структуре (в частности, дереве из 2-3 пальцев), поэтому у него должны быть хорошие свойства совместного использования (это означает, что он не будет копировать всю последовательность для инкрементных модификаций и будет выполнять их также быстрее).Обратите внимание, что Seq s строгие, в отличие от списков.

Answer 2

В этом случае я бы попытался использовать изменяемые массивы, предпочтительно в монаде ST.

Основными преимуществами было бы сделать перевод более простым и простым и эффективным.

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