Data.Map.Strict

 import qualified Data.Map.Strict as Map

Свойства строгости

Этот модуль удовлетворяет следующим свойствам строгости:

1. Аргументы ключей вычисляются до WHNF;
2. Ключи и значения вычисляются до WHNF перед тем, как они будут сохранены в карте.

Вот пример, иллюстрирующий первое свойство:

delete undefined m  ==  undefined

Вот несколько примеров, которые иллюстрируют второе свойство:

map (\ v -> undefined) m  ==  undefined      -- m is not empty
mapKeys (\ k -> undefined) m  ==  undefined  -- m is not empty

Тип Map

data Map k a Исходный код

Карта из ключей k в значения a.

Операторы

(!) :: Ord k => Map k a -> k -> a infixl 9 Исходный код

O(log n). Находит значение по ключу. Вызывает error если элемент не найден.

fromList [(5,'a'), (3,'b')] ! 1    Error: element not in the map
fromList [(5,'a'), (3,'b')] ! 5 == 'a'

(\\) :: Ord k => Map k a -> Map k b -> Map k a infixl 9 Исходный код

То же, что и difference.

Запрос

null :: Map k a -> Bool Исходный код

O(1). Является ли карта пустой?

Data.Map.null (empty)           == True
Data.Map.null (singleton 1 'a') == False

size :: Map k a -> Int Исходный код

O(1). Количество элементов в карте.

size empty                                   == 0
size (singleton 1 'a')                       == 1
size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3

member :: Ord k => k -> Map k a -> Bool Исходный код

O(log n). Является ли ключ членом карты? См. также notMember.

member 5 (fromList [(5,'a'), (3,'b')]) == True
member 1 (fromList [(5,'a'), (3,'b')]) == False

notMember :: Ord k => k -> Map k a -> Bool Исходный код

O(log n). Не является ли ключ членом карты? См. также member.

notMember 5 (fromList [(5,'a'), (3,'b')]) == False
notMember 1 (fromList [(5,'a'), (3,'b')]) == True

lookup :: Ord k => k -> Map k a -> Maybe a Исходный код

O(log n). Поиск значения по ключу в карте.

Функция вернёт соответствующее значение как (Just value), или Nothing, если ключ отсутствует в карте.

Пример использования lookup:

import Prelude hiding (lookup)
import Data.Map

employeeDept = fromList([("John","Sales"), ("Bob","IT")])
deptCountry = fromList([("IT","USA"), ("Sales","France")])
countryCurrency = fromList([("USA", "Dollar"), ("France", "Euro")])

employeeCurrency :: String -> Maybe String
employeeCurrency name = do
    dept <- lookup name employeeDept
    country <- lookup dept deptCountry
    lookup country countryCurrency

main = do
    putStrLn $ "John's currency: " ++ (show (employeeCurrency "John"))
    putStrLn $ "Pete's currency: " ++ (show (employeeCurrency "Pete"))

Вывод этой программы:

  John's currency: Just "Euro"
  Pete's currency: Nothing

findWithDefault :: Ord k => a -> k -> Map k a -> a Исходный код

O(log n). Выражение (findWithDefault def k map) возвращает значение по ключу k или значение по умолчанию def, если ключ отсутствует в карте.

findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'

lookupLT :: Ord k => k -> Map k v -> Maybe (k, v) Исходный код

O(log n). Найти наибольший ключ, меньший данного, и вернуть соответствующую пару (ключ, значение).

lookupLT 3 (fromList [(3,'a'), (5,'b')]) == Nothing
lookupLT 4 (fromList [(3,'a'), (5,'b')]) == Just (3, 'a')

lookupGT :: Ord k => k -> Map k v -> Maybe (k, v) Source

O(log n). Найти наименьший ключ, больший данного, и вернуть соответствующую пару (ключ, значение).

lookupGT 4 (fromList [(3,'a'), (5,'b')]) == Just (5, 'b')
lookupGT 5 (fromList [(3,'a'), (5,'b')]) == Nothing

lookupLE :: Ord k => k -> Map k v -> Maybe (k, v) Source

O(log n). Найти наибольший ключ, меньший или равный данному, и вернуть соответствующую пару (ключ, значение).

lookupLE 2 (fromList [(3,'a'), (5,'b')]) == Nothing
lookupLE 4 (fromList [(3,'a'), (5,'b')]) == Just (3, 'a')
lookupLE 5 (fromList [(3,'a'), (5,'b')]) == Just (5, 'b')

lookupGE :: Ord k => k -> Map k v -> Maybe (k, v) Source

O(log n). Найти наименьший ключ, больший или равный данному, и вернуть соответствующую пару (ключ, значение).

