Data.IntMap.Strict

 import Data.IntMap.Strict (IntMap)
 import qualified Data.IntMap.Strict as IntMap

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

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

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

Тип карты

data IntMap a Source

Карта целых чисел к значениям a.

type Key = Int Source

Операторы

(!) :: IntMap a -> Key -> a Source

O(min(n,W)). Найти значение по ключу. Вызывает error когда элемент не найден.

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

(\\) :: IntMap a -> IntMap b -> IntMap a infixl 9 Source

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

Запрос

null :: IntMap a -> Bool Source

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

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

size :: IntMap a -> Int Source

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

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

member :: Key -> IntMap a -> Bool Source

O(min(n,W)). Является ли ключ членом карты?

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

notMember :: Key -> IntMap a -> Bool Source

O(min(n,W)). Не является ли ключ членом карты?

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

lookup :: Key -> IntMap a -> Maybe a Source

O(min(n,W)). Поиск значения по ключу в карте. Также см. lookup.

findWithDefault :: a -> Key -> IntMap a -> a Source

O(min(n,W)). Выражение (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 :: Key -> IntMap a -> Maybe (Key, a) Source

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

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

lookupGT :: Key -> IntMap a -> Maybe (Key, a) Source

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

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

lookupLE :: Key -> IntMap a -> Maybe (Key, a) 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 :: Key -> IntMap a -> Maybe (Key, a) 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 :: IntMap a Source

O(1). Пустой массив.

empty      == fromList []
size empty == 0

singleton :: Key -> a -> IntMap a Source

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

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

Вставка

insert :: Key -> a -> IntMap a -> IntMap a Source

O(min(n,W)). Вставка новой пары ключ/значение в массив. Если ключ уже присутствует в массиве, связанное значение заменяется на указанное значение, т.е. 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 :: (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a Source

O(min(n,W)). Вставка со комбинирующей функцией. insertWith f key value mp вставит пару (ключ, значение) в mp, если ключ не существует в массиве. Если ключ существует, функция вставит 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 :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a Source

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

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"

Если ключ существует в массиве, эта функция ленивая в x, но строгой в результате f.

insertLookupWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> (Maybe a, IntMap a) Source

O(min(n,W)). Выражение (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 :: Key -> IntMap a -> IntMap a Source

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

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 :: (a -> a) -> Key -> IntMap a -> IntMap a Source

O(min(n,W)). Корректировка значения по указанному ключу. Если ключ не является членом массива, возвращается исходный массив.

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 :: (Key -> a -> a) -> Key -> IntMap a -> IntMap a Source

O(min(n,W)). Корректировка значения по указанному ключу. Если ключ не является членом массива, возвращается исходный массив.

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 :: (a -> Maybe a) -> Key -> IntMap a -> IntMap a Source

O(min(n,W)). Выражение (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 :: (Key -> a -> Maybe a) -> Key -> IntMap a -> IntMap a Source

O(min(n,W)). Выражение (update 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 :: (Key -> a -> Maybe a) -> Key -> IntMap a -> (Maybe a, IntMap a) Source

O(min(n,W)). Поиск и обновление. Функция возвращает исходное значение, если оно было обновлено. Это отличается от updateLookupWithKey. Возвращает исходное значение ключа, если запись в массиве удалена.

let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "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 :: (Maybe a -> Maybe a) -> Key -> IntMap a -> IntMap a Source

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

Объединение

Объединение

union :: IntMap a -> IntMap a -> IntMap a Source

O(n+m). Объединение (с левой предвзятостью) двух массивов. В случае дублирования ключей отдаёт предпочтение первому массиву, т.е. (union == unionWith const).

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

unionWith :: (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a Source

O(n+m). Объединение с функцией комбинирования.

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

unionWithKey :: (Key -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap a Source

O(n+m). Объединение с функцией комбинирования.

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 :: [IntMap a] -> IntMap a Source

Объединение списка карт.

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 :: (a -> a -> a) -> [IntMap a] -> IntMap a Source

Объединение списка карт с операцией комбинирования.

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

Разность

difference :: IntMap a -> IntMap b -> IntMap a Source

O(n+m). Разность между двумя картами (на основе ключей).

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

differenceWith :: (a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a Source

O(n+m). Разность с функцией комбинирования.

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 :: (Key -> a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a Source

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

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 :: IntMap a -> IntMap b -> IntMap a Source

O(n+m). Пересечение двух карт (левосторонняя предвзятость, based on keys).

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

intersectionWith :: (a -> b -> c) -> IntMap a -> IntMap b -> IntMap c Source

O(n+m). Пересечение с функцией комбинирования.

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

intersectionWithKey :: (Key -> a -> b -> c) -> IntMap a -> IntMap b -> IntMap c Source

O(n+m). Пересечение с функцией комбинирования.

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 :: (Key -> a -> b -> Maybe c) -> (IntMap a -> IntMap c) -> (IntMap b -> IntMap c) -> IntMap a -> IntMap b -> IntMap c Source

O(n+m). Высокопроизводительная универсальная функция комбинирования. Используя mergeWithKey, все функции комбинирования могут быть определены без потери эффективности (за исключением union, difference и intersection, где совместное использование некоторых узлов теряется с mergeWithKey).

Пожалуйста, убедитесь, что вы понимаете, что происходит при использовании 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) -> IntMap a -> IntMap b Source

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

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

mapWithKey :: (Key -> a -> b) -> IntMap a -> IntMap 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 => (Key -> a -> t b) -> IntMap a -> t (IntMap 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 -> IntMap b -> (a, IntMap 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 -> Key -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c) Source

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 -> Key -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c) Source

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

mapKeys :: (Ключ -> Ключ) -> IntMap a -> IntMap a Источник

O(n*min(n,W)). 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 :: (a -> a -> a) -> (Ключ -> Ключ) -> IntMap a -> IntMap 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 :: (Ключ -> Ключ) -> IntMap a -> IntMap a Источник

O(n*min(n,W)). 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")]

Склады

foldr :: (a -> b -> b) -> b -> IntMap 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 -> IntMap 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 :: (Ключ -> a -> b -> b) -> b -> IntMap 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 -> Ключ -> b -> a) -> a -> IntMap 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 :: Моноид m => (Ключ -> a -> m) -> IntMap a -> m Источник

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

foldMapWithKey f = fold . mapWithKey f

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

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

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

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

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

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

foldrWithKey' :: (Ключ -> a -> b -> b) -> b -> IntMap a -> b Источник

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

foldlWithKey' :: (a -> Ключ -> b -> a) -> a -> IntMap b -> a Источник

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

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

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

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

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

keys :: IntMap a -> [Ключ] Источник

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

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

assocs :: IntMap a -> [(Ключ, a)] Источник

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

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

keysSet :: IntMap a -> IntSet Источник

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

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

fromSet :: (Ключ -> a) -> IntSet -> IntMap a Источник

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

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

Списки

toList :: IntMap a -> [(Ключ, a)] Источник

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

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

fromList :: [(Ключ, a)] -> IntMap a Источник

O(n*min(n,W)). Создание карты из списка пар ключ/значение.

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 :: (a -> a -> a) -> [(Key, a)] -> IntMap a Source

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

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

fromListWithKey :: (Key -> a -> a -> a) -> [(Key, a)] -> IntMap a Source

O(n*min(n,W)). Построение карты из списка пар ключ/значение с объединяющей функцией. См. также fromAscListWithKey'.

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

Отсортированные списки

toAscList :: IntMap a -> [(Key, a)] Source

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

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

toDescList :: IntMap a -> [(Key, a)] Source

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

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

fromAscList :: [(Key, a)] -> IntMap 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")]

fromAscListWith :: (a -> a -> a) -> [(Key, a)] -> IntMap a Source

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

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

fromAscListWithKey :: (Key -> a -> a -> a) -> [(Key, a)] -> IntMap a Source

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

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

fromDistinctAscList :: [(Key, a)] -> IntMap a Source

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

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

Фильтр

filter :: (a -> Bool) -> IntMap a -> IntMap 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 :: (Key -> a -> Bool) -> IntMap a -> IntMap a Source

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

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

partition :: (a -> Bool) -> IntMap a -> (IntMap a, IntMap 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 :: (Key -> a -> Bool) -> IntMap a -> (IntMap a, IntMap 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) -> IntMap a -> IntMap 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 :: (Key -> a -> Maybe b) -> IntMap a -> IntMap 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) -> IntMap a -> (IntMap b, IntMap 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 :: (Key -> a -> Either b c) -> IntMap a -> (IntMap b, IntMap 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 :: Key -> IntMap a -> (IntMap a, IntMap a) Source

O(min(n,W)). Выражение (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 :: Key -> IntMap a -> (IntMap a, Maybe a, IntMap a) Source

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

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 :: IntMap a -> [IntMap a] Source

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

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

Примеры:

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

splitRoot empty == []

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

Подкарта

isSubmapOf :: Eq a => IntMap a -> IntMap a -> Bool Источник

O(n+m). Является ли это подкартой? Определяется как (isSubmapOf = isSubmapOfBy (==)).

isSubmapOfBy :: (a -> b -> Bool) -> IntMap a -> IntMap b -> Bool Источник

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

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

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

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

isProperSubmapOf :: Eq a => IntMap a -> IntMap a -> Bool Источник

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

isProperSubmapOfBy :: (a -> b -> Bool) -> IntMap a -> IntMap b -> Bool Источник

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

Min/Max

findMin :: IntMap a -> (Key, a) Источник

O(min(n,W)). Минимальный ключ карты.

findMax :: IntMap a -> (Key, a) Источник

O(min(n,W)). Максимальный ключ карты.

deleteMin :: IntMap a -> IntMap a Источник

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

Обратите внимание, что это изменение поведения для согласованности с Map – версии до 0.5 выдавали ошибку, если IntMap была уже пуста.

deleteMax :: IntMap a -> IntMap a Источник

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

Обратите внимание, что это изменение поведения для согласованности с Map – версии до 0.5 выдавали ошибку, если IntMap была уже пуста.

deleteFindMin :: IntMap a -> ((Key, a), IntMap a) Источник

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

deleteFindMax :: IntMap a -> ((Key, a), IntMap a) Источник

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

updateMin :: (a -> Maybe a) -> IntMap a -> IntMap a Источник

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) -> IntMap a -> IntMap a Источник

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 :: (Key -> a -> Maybe a) -> IntMap a -> IntMap a Источник

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 :: (Key -> a -> Maybe a) -> IntMap a -> IntMap a Источник

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 :: IntMap a -> Maybe (a, IntMap a) Источник

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

maxView :: IntMap a -> Maybe (a, IntMap a) Источник

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

minViewWithKey :: IntMap a -> Maybe ((Key, a), IntMap a) Источник

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

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

maxViewWithKey :: IntMap a -> Maybe ((Key, a), IntMap a) Источник

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

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

Отладка

showTree :: Show a => IntMap a -> String Источник

O(n). Показать дерево, реализующее карту. Дерево отображается в сжатом, висящем формате.

showTreeWith :: Show a => Bool -> Bool -> IntMap a -> String Исходный код

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