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

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

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

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

В пакете containers указано

Объявленная стоимость каждой операции либо наихудшая, либо амортизированная, но остается действительной, даже если структуры разделены.

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

Ключи и аргументы значения оцениваются в WHNF; Ключи и значения оцениваются до WHNF до их сохранения на карте.

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

Ответ 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, но это то, о чем нужно знать.