lookupGE 3 (fromList [(3,'a'), (5,'b')]) == Just (3, 'a')
lookupGE 4 (fromList [(3,'a'), (5,'b')]) == Just (5, 'b')
lookupGE 6 (fromList [(3,'a'), (5,'b')]) == Nothing

Создание

empty :: Map k a Source

O(1). Пустое множество.

empty      == fromList []
size empty == 0

singleton :: k -> a -> Map k a Source

O(1). Множество с одним элементом.

singleton 1 'a'        == fromList [(1, 'a')]
size (singleton 1 'a') == 1

Вставка

insert :: Ord k => k -> a -> Map k a -> Map k a Source

O(log n). Вставка нового ключа и значения в множество. Если ключ уже присутствует в множестве, связанное значение заменяется на предоставленное. insert эквивалентно insertWith const.

insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'x')]
insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'a'), (7, 'x')]
insert 5 'x' empty                         == singleton 5 'x'

insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a Source

O(log n). Вставка с функцией, объединяющей новое и старое значения. insertWith f key value mp вставит пару (ключ, значение) в mp, если ключ не существует в множестве. Если ключ существует, функция вставит пару (key, f new_value old_value).

insertWith (++) 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "xxxa")]
insertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
insertWith (++) 5 "xxx" empty                         == singleton 5 "xxx"

insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a Source

O(log n). Вставка с функцией, объединяющей ключ, новое и старое значения. insertWithKey f key value mp вставит пару (ключ, значение) в mp, если ключ не существует в множестве. Если ключ существует, функция вставит пару (key,f key new_value old_value). Обратите внимание, что ключ, переданный в f, совпадает с ключом, переданным в insertWithKey.

let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
insertWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:xxx|a")]
insertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
insertWithKey f 5 "xxx" empty                         == singleton 5 "xxx"

insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a) Source

O(log n). Объединяет операцию вставки со получением старого значения. Выражение (insertLookupWithKey f k x map) представляет собой пару, где первый элемент равен (lookup k map), а второй элемент равен (insertWithKey f k x map).

let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
insertLookupWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:xxx|a")])
insertLookupWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "xxx")])
insertLookupWithKey f 5 "xxx" empty                         == (Nothing,  singleton 5 "xxx")

Вот как определить insertLookup с помощью insertLookupWithKey:

let insertLookup kx x t = insertLookupWithKey (\_ a _ -> a) kx x t
insertLookup 5 "x" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "x")])
insertLookup 7 "x" (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "x")])

Удаление/Обновление

delete :: Ord k => k -> Map k a -> Map k a Source

O(log n). Удаление ключа и его значения из множества. Если ключ не является элементом множества, возвращается исходное множество.

delete 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
delete 5 empty                         == empty

adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k a Source

O(log n). Обновить значение по определённому ключу результатом предоставленной функции. Если ключ не является элементом множества, возвращается исходное множество.

adjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
adjust ("new " ++) 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
adjust ("new " ++) 7 empty                         == empty

adjustWithKey :: Ord k => (k -> a -> a) -> k -> Map k a -> Map k a Source

O(log n). Корректировка значения по определённому ключу. Если ключ не является элементом множества, возвращается исходное множество.

let f key x = (show key) ++ ":new " ++ x
adjustWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
adjustWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
adjustWithKey f 7 empty                         == empty

update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a Source

O(log n). Выражение (update f k map) обновляет значение x по ключу k (если он есть в множестве). Если (f x) равно Nothing, элемент удаляется. Если оно равно (Just y), ключ k связывается с новым значением y.

let f x = if x == "a" then Just "new a" else Nothing
update f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
update f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"

updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a Source

O(log n). Обновляет значение x по ключу k (если он есть в множестве). Если (f k x) равно Nothing, элемент удаляется. Если оно равно (Just y), ключ k связывается с новым значением y.

let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
updateWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
updateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
updateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"

updateLookupWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a) Source

O(log n). Поиск и обновление. См. также updateWithKey. Функция возвращает изменённое значение, если оно было обновлено. Возвращает исходное значение ключа, если запись в множестве была удалена.

let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "5:new a", fromList [(3, "b"), (5, "5:new a")])
updateLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a")])
updateLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")

alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a Source

O(log n). Выражение (alter f k map) изменяет значение x по ключу k, или его отсутствие. alter может использоваться для вставки, удаления или обновления значения в множестве Map. Короче говоря: lookup k (alter f k m) = f (lookup k m).

let f _ = Nothing
alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
alter f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"

let f _ = Just "c"
alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "c")]
alter f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "c")]

Объединение

Объединение

union :: Ord k => Map k a -> Map k a -> Map k a Source

O(n+m). Выражение (union t1 t2) выполняет левостороннее объединение t1 и t2. При возникновении дублирующихся ключей оно отдаёт предпочтение t1, т.е. (union == unionWith const). Реализация использует эффективный алгоритм hedge-union.

