Data.Map.Lazy

 import qualified Data.Map.Lazy as Map

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

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

• Ключевые аргументы вычисляются до WHNF

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

insertWith (\ new old -> old) undefined v m  ==  undefined
insertWith (\ new old -> old) k undefined m  ==  OK
delete undefined m  ==  undefined

Тип Map

data Map k a Source

Map из ключей k в значения a.

Операторы

(!) :: Ord k => Map k a -> k -> a infixl 9 Source

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 Source

То же самое, что и difference.

Запрос

null :: Map k a -> Bool Source

O(1). Пустое ли отображение?

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

size :: Map k a -> Int Source

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 Source

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 Source

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 Source

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 Source

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) Source

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). Выражение (updateWithKey f k map) обновляет значение 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, отдавая приоритет левому операнду при совпадении ключей, т. е. (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) Source

O(n). The function mapAccumWithKey threads an accumulating argument through the map in ascending order of keys.

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) Source

O(n). The function mapAccumR threads an accumulating argument through the map in descending order of keys.

mapKeys :: Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a Source

O(n*log n). Полученная карта получается путём применения 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 Source

O(n*log n). Полученная карта получается путём применения 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 Source

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 Source

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 Source

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 Source

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 Source

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 Source

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

foldMapWithKey f = fold . mapWithKey f

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

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

foldr' :: (a -> b -> b) -> b -> Map k a -> b Source

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

foldl' :: (a -> b -> a) -> a -> Map k b -> a Source

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

foldrWithKey' :: (k -> a -> b -> b) -> b -> Map k a -> b Source

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

foldlWithKey' :: (a -> k -> b -> a) -> a -> Map k b -> a Source

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

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

elems :: Map k a -> [a] Source

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

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

keys :: Map k a -> [k] Source

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

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

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

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

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

keysSet :: Map k a -> Set k Source

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 Source

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)] Source

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

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

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

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). Обновление элемента по индексу, т.е. по его индексу в нулевом базисе в последовательности, отсортированной по ключам. Если индекс выходит за пределы диапазона (меньше нуля, больше или равен size карты), вызывается 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 -> МожетБыть (a, Map k a) Источник

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

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

maxView :: Map k a -> МожетБыть (a, Map k a) Источник

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

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

minViewWithKey :: Map k a -> МожетБыть ((k, a), Map k a) Источник

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

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

maxViewWithKey :: Map k a -> МожетБыть ((k, a), Map k a) Источник

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 -> Строка Источник

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

showTreeWith :: (k -> a -> Строка) -> Булево -> Булево -> Map k a -> Строка Источник

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 -> Булево Источник

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

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