Коллекции Haskell с гарантией наихудших оценок для каждой отдельной операции?

Такие структуры необходимы для приложений реального времени - например, пользовательских интерфейсов. (Пользователям все равно, если нажатие кнопки занимает 0,1 с или 0,2 с, но им все равно, если 100-й клик заставляет выдающееся ленивое вычисление и длится 10 секунд.)

Я читал тезис Окасаки Чисто функциональные структуры данных, и он описывает интересный общий метод преобразования ленивых структур данных с амортизированными границами в структуры с тем же худшим -предельные рамки для каждой операции. Идея состоит в том, чтобы распределять вычисления таким образом, чтобы при каждом обновлении была вынуждена вынудить некоторую часть необоснованных трюков.

Интересно, есть ли такая реализация стандартных коллекций (Map, Set и т.д.) в Haskell?

поэтому нет гарантии для наихудших оценок для одной операции. Существуют строгие варианты, такие как Data.Map.Strict, но они строгие в своих ключах и значениях:

Ответы

Ответ 1

нет (возможной) строгости его структуры.

Ищите источник, например. для Data.Map.Map

-- See Note: Order of constructors
data Map k a  = Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
              | Tip

Вы видите, что a Map полностью сугубо-строгий (и строгий в ключах, даже с Data.Map.Lazy), если вы его оцениваете в WHNF, полный позвоночник принудительно. То же самое верно для IntMap s, Set и IntSet s.

Таким образом, вы можете предотвратить конструкцию больших трюков (за исключением отображаемых/содержащихся значений), заставив контейнер WHNF перед каждой операцией. Предотвращение больших трюков для содержащихся значений [общая причина утечки времени (и пространства)] автоматически для вариантов Data.XYZ.Strict (оговорка: значения оцениваются только в WHNF, если вам нужно больше, вам нужно это сделать самостоятельно, например, deepseq с любыми измененными значениями сразу после операции), что вам нужно, чтобы справиться с вариантами Data.XYZ.Lazy.

Таким образом,

Пользователям все равно, если нажатие кнопки занимает 0,1 с или 0,2 с, но им все равно, если 100-й щелчок заставляет выдающееся ленивое вычисление и длится 10 секунд.

- это легко избежать проблемы с этими контейнерами.

Тем не менее, все же может быть, что 100-й клик требует гораздо больше времени для обработки, чем средний, а не из-за выдающихся ленивых вычислений, но из-за алгоритма (рассмотрим классическую реализацию очереди с двумя списками, фронт, где вы удаляете элементы dequeue (Q (x:xs) ys) = (x, Q xs ys) в O (1) и обратно, где вы enqueue y (Q xs ys) = Q xs (y:ys) в O (1), ну, кроме того, что dequeuing принимает O (размер), когда передний список пуст, а назад нужно сначала отменить, но он O (1) амортизируется все еще) без изменения амортизированной стоимости.

Я не знаю, имеют ли такие алгоритмы, используемые в containers, но это то, о чем нужно знать.