union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]

unionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a Source

O(n+m). Объединение с функцией комбинирования. Реализация использует эффективный алгоритм hedge-union.

unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]

unionWithKey :: Ord k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a Source

O(n+m). Объединение с функцией комбинирования. Реализация использует эффективный алгоритм hedge-union.

let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value
unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]

unions :: Ord k => [Map k a] -> Map k a Source

Объединение списка словарей: (unions == foldl union empty).

unions [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
    == fromList [(3, "b"), (5, "a"), (7, "C")]
unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])]
    == fromList [(3, "B3"), (5, "A3"), (7, "C")]

unionsWith :: Ord k => (a -> a -> a) -> [Map k a] -> Map k a Source

Объединение списка словарей с операцией комбинирования: (unionsWith f == foldl (unionWith f) empty).

unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
    == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]

Разность

difference :: Ord k => Map k a -> Map k b -> Map k a Source

O(n+m). Разность двух словарей. Возвращает элементы первого словаря, отсутствующие во втором словаре. Реализация использует эффективный алгоритм hedge, сопоставимый с hedge-union.

difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"

differenceWith :: Ord k => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a Source

O(n+m). Разность с функцией комбинирования. Когда встречаются одинаковые ключи, функция комбинирования применяется к значениям этих ключей. Если она возвращает Nothing, элемент отбрасывается (собственно разность множеств). Если она возвращает (Just y), элемент обновляется новым значением y. Реализация использует эффективный алгоритм hedge, сопоставимый с hedge-union.

let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])
    == singleton 3 "b:B"

differenceWithKey :: Ord k => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a Source

O(n+m). Разность с функцией комбинирования. При встрече одинаковых ключей функция комбинирования применяется к ключу и обоим значениям. Если она возвращает Nothing, элемент отбрасывается (собственно разность множеств). Если она возвращает (Just y), элемент обновляется новым значением y. Реализация использует эффективный алгоритм hedge, сопоставимый с hedge-union.

let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
differenceWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (10, "C")])
    == singleton 3 "3:b|B"

Пересечение

intersection :: Ord k => Map k a -> Map k b -> Map k a Source

O(n+m). Пересечение двух словарей. Возвращает данные из первого словаря для ключей, присутствующих в обоих словарях. (intersection m1 m2 == intersectionWith const m1 m2). Реализация использует эффективный алгоритм hedge, сопоставимый с hedge-union.

intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a"

intersectionWith :: Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k c Source

O(n+m). Пересечение с функцией комбинирования. Реализация использует эффективный алгоритм hedge, сопоставимый с hedge-union.

intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA"

intersectionWithKey :: Ord k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c Source

O(n+m). Пересечение с функцией комбинирования. Реализация использует эффективный алгоритм hedge, сопоставимый с hedge-union.

let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar
intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "5:a|A"

Универсальная функция комбинирования

mergeWithKey :: Ord k => (k -> a -> b -> Maybe c) -> (Map k a -> Map k c) -> (Map k b -> Map k c) -> Map k a -> Map k b -> Map k c Source

O(n+m). Высокопроизводительная универсальная функция комбинирования. Эта функция используется для определения unionWith, unionWithKey, differenceWith, differenceWithKey, intersectionWith, intersectionWithKey и может использоваться для определения других пользовательских функций комбинирования.

Убедитесь, что вы понимаете, что происходит при использовании mergeWithKey, иначе вас могут удивить неожиданный рост кода или даже повреждение структуры данных.

Когда mergeWithKey получает три аргумента, она встраивается в место вызова. Поэтому следует использовать mergeWithKey только для определения пользовательских функций комбинирования. Например, можно определить unionWithKey, differenceWithKey и intersectionWithKey как

myUnionWithKey f m1 m2 = mergeWithKey (\k x1 x2 -> Just (f k x1 x2)) id id m1 m2
myDifferenceWithKey f m1 m2 = mergeWithKey f id (const empty) m1 m2
myIntersectionWithKey f m1 m2 = mergeWithKey (\k x1 x2 -> Just (f k x1 x2)) (const empty) (const empty) m1 m2

При вызове mergeWithKey combine only1 only2, создается функция комбинирования двух IntMap таким образом:

• если ключ присутствует в обоих словарях, он передаётся с соответствующими значениями в функцию combine. В зависимости от результата, ключ либо присутствует в результате со своим значением, либо его нет;
• непустое поддерево, присутствующее только в первом словаре, передаётся в only1, и результат добавляется к результату;
• непустое поддерево, присутствующее только во втором словаре, передаётся в only2, и результат добавляется к результату.

