Поместить модификацию массива в Haskell?

Question

Мы все знаем, что изменение члена списка в функциональном стиле довольно медленно (O (n) для вектора, O (log n) для деревьев), поэтому есть ли оптимизация в компиляторе ghc, которая оптимизирует эту операциюна месте модификации? Если да, то в каких обстоятельствах это нужно? Работает ли это, если изменение происходит в функции, а список, который вы хотите изменить, является одним из ее аргументов?

Answer 1

Нет, компилятор не обнаруживает «модификацию» чистых структур данных, превращая их в модификацию на месте. Если вам действительно нужны характеристики производительности изменяемых массивов, вы должны использовать их явно (как упоминает Виллем в комментарии).

Answer 2

Я не совсем уверен, что O (log n) так медленно. На самом деле O (log n) часто рассматривается как "быстрый". В большинстве индексов базы данных используется B-дерево s [wiki] или аналогичные структуры данных. Хотя большинство баз данных не обновляют деревья в функционально-подобном стиле, временная сложность для вставки, извлечения, обновления, удаления и т. Д. Также составляет O (log n) . Если объем данных действительно не масштабируется, O (log n) , вероятно, будет достаточно, учитывая, что алгоритм реализован достаточно хорошо.

Популярный пакет, который поставляется с большинством дистрибутивов. array [hackage] , что позволяет быстро редактировать массивы. Он использует IO или ST монаду, так что «вне» контейнера он все еще чист, а под капотом он, конечно, вносит изменения в массив.

Haskell wiki имеет пример для массива ST. Здесь мы делаем:

buildPair :: ST s (Integer, Integer)
buildPair = do
    arr <- newArray (1,10) 37 :: ST s (STArray s Int Integer)
    a <- readArray arr 1
    writeArray arr 1 64
    b <- readArray arr 1
    return (a,b)

Здесь мы сначала создаем массив с границами (1,10) и инициализируем все элементы с 37. Затем мы читаем значение в первой строке, затем меняем его на 64, а затем снова читаем значение.

Обратите внимание, что сам ST s (Integer, Integer) не вносит изменения, выможно рассматривать как рецепт получения 2-х кортежей (Integer, Integer). Если затем мы используем runST :: (forall s . ST s a) -> a, мы запустим рецепт и, таким образом, получим результат.

Например:

Prelude Control.Monad Control.Monad.ST Data.Array.ST> runST buildPair
(37,64)