Data.Map
| Авторские права | (c) Daan Leijen 2002 (c) Andriy Palamarchuk 2008 |
|---|---|
| Лицензия | BSD-стиль |
| Поддержка | libraries@haskell.org |
| Стабильность | предварительная |
| Переносимость | переносимый |
| Safe Haskell | Safe |
| Язык | Haskell98 |
Описание
Примечание: Используйте Data.Map.Strict вместо этого модуля, если:
- Вам в конечном итоге потребуются все сохраненные значения.
- Сохраненные значения не представляют собой большие виртуальные структуры данных, которые должны вычисляться лениво.
Эффективная реализация упорядоченных отображений ключей на значения (словари).
Эти модули предназначены для импорта с квалификацией, чтобы избежать конфликтов имен с функциями Prelude, например:
import qualified Data.Map as Map
Реализация Map основана на сбалансированных по размеру двоичных деревьях (или деревьях с ограниченным балансом), как описано в:
- Stephen Adams, "Эффективные множества: балансирование", Журнал функционального программирования 3(4):553-562, октябрь 1993, http://www.swiss.ai.mit.edu/~adams/BB/.
- J. Nievergelt и E.M. Reingold, "Двоичные деревья поиска с ограниченным балансом", Журнал вычислений SIAM 2(1), март 1973.
Обратите внимание, что реализация смещена влево — элементы первого аргумента всегда отдаются предпочтение перед вторым, например, в union или insert.
Комментарии к операциям содержат сложность времени операции в обозначении Big-O (http://en.wikipedia.org/wiki/Big_O_notation).
модуль Data.Map.Lazy
insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a Источник
Устарело. Начиная с версии 0.5, заменено на insertWith.
O(log n). Аналогично insertWith, но значение, вставляемое в карту, вычисляется до WHNF предварительно.
Например, для обновления счетчика:
insertWith' (+) k 1 m
insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a Источник
Устарело. Начиная с версии 0.5, заменено на insertWithKey.
O(log n). Аналогично insertWithKey, но значение, вставляемое в карту, вычисляется до WHNF предварительно.
insertLookupWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a) Источник
Устарело. Начиная с версии 0.5, заменено на insertLookupWithKey.
O(log n). Аналогично insertLookupWithKey, но значение, вставляемое в карту, вычисляется до WHNF предварительно.
fold :: (a -> b -> b) -> b -> Map k a -> b Источник
Устарело. Начиная с версии 0.5, заменено на foldr.
O(n). Складывает значения в карте, используя заданный справа-ассоциативный бинарный оператор. Эта функция эквивалентна foldr и присутствует только для совместимости.
foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b Источник
Устарело. Начиная с версии 0.4, заменено на foldrWithKey.
O(n). Складывает ключи и значения в карте, используя заданный справа-ассоциативный бинарный оператор. Эта функция эквивалентна foldrWithKey и присутствует только для совместимости.
© The University of Glasgow and others
Licensed under a BSD-style license (see top of the page).
https://downloads.haskell.org/~ghc/7.10.3/docs/html/libraries/containers-0.5.6.2/Data-Map.html