Методы only1 и only2 должны возвращать словарь с подмножеством (возможно пустым) ключей заданного словаря. Значения могут быть изменены произвольным образом. Наиболее распространённые варианты only1 и only2 — id и const empty, но, например, map f или filterWithKey f могут использоваться для любого f.

Обход

Словарь

map :: (a -> b) -> Map k a -> Map k b Source

O(n). Применение функции ко всем значениям в словаре.

map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]

mapWithKey :: (k -> a -> b) -> Map k a -> Map k b Source

O(n). Применение функции ко всем значениям в словаре.

let f key x = (show key) ++ ":" ++ x
mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]

traverseWithKey :: Applicative t => (k -> a -> t b) -> Map k a -> t (Map k b) Source

O(n). traverseWithKey f s == fromList $ traverse ((k, v) -> (,) k $ f k v) (toList m) То есть, ведёт себя точно как обычный traverse за исключением того, что функция обхода также имеет доступ к ключу, связанному со значением.

traverseWithKey (\k v -> if odd k then Just (succ v) else Nothing) (fromList [(1, 'a'), (5, 'e')]) == Just (fromList [(1, 'b'), (5, 'f')])
traverseWithKey (\k v -> if odd k then Just (succ v) else Nothing) (fromList [(2, 'c')])           == Nothing

mapAccum :: (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c) Source

O(n). Функция mapAccum пропускает аргумент накопления через карту в порядке возрастания ключей.

let f a b = (a ++ b, b ++ "X")
mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])

mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c) Источник

O(n). Функция mapAccumWithKey пропускает аргумент накопления через карту в порядке возрастания ключей.

let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")
mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])

mapAccumRWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c) Источник

O(n). Функция mapAccumR пропускает аргумент накопления через карту в порядке убывания ключей.

mapKeys :: Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a Источник

O(n*log n). mapKeys f s — это карта, полученная путём применения f к каждому ключу s.

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

mapKeys (+ 1) (fromList [(5,"a"), (3,"b")])                        == fromList [(4, "b"), (6, "a")]
mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "c"
mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "c"

