Data.IntMap.Lazy

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

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

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

• Аргументы ключей вычисляются до WHNF

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

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

Тип Map

data IntMap a Источник

Словарь целых чисел со значениями a.

type Ключ = Int Источник

Операторы

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

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

То же, что и difference.

Запрос

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

O(1). Является ли словарь пустым?

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

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

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

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

member :: Ключ -> IntMap a -> Bool Источник

O(min(n,W)). Принадлежит ли ключ словарю?

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

notMember :: Ключ -> IntMap a -> Bool Источник

O(min(n,W)). Не принадлежит ли ключ словарю?

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

lookup :: Ключ -> IntMap a -> Maybe a Источник

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

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

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

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

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

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

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

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

lookupLE :: Ключ -> IntMap a -> МожетБыть (Ключ, a) Источник

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 :: Ключ -> IntMap a -> МожетБыть (Ключ, a) Источник

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

O(1). Пустой словарь.

empty      == fromList []
size empty == 0

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

O(1). Словарь из одного элемента.

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

Вставка

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

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

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

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"

insertLookupWithKey :: (Ключ -> a -> a -> a) -> Ключ -> a -> IntMap a -> (МожетБыть a, IntMap a) Источник

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 :: Ключ -> IntMap a -> IntMap a Источник

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

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

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 -> МожетБыть a) -> Ключ -> IntMap a -> IntMap a Источник

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 :: (Ключ -> a -> МожетБыть a) -> Ключ -> IntMap a -> IntMap a Источник

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 :: (Ключ -> a -> МожетБыть a) -> Ключ -> IntMap a -> (МожетБыть a, IntMap a) Источник

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 :: (МожетБыть a -> МожетБыть a) -> Ключ -> IntMap a -> IntMap a Источник

O(min(n,W)). Выражение (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 Источник

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

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

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

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

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). (Левостороннее) пересечение двух словарей (по ключам).

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

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

O(n*min(n,W)). 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 :: (Key -> Key) -> IntMap a -> IntMap a Source

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

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

foldMapWithKey f = fold . mapWithKey f

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

Жесткие склады

foldr' :: (a -> b -> b) -> b -> IntMap a -> b Source

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

foldl' :: (a -> b -> a) -> a -> IntMap b -> a Source

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

foldrWithKey' :: (Key -> a -> b -> b) -> b -> IntMap a -> b Source

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

foldlWithKey' :: (a -> Key -> b -> a) -> a -> IntMap b -> a Source

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

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

elems :: IntMap a -> [a] Source

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

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

keys :: IntMap a -> [Key] Source

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

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

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

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

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

keysSet :: IntMap a -> IntSet Source

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

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

fromSet :: (Key -> a) -> IntSet -> IntMap a Source

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

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

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

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

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,"c")] == fromList [(3, "ab"), (5, "cba")]
fromListWith (++) [] == empty

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

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

let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")] == fromList [(3, "3:a|b"), (5, "5:c|5:b|a")]
fromListWithKey f [] == 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). Построение карты из списка пар ключ/значение, где ключи расположены в порядке возрастания, с функцией комбинирования для одинаковых ключей. Предпосылка (входной список отсортирован по возрастанию) не проверяется.

let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "5:b|a")]

fromDistinctAscList :: forall a. [(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). Преобразование значений и сбор результатов.

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). Преобразование ключей/значений и сбор результатов.

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). Преобразование значений и разделение результатов на два набора.

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). Преобразование ключей/значений и разделение результатов на два набора.

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)). Выполняет операцию разделения, но также возвращает, найден ли ключевой элемент в исходной карте.

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 Source

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

isSubmapOfBy :: (a -> b -> Bool) -> IntMap a -> IntMap b -> Bool Source

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 Source

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

isProperSubmapOfBy :: (a -> b -> Bool) -> IntMap a -> IntMap 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)])

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

findMin :: IntMap a -> (Key, a) Source

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

findMax :: IntMap a -> (Key, a) Source

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

deleteMin :: IntMap a -> IntMap a Source

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

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

deleteMax :: IntMap a -> IntMap a Source

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

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

deleteFindMin :: IntMap a -> ((Key, a), IntMap a) Source

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

deleteFindMax :: IntMap a -> ((Key, a), IntMap a) Source

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

updateMin :: (a -> Maybe a) -> IntMap a -> IntMap a Source

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

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 Source

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

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 Source

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

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 Source

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

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

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

maxView :: IntMap a -> Maybe (a, IntMap a) Source

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

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

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

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 Source

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

showTreeWith :: Show a => Bool -> Bool -> IntMap a -> String Source

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