mapKeysWith :: Ord k2 => (a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a Источник

O(n*log n). mapKeysWith c f s — это карта, полученная путём применения f к каждому ключу s.

Размер результата может быть меньше, если f отображает два или более различных ключа в один и тот же новый ключ. В этом случае связанные значения будут объединены с использованием c.

mapKeysWith (++) (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "cdab"
mapKeysWith (++) (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "cdab"

mapKeysMonotonic :: (k1 -> k2) -> Map k1 a -> Map k2 a Источник

O(n). mapKeysMonotonic f s == mapKeys f s, но работает только тогда, когда f является строго монотонной. То есть, для любых значений x и y, если x < y, то f x < f y. Предварительное условие не проверяется. Полуформально, у нас есть:

and [x < y ==> f x < f y | x <- ls, y <- ls]
                    ==> mapKeysMonotonic f s == mapKeys f s
    where ls = keys s

Это означает, что f отображает различные оригинальные ключи в различные результирующие ключи. Эта функция имеет лучшую производительность, чем mapKeys.

mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
valid (mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")])) == True
valid (mapKeysMonotonic (\ _ -> 1)     (fromList [(5,"a"), (3,"b")])) == False

Склады

foldr :: (a -> b -> b) -> b -> Map k a -> b Источник

O(n). Склады значения в карте с использованием заданного правого ассоциативного бинарного оператора, такого, что foldr f z == foldr f z . elems.

Например,

elems map = foldr (:) [] map

let f a len = len + (length a)
foldr f 0 (fromList [(5,"a"), (3,"bbb")]) == 4

foldl :: (a -> b -> a) -> a -> Map k b -> a Источник

O(n). Склады значения в карте с использованием заданного левого ассоциативного бинарного оператора, такого, что foldl f z == foldl f z . elems.

Например,

elems = reverse . foldl (flip (:)) []

let f len a = len + (length a)
foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4

foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b Источник

O(n). Склады ключи и значения в карте с использованием заданного правого ассоциативного бинарного оператора, такого, что foldrWithKey f z == foldr (uncurry f) z . toAscList.

Например,

keys map = foldrWithKey (\k x ks -> k:ks) [] map

let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
foldrWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"

foldlWithKey :: (a -> k -> b -> a) -> a -> Map k b -> a Источник

O(n). Склады ключи и значения в карте с использованием заданного левого ассоциативного бинарного оператора, такого, что foldlWithKey f z == foldl (\z' (kx, x) -> f z' kx x) z . toAscList.

Например,

keys = reverse . foldlWithKey (\ks k x -> k:ks) []

let f result k a = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
foldlWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (3:b)(5:a)"

foldMapWithKey :: Monoid m => (k -> a -> m) -> Map k a -> m Источник

O(n). Склады ключи и значения в карте с использованием заданного моноида, такого, что

foldMapWithKey f = fold . mapWithKey f

Это может быть асимптотически быстрее, чем foldrWithKey или foldlWithKey для некоторых моноидов.

Строгие склады

foldr' :: (a -> b -> b) -> b -> Map k a -> b Источник

O(n). Строгая версия foldr. Каждое применение оператора оценивается перед использованием результата в следующем применении. Эта функция строго типизирует начальное значение.

foldl' :: (a -> b -> a) -> a -> Map k b -> a Источник

O(n). Строгая версия foldl. Каждое применение оператора оценивается перед использованием результата в следующем применении. Эта функция строго типизирует начальное значение.

foldrWithKey' :: (k -> a -> b -> b) -> b -> Map k a -> b Источник

O(n). Строгая версия foldrWithKey. Каждое применение оператора оценивается перед использованием результата в следующем применении. Эта функция строго типизирует начальное значение.

foldlWithKey' :: (a -> k -> b -> a) -> a -> Map k b -> a Источник

O(n). Строгая версия foldlWithKey. Каждое применение оператора оценивается перед использованием результата в следующем применении. Эта функция строго типизирует начальное значение.

Преобразование

elems :: Map k a -> [a] Источник

O(n). Возвращает все элементы карты в порядке возрастания их ключей. Поддерживает слияние списков.

elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]
elems empty == []

keys :: Map k a -> [k] Источник

O(n). Возвращает все ключи карты в порядке возрастания. Поддерживает слияние списков.

keys (fromList [(5,"a"), (3,"b")]) == [3,5]
keys empty == []

assocs :: Map k a -> [(k, a)] Источник

O(n). Псевдоним для toAscList. Возвращает все пары ключ/значение в карте в порядке возрастания ключа. Поддерживает слияние списков.

assocs (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
assocs empty == []

keysSet :: Map k a -> Set k Источник

O(n). Множество всех ключей карты.

keysSet (fromList [(5,"a"), (3,"b")]) == Data.Set.fromList [3,5]
keysSet empty == Data.Set.empty

fromSet :: (k -> a) -> Set k -> Map k a Источник

O(n). Создаёт карту из набора ключей и функции, которая для каждого ключа вычисляет его значение.

fromSet (\k -> replicate k 'a') (Data.Set.fromList [3, 5]) == fromList [(5,"aaaaa"), (3,"aaa")]
fromSet undefined Data.Set.empty == empty

Списки

toList :: Map k a -> [(k, a)] Источник

O(n). Преобразует карту в список пар ключ/значение. Поддерживает слияние списков.

toList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
toList empty == []

fromList :: Ord k => [(k, a)] -> Map k a Источник

O(n*log n). Создаёт карту из списка пар ключ/значение. Смотрите также fromAscList. Если список содержит более одного значения для одного ключа, сохраняется последнее значение для ключа.

Если ключи в списке упорядочены, используется реализация с линейным временем выполнения, со скоростью, равной fromDistinctAscList.

fromList [] == empty
fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]
fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]

fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k a Source

O(n*log n). Создаёт карту из списка пар ключ/значение с функцией объединения. Смотрите также fromAscListWith.

fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
fromListWith (++) [] == empty

fromListWithKey :: Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a Source

O(n*log n). Создаёт карту из списка пар ключ/значение с функцией объединения. Смотрите также fromAscListWithKey.

let f k a1 a2 = (show k) ++ a1 ++ a2
fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "3ab"), (5, "5a5ba")]
fromListWithKey f [] == empty

Упорядоченные списки

toAscList :: Map k a -> [(k, a)] Source

O(n). Преобразует карту в список пар ключ/значение, где ключи отсортированы по возрастанию. Поддерживает слияние списков.

toAscList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]

toDescList :: Map k a -> [(k, a)] Source

O(n). Преобразует карту в список пар ключ/значение, где ключи отсортированы по убыванию. Поддерживает слияние списков.

toDescList (fromList [(5,"a"), (3,"b")]) == [(5,"a"), (3,"b")]

fromAscList :: Eq k => [(k, a)] -> Map k a Source

O(n). Создаёт карту из отсортированного по возрастанию списка за линейное время. Предварительное условие (входной список отсортирован по возрастанию) не проверяется.

fromAscList [(3,"b"), (5,"a")]          == fromList [(3, "b"), (5, "a")]
fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")]
valid (fromAscList [(3,"b"), (5,"a"), (5,"b")]) == True
valid (fromAscList [(5,"a"), (3,"b"), (5,"b")]) == False

fromAscListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a Source

O(n). Создаёт карту из отсортированного по возрастанию списка за линейное время с функцией объединения для одинаковых ключей. Предварительное условие (входной список отсортирован по возрастанию) не проверяется.

fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
valid (fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")]) == True
valid (fromAscListWith (++) [(5,"a"), (3,"b"), (5,"b")]) == False

fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a Source

O(n). Создаёт карту из отсортированного по возрастанию списка за линейное время с функцией объединения для одинаковых ключей. Предварительное условие (входной список отсортирован по возрастанию) не проверяется.

let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2
fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")] == fromList [(3, "b"), (5, "5:b5:ba")]
valid (fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")]) == True
valid (fromAscListWithKey f [(5,"a"), (3,"b"), (5,"b"), (5,"b")]) == False

fromDistinctAscList :: [(k, a)] -> Map k a Source

O(n). Создаёт карту из отсортированного по возрастанию списка уникальных элементов за линейное время. Предварительное условие не проверяется.

fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
valid (fromDistinctAscList [(3,"b"), (5,"a")])          == True
valid (fromDistinctAscList [(3,"b"), (5,"a"), (5,"b")]) == False

Фильтр

filter :: (a -> Bool) -> Map k a -> Map k a Source

O(n). Фильтрует все значения, удовлетворяющие предикату.

filter (> "a") (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
filter (> "x") (fromList [(5,"a"), (3,"b")]) == empty
filter (< "a") (fromList [(5,"a"), (3,"b")]) == empty

filterWithKey :: (k -> a -> Bool) -> Map k a -> Map k a Source

O(n). Фильтрует все пары ключ/значение, удовлетворяющие предикату.

filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"

partition :: (a -> Bool) -> Map k a -> (Map k a, Map k a) Source

O(n). Разделяет карту по предикату. Первая карта содержит все элементы, удовлетворяющие предикату, вторая — все элементы, которые не удовлетворяют предикату. Смотрите также split.

partition (> "a") (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a")
partition (< "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
partition (> "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])

partitionWithKey :: (k -> a -> Bool) -> Map k a -> (Map k a, Map k a) Source

O(n). Разделяет карту по предикату. Первая карта содержит все элементы, удовлетворяющие предикату, вторая — все элементы, которые не удовлетворяют предикату. Смотрите также split.

partitionWithKey (\ k _ -> k > 3) (fromList [(5,"a"), (3,"b")]) == (singleton 5 "a", singleton 3 "b")
partitionWithKey (\ k _ -> k < 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
partitionWithKey (\ k _ -> k > 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])

mapMaybe :: (a -> Maybe b) -> Map k a -> Map k b Source

O(n). Применяет функцию к значениям и собирает результаты Just.

let f x = if x == "a" then Just "new a" else Nothing
mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"

mapMaybeWithKey :: (k -> a -> Maybe b) -> Map k a -> Map k b Source

O(n). Применяет функцию к ключам/значениям и собирает результаты Just.

let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing
mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"

mapEither :: (a -> Either b c) -> Map k a -> (Map k b, Map k c) Source

O(n). Применяет функцию к значениям и разделяет результаты Left и Right.

let f a = if a < "c" then Left a else Right a
mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")])

mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])

mapEitherWithKey :: (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c) Source

O(n). Применяет функцию к ключам/значениям и разделяет результаты Left и Right.

let f k a = if k < 5 then Left (k * 2) else Right (a ++ a)
mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")])

mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")])

split :: Ord k => k -> Map k a -> (Map k a, Map k a) Source

O(log n). Выражение (split k map) — это пара (map1,map2) где ключи в map1 меньше k, а ключи в map2 больше k. Любой ключ, равный k, не находится ни в map1 ни в map2.

split 2 (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3,"b"), (5,"a")])
split 3 (fromList [(5,"a"), (3,"b")]) == (empty, singleton 5 "a")
split 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a")
split 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", empty)
split 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], empty)

splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a) Source

O(log n). Выражение (splitLookup k map) разделяет карту так же, как split но также возвращает lookup k map.

splitLookup 2 (fromList [(5,"a"), (3,"b")]) == (empty, Nothing, fromList [(3,"b"), (5,"a")])
splitLookup 3 (fromList [(5,"a"), (3,"b")]) == (empty, Just "b", singleton 5 "a")
splitLookup 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Nothing, singleton 5 "a")
splitLookup 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Just "a", empty)
splitLookup 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], Nothing, empty)

splitRoot :: Map k b -> [Map k b] Source

O(1). Разделяет карту на части на основе структуры базового дерева. Эта функция полезна для одновременной обработки карты.

Гарантия относительно размеров частей не предоставляется; внутренний, но детерминированный процесс определяет это. Однако гарантируется, что возвращаемые части будут отсортированы по возрастанию (все элементы в первой подкарте меньше всех элементов во второй и так далее).

Примеры:

splitRoot (fromList (zip [1..6] ['a'..])) ==
  [fromList [(1,'a'),(2,'b'),(3,'c')],fromList [(4,'d')],fromList [(5,'e'),(6,'f')]]

splitRoot empty == []

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

Подмапа

isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool Source

O(n+m). Эта функция определена как (isSubmapOf = isSubmapOfBy (==)).

isSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool Source

O(n+m). Выражение (isSubmapOfBy f t1 t2) возвращает True если все ключи в t1 находятся в дереве t2, и когда f возвращает True при применении к соответствующим значениям. Например, следующие выражения являются всеми True:

isSubmapOfBy (==) (fromList [('a',1)]) (fromList [('a',1),('b',2)])
isSubmapOfBy (<=) (fromList [('a',1)]) (fromList [('a',1),('b',2)])
isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1),('b',2)])

Но следующие являются всеми False:

isSubmapOfBy (==) (fromList [('a',2)]) (fromList [('a',1),('b',2)])
isSubmapOfBy (<)  (fromList [('a',1)]) (fromList [('a',1),('b',2)])
isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1)])

isProperSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool Source

O(n+m). Является ли это собственной подмапой? (т. е. подмапа, но не равна). Определено как (isProperSubmapOf = isProperSubmapOfBy (==)).

isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool Source

O(n+m). Является ли это собственной подмапой? (т. е. подмапа, но не равна). Выражение (isProperSubmapOfBy f m1 m2) возвращает True когда m1 и m2 не равны, все ключи в m1 находятся в m2, и когда f возвращает True при применении к соответствующим значениям. Например, следующие выражения являются всеми True:

isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
isProperSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])

Но следующие являются всеми False:

isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)])
isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)])
isProperSubmapOfBy (<)  (fromList [(1,1)])       (fromList [(1,1),(2,2)])

Индексированный

lookupIndex :: Ord k => k -> Map k a -> Maybe Int Source

O(log n). Поиск индекса ключа, который является его нулевым индексом в последовательности, отсортированной по ключам. Индекс — это число от 0 до, но не включая, size карты.

isJust (lookupIndex 2 (fromList [(5,"a"), (3,"b")]))   == False
fromJust (lookupIndex 3 (fromList [(5,"a"), (3,"b")])) == 0
fromJust (lookupIndex 5 (fromList [(5,"a"), (3,"b")])) == 1
isJust (lookupIndex 6 (fromList [(5,"a"), (3,"b")]))   == False

findIndex :: Ord k => k -> Map k a -> Int Source

O(log n). Возвращает индекс ключа, который является его нулевым индексом в последовательности, отсортированной по ключам. Индекс — это число от 0 до, но не включая, size карты. Вызывает error, когда ключ не является member карты.

findIndex 2 (fromList [(5,"a"), (3,"b")])    Error: element is not in the map
findIndex 3 (fromList [(5,"a"), (3,"b")]) == 0
findIndex 5 (fromList [(5,"a"), (3,"b")]) == 1
findIndex 6 (fromList [(5,"a"), (3,"b")])    Error: element is not in the map

elemAt :: Int -> Map k a -> (k, a) Source

O(log n). Извлечение элемента по его индексу, т. е. по его нулевому индексу в последовательности, отсортированной по ключам. Если индекс выходит за пределы диапазона (меньше нуля, больше или равен size карты), вызывается error.

elemAt 0 (fromList [(5,"a"), (3,"b")]) == (3,"b")
elemAt 1 (fromList [(5,"a"), (3,"b")]) == (5, "a")
elemAt 2 (fromList [(5,"a"), (3,"b")])    Error: index out of range

updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a Source

O(log n). Обновление элемента по индексу. Вызывает error при использовании недопустимого индекса.

updateAt (\ _ _ -> Just "x") 0    (fromList [(5,"a"), (3,"b")]) == fromList [(3, "x"), (5, "a")]
updateAt (\ _ _ -> Just "x") 1    (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "x")]
updateAt (\ _ _ -> Just "x") 2    (fromList [(5,"a"), (3,"b")])    Error: index out of range
updateAt (\ _ _ -> Just "x") (-1) (fromList [(5,"a"), (3,"b")])    Error: index out of range
updateAt (\_ _  -> Nothing)  0    (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
updateAt (\_ _  -> Nothing)  1    (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
updateAt (\_ _  -> Nothing)  2    (fromList [(5,"a"), (3,"b")])    Error: index out of range
updateAt (\_ _  -> Nothing)  (-1) (fromList [(5,"a"), (3,"b")])    Error: index out of range

deleteAt :: Int -> Map k a -> Map k a Source

O(log n). Удаление элемента по индексу, т. е. по его нулевому индексу в последовательности, отсортированной по ключам. Если индекс выходит за пределы диапазона (меньше нуля, больше или равен size карты), вызывается error.

deleteAt 0  (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
deleteAt 1  (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
deleteAt 2 (fromList [(5,"a"), (3,"b")])     Error: index out of range
deleteAt (-1) (fromList [(5,"a"), (3,"b")])  Error: index out of range

Минимум/Максимум

findMin :: Map k a -> (k, a) Source

O(log n). Минимальный ключ карты. Вызывает error если карта пуста.

findMin (fromList [(5,"a"), (3,"b")]) == (3,"b")
findMin empty                            Error: empty map has no minimal element

findMax :: Map k a -> (k, a) Source

O(log n). Максимальный ключ карты. Вызывает error если карта пуста.

findMax (fromList [(5,"a"), (3,"b")]) == (5,"a")
findMax empty                            Error: empty map has no maximal element

deleteMin :: Map k a -> Map k a Source

O(log n). Удаление минимального ключа. Возвращает пустую карту, если карта пуста.

deleteMin (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(5,"a"), (7,"c")]
deleteMin empty == empty

deleteMax :: Map k a -> Map k a Source

O(log n). Удаление максимального ключа. Возвращает пустую карту, если карта пуста.

deleteMax (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(3,"b"), (5,"a")]
deleteMax empty == empty

deleteFindMin :: Map k a -> ((k, a), Map k a) Source

O(log n). Удаление и поиск минимального элемента.

deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")])
deleteFindMin                                            Error: can not return the minimal element of an empty map

deleteFindMax :: Map k a -> ((k, a), Map k a) Source

O(log n). Удаление и поиск максимального элемента.

deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")])
deleteFindMax empty                                      Error: can not return the maximal element of an empty map

updateMin :: (a -> Maybe a) -> Map k a -> Map k a Source

O(log n). Обновление значения по минимальному ключу.

updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")]
updateMin (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"

updateMax :: (a -> Maybe a) -> Map k a -> Map k a Source

O(log n). Обновление значения по максимальному ключу.

updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")]
updateMax (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"

updateMinWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a Source

O(log n). Обновление значения по минимальному ключу.

updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")]
updateMinWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"

updateMaxWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a Source

O(log n). Обновление значения по максимальному ключу.

updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")]
updateMaxWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"

minView :: Map k a -> Maybe (a, Map k a) Source

O(log n). Извлекает значение, связанное с минимальным ключом карты, и карту, очищенную от этого элемента, или Nothing если передана пустая карта.

minView (fromList [(5,"a"), (3,"b")]) == Just ("b", singleton 5 "a")
minView empty == Nothing

maxView :: Map k a -> Maybe (a, Map k a) Source

O(log n). Извлекает значение, связанное с максимальным ключом карты, и карту, очищенную от этого элемента, или Nothing если передана пустая карта.

maxView (fromList [(5,"a"), (3,"b")]) == Just ("a", singleton 3 "b")
maxView empty == Nothing

minViewWithKey :: Map k a -> Maybe ((k, a), Map k a) Source

O(log n). Извлекает минимальную пару (ключ, значение) карты и карту, очищенную от этого элемента, или Nothing если передана пустая карта.

minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
minViewWithKey empty == Nothing

maxViewWithKey :: Map k a -> Maybe ((k, a), Map k a) Source

O(log n). Извлекает максимальную пару (ключ, значение) карты и карту, очищенную от этого элемента, или Nothing если передана пустая карта.

maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b")
maxViewWithKey empty == Nothing

Отладка

showTree :: (Show k, Show a) => Map k a -> String Source

O(n). Отображает дерево, реализующее карту. Дерево показано в сжатом, висящем формате. См. showTreeWith.

showTreeWith :: (k -> a -> String) -> Bool -> Bool -> Map k a -> String Source

O(n). Выражение (showTreeWith showelem hang wide map) показывает дерево, реализующее карту. Элементы отображаются с помощью функции showElem. Если hang равно True, отображается *висячее* дерево, в противном случае — вращаемое дерево. Если wide равно True, отображается расширенная версия.

 Map> let t = fromDistinctAscList [(x,()) | x <- [1..5]]
 Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True False t
 (4,())
 +--(2,())
 |  +--(1,())
 |  +--(3,())
 +--(5,())

 Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True True t
 (4,())
 |
 +--(2,())
 |  |
 |  +--(1,())
 |  |
 |  +--(3,())
 |
 +--(5,())

 Map> putStrLn $ showTreeWith (\k x -> show (k,x)) False True t
 +--(5,())
 |
 (4,())
 |
 |  +--(3,())
 |  |
 +--(2,())
    |
    +--(1,())

valid :: Ord k => Map k a -> Bool Source

O(n). Проверяет, является ли внутренняя структура карты корректной.

valid (fromAscList [(3,"b"), (5,"a")]) == True
valid (fromAscList [(5,"a"), (3,"b")]) == False