-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Assorted concrete container types
--
-- This package contains efficient general-purpose implementations of
-- various basic immutable container types. The declared cost of each
-- operation is either worst-case or amortized, but remains valid even if
-- structures are shared.
@package containers
@version 0.5.8.2
-- | An efficient implementation of sets.
--
-- These modules are intended to be imported qualified, to avoid name
-- clashes with Prelude functions, e.g.
--
--
-- import Data.Set (Set)
-- import qualified Data.Set as Set
--
--
-- The implementation of Set is based on size balanced
-- binary trees (or trees of bounded balance) as described by:
--
--
-- - Stephen Adams, "Efficient sets: a balancing act", Journal
-- of Functional Programming 3(4):553-562, October 1993,
-- http://www.swiss.ai.mit.edu/~adams/BB/.
-- - J. Nievergelt and E.M. Reingold, "Binary search trees of
-- bounded balance", SIAM journal of computing 2(1), March 1973.
--
--
-- Bounds for union, intersection, and difference
-- are as given by
--
--
--
-- Note that the implementation is left-biased -- the elements of
-- a first argument are always preferred to the second, for example in
-- union or insert. Of course, left-biasing can only be
-- observed when equality is an equivalence relation instead of
-- structural equality.
--
-- Warning: The size of the set must not exceed
-- maxBound::Int. Violation of this condition is not detected
-- and if the size limit is exceeded, its behaviour is undefined.
module Data.Set
-- | A set of values a.
data Set a
-- | O(m*log(n/m+1)), m <= n. See difference.
(\\) :: Ord a => Set a -> Set a -> Set a
infixl 9 \\
-- | O(1). Is this the empty set?
null :: Set a -> Bool
-- | O(1). The number of elements in the set.
size :: Set a -> Int
-- | O(log n). Is the element in the set?
member :: Ord a => a -> Set a -> Bool
-- | O(log n). Is the element not in the set?
notMember :: Ord a => a -> Set a -> Bool
-- | O(log n). Find largest element smaller than the given one.
--
--
-- lookupLT 3 (fromList [3, 5]) == Nothing
-- lookupLT 5 (fromList [3, 5]) == Just 3
--
lookupLT :: Ord a => a -> Set a -> Maybe a
-- | O(log n). Find smallest element greater than the given one.
--
--
-- lookupGT 4 (fromList [3, 5]) == Just 5
-- lookupGT 5 (fromList [3, 5]) == Nothing
--
lookupGT :: Ord a => a -> Set a -> Maybe a
-- | O(log n). Find largest element smaller or equal to the given
-- one.
--
--
-- lookupLE 2 (fromList [3, 5]) == Nothing
-- lookupLE 4 (fromList [3, 5]) == Just 3
-- lookupLE 5 (fromList [3, 5]) == Just 5
--
lookupLE :: Ord a => a -> Set a -> Maybe a
-- | O(log n). Find smallest element greater or equal to the given
-- one.
--
--
-- lookupGE 3 (fromList [3, 5]) == Just 3
-- lookupGE 4 (fromList [3, 5]) == Just 5
-- lookupGE 6 (fromList [3, 5]) == Nothing
--
lookupGE :: Ord a => a -> Set a -> Maybe a
-- | O(n+m). Is this a subset? (s1 isSubsetOf s2)
-- tells whether s1 is a subset of s2.
isSubsetOf :: Ord a => Set a -> Set a -> Bool
-- | O(n+m). Is this a proper subset? (ie. a subset but not equal).
isProperSubsetOf :: Ord a => Set a -> Set a -> Bool
-- | O(1). The empty set.
empty :: Set a
-- | O(1). Create a singleton set.
singleton :: a -> Set a
-- | O(log n). Insert an element in a set. If the set already
-- contains an element equal to the given value, it is replaced with the
-- new value.
insert :: Ord a => a -> Set a -> Set a
-- | O(log n). Delete an element from a set.
delete :: Ord a => a -> Set a -> Set a
-- | O(m*log(nm + 1)), m <= n/. The union of two sets, preferring
-- the first set when equal elements are encountered.
union :: Ord a => Set a -> Set a -> Set a
-- | The union of a list of sets: (unions == foldl
-- union empty).
unions :: Ord a => [Set a] -> Set a
-- | O(m*log(nm + 1)), m <= n/. Difference of two sets.
difference :: Ord a => Set a -> Set a -> Set a
-- | O(m*log(nm + 1)), m <= n/. The intersection of two sets.
-- Elements of the result come from the first set, so for example
--
--
-- import qualified Data.Set as S
-- data AB = A | B deriving Show
-- instance Ord AB where compare _ _ = EQ
-- instance Eq AB where _ == _ = True
-- main = print (S.singleton A `S.intersection` S.singleton B,
-- S.singleton B `S.intersection` S.singleton A)
--
--
-- prints (fromList [A],fromList [B]).
intersection :: Ord a => Set a -> Set a -> Set a
-- | O(n). Filter all elements that satisfy the predicate.
filter :: (a -> Bool) -> Set a -> Set a
-- | O(log n). Take while a predicate on the elements holds. The
-- user is responsible for ensuring that for all elements j and
-- k in the set, j < k ==> p j >= p k. See
-- note at spanAntitone.
--
--
-- takeWhileAntitone p = fromDistinctAscList . takeWhile p . toList
-- takeWhileAntitone p = filter p
--
takeWhileAntitone :: (a -> Bool) -> Set a -> Set a
-- | O(log n). Drop while a predicate on the elements holds. The
-- user is responsible for ensuring that for all elements j and
-- k in the set, j < k ==> p j >= p k. See
-- note at spanAntitone.
--
--
-- dropWhileAntitone p = fromDistinctAscList . dropWhile p . toList
-- dropWhileAntitone p = filter (not . p)
--
dropWhileAntitone :: (a -> Bool) -> Set a -> Set a
-- | O(log n). Divide a set at the point where a predicate on the
-- elements stops holding. The user is responsible for ensuring that for
-- all elements j and k in the set, j < k ==>
-- p j >= p k.
--
--
-- spanAntitone p xs = (takeWhileAntitone p xs, dropWhileAntitone p xs)
-- spanAntitone p xs = partition p xs
--
--
-- Note: if p is not actually antitone, then
-- spanAntitone will split the set at some unspecified
-- point where the predicate switches from holding to not holding (where
-- the predicate is seen to hold before the first element and to fail
-- after the last element).
spanAntitone :: (a -> Bool) -> Set a -> (Set a, Set a)
-- | O(n). Partition the set into two sets, one with all elements
-- that satisfy the predicate and one with all elements that don't
-- satisfy the predicate. See also split.
partition :: (a -> Bool) -> Set a -> (Set a, Set a)
-- | O(log n). The expression (split x set) is a
-- pair (set1,set2) where set1 comprises the elements
-- of set less than x and set2 comprises the
-- elements of set greater than x.
split :: Ord a => a -> Set a -> (Set a, Set a)
-- | O(log n). Performs a split but also returns whether the
-- pivot element was found in the original set.
splitMember :: Ord a => a -> Set a -> (Set a, Bool, Set a)
-- | O(1). Decompose a set into pieces based on the structure of the
-- underlying tree. This function is useful for consuming a set in
-- parallel.
--
-- No guarantee is made as to the sizes of the pieces; an internal, but
-- deterministic process determines this. However, it is guaranteed that
-- the pieces returned will be in ascending order (all elements in the
-- first subset less than all elements in the second, and so on).
--
-- Examples:
--
--
-- splitRoot (fromList [1..6]) ==
-- [fromList [1,2,3],fromList [4],fromList [5,6]]
--
--
--
-- splitRoot empty == []
--
--
-- Note that the current implementation does not return more than three
-- subsets, but you should not depend on this behaviour because it can
-- change in the future without notice.
splitRoot :: Set a -> [Set a]
-- | O(log n). Lookup the index of an element, which is its
-- zero-based index in the sorted sequence of elements. The index is a
-- number from 0 up to, but not including, the size of the
-- set.
--
--
-- isJust (lookupIndex 2 (fromList [5,3])) == False
-- fromJust (lookupIndex 3 (fromList [5,3])) == 0
-- fromJust (lookupIndex 5 (fromList [5,3])) == 1
-- isJust (lookupIndex 6 (fromList [5,3])) == False
--
lookupIndex :: Ord a => a -> Set a -> Maybe Int
-- | O(log n). Return the index of an element, which is its
-- zero-based index in the sorted sequence of elements. The index is a
-- number from 0 up to, but not including, the size of the
-- set. Calls error when the element is not a member of the
-- set.
--
--
-- findIndex 2 (fromList [5,3]) Error: element is not in the set
-- findIndex 3 (fromList [5,3]) == 0
-- findIndex 5 (fromList [5,3]) == 1
-- findIndex 6 (fromList [5,3]) Error: element is not in the set
--
findIndex :: Ord a => a -> Set a -> Int
-- | O(log n). Retrieve an element by its index, i.e. by its
-- zero-based index in the sorted sequence of elements. If the
-- index is out of range (less than zero, greater or equal to
-- size of the set), error is called.
--
--
-- elemAt 0 (fromList [5,3]) == 3
-- elemAt 1 (fromList [5,3]) == 5
-- elemAt 2 (fromList [5,3]) Error: index out of range
--
elemAt :: Int -> Set a -> a
-- | O(log n). Delete the element at index, i.e. by its
-- zero-based index in the sorted sequence of elements. If the
-- index is out of range (less than zero, greater or equal to
-- size of the set), error is called.
--
--
-- deleteAt 0 (fromList [5,3]) == singleton 5
-- deleteAt 1 (fromList [5,3]) == singleton 3
-- deleteAt 2 (fromList [5,3]) Error: index out of range
-- deleteAt (-1) (fromList [5,3]) Error: index out of range
--
deleteAt :: Int -> Set a -> Set a
-- | Take a given number of elements in order, beginning with the smallest
-- ones.
--
--
-- take n = fromDistinctAscList . take n . toAscList
--
take :: Int -> Set a -> Set a
-- | Drop a given number of elements in order, beginning with the smallest
-- ones.
--
--
-- drop n = fromDistinctAscList . drop n . toAscList
--
drop :: Int -> Set a -> Set a
-- | O(log n). Split a set at a particular index.
--
--
-- splitAt !n !xs = (take n xs, drop n xs)
--
splitAt :: Int -> Set a -> (Set a, Set a)
-- | O(n*log n). map f s is the set obtained by
-- applying f to each element of s.
--
-- It's worth noting that the size of the result may be smaller if, for
-- some (x,y), x /= y && f x == f y
map :: Ord b => (a -> b) -> Set a -> Set b
-- | O(n). The
--
-- mapMonotonic f s == map f s, but works only
-- when f is strictly increasing. The precondition is not
-- checked. Semi-formally, we have:
--
--
-- and [x < y ==> f x < f y | x <- ls, y <- ls]
-- ==> mapMonotonic f s == map f s
-- where ls = toList s
--
mapMonotonic :: (a -> b) -> Set a -> Set b
-- | O(n). Fold the elements in the set using the given
-- right-associative binary operator, such that foldr f z ==
-- foldr f z . toAscList.
--
-- For example,
--
--
-- toAscList set = foldr (:) [] set
--
foldr :: (a -> b -> b) -> b -> Set a -> b
-- | O(n). Fold the elements in the set using the given
-- left-associative binary operator, such that foldl f z ==
-- foldl f z . toAscList.
--
-- For example,
--
--
-- toDescList set = foldl (flip (:)) [] set
--
foldl :: (a -> b -> a) -> a -> Set b -> a
-- | O(n). A strict version of foldr. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> Set a -> b
-- | O(n). A strict version of foldl. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldl' :: (a -> b -> a) -> a -> Set b -> a
-- | O(n). Fold the elements in the set using the given
-- right-associative binary operator. This function is an equivalent of
-- foldr and is present for compatibility only.
--
-- Please note that fold will be deprecated in the future and
-- removed.
fold :: (a -> b -> b) -> b -> Set a -> b
-- | O(log n). The minimal element of a set.
findMin :: Set a -> a
-- | O(log n). The maximal element of a set.
findMax :: Set a -> a
-- | O(log n). Delete the minimal element. Returns an empty set if
-- the set is empty.
deleteMin :: Set a -> Set a
-- | O(log n). Delete the maximal element. Returns an empty set if
-- the set is empty.
deleteMax :: Set a -> Set a
-- | O(log n). Delete and find the minimal element.
--
--
-- deleteFindMin set = (findMin set, deleteMin set)
--
deleteFindMin :: Set a -> (a, Set a)
-- | O(log n). Delete and find the maximal element.
--
--
-- deleteFindMax set = (findMax set, deleteMax set)
--
deleteFindMax :: Set a -> (a, Set a)
-- | O(log n). Retrieves the maximal key of the set, and the set
-- stripped of that element, or Nothing if passed an empty set.
maxView :: Set a -> Maybe (a, Set a)
-- | O(log n). Retrieves the minimal key of the set, and the set
-- stripped of that element, or Nothing if passed an empty set.
minView :: Set a -> Maybe (a, Set a)
-- | O(n). An alias of toAscList. The elements of a set in
-- ascending order. Subject to list fusion.
elems :: Set a -> [a]
-- | O(n). Convert the set to a list of elements. Subject to list
-- fusion.
toList :: Set a -> [a]
-- | O(n*log n). Create a set from a list of elements.
--
-- If the elements are ordered, a linear-time implementation is used,
-- with the performance equal to fromDistinctAscList.
fromList :: Ord a => [a] -> Set a
-- | O(n). Convert the set to an ascending list of elements. Subject
-- to list fusion.
toAscList :: Set a -> [a]
-- | O(n). Convert the set to a descending list of elements. Subject
-- to list fusion.
toDescList :: Set a -> [a]
-- | O(n). Build a set from an ascending list in linear time. The
-- precondition (input list is ascending) is not checked.
fromAscList :: Eq a => [a] -> Set a
-- | O(n). Build a set from a descending list in linear time. The
-- precondition (input list is descending) is not checked.
fromDescList :: Eq a => [a] -> Set a
-- | O(n). Build a set from an ascending list of distinct elements
-- in linear time. The precondition (input list is strictly ascending)
-- is not checked.
fromDistinctAscList :: [a] -> Set a
-- | O(n). Build a set from a descending list of distinct elements
-- in linear time. The precondition (input list is strictly
-- descending) is not checked.
fromDistinctDescList :: [a] -> Set a
-- | O(n). Show the tree that implements the set. The tree is shown
-- in a compressed, hanging format.
showTree :: Show a => Set a -> String
-- | O(n). The expression (showTreeWith hang wide map)
-- shows the tree that implements the set. If hang is
-- True, a hanging tree is shown otherwise a rotated tree
-- is shown. If wide is True, an extra wide version is
-- shown.
--
--
-- Set> putStrLn $ showTreeWith True False $ fromDistinctAscList [1..5]
-- 4
-- +--2
-- | +--1
-- | +--3
-- +--5
--
-- Set> putStrLn $ showTreeWith True True $ fromDistinctAscList [1..5]
-- 4
-- |
-- +--2
-- | |
-- | +--1
-- | |
-- | +--3
-- |
-- +--5
--
-- Set> putStrLn $ showTreeWith False True $ fromDistinctAscList [1..5]
-- +--5
-- |
-- 4
-- |
-- | +--3
-- | |
-- +--2
-- |
-- +--1
--
showTreeWith :: Show a => Bool -> Bool -> Set a -> String
-- | O(n). Test if the internal set structure is valid.
valid :: Ord a => Set a -> Bool
-- | General purpose finite sequences. Apart from being finite and having
-- strict operations, sequences also differ from lists in supporting a
-- wider variety of operations efficiently.
--
-- An amortized running time is given for each operation, with n
-- referring to the length of the sequence and i being the
-- integral index used by some operations. These bounds hold even in a
-- persistent (shared) setting.
--
-- The implementation uses 2-3 finger trees annotated with sizes, as
-- described in section 4.2 of
--
--
--
-- Note: Many of these operations have the same names as similar
-- operations on lists in the Prelude. The ambiguity may be
-- resolved using either qualification or the hiding clause.
--
-- Warning: The size of a Seq must not exceed
-- maxBound::Int. Violation of this condition is not detected
-- and if the size limit is exceeded, the behaviour of the sequence is
-- undefined. This is unlikely to occur in most applications, but some
-- care may be required when using ><, <*>,
-- *>, or >>, particularly repeatedly and
-- particularly in combination with replicate or
-- fromFunction.
module Data.Sequence
-- | General-purpose finite sequences.
data Seq a
-- | O(1). The empty sequence.
empty :: Seq a
-- | O(1). A singleton sequence.
singleton :: a -> Seq a
-- | O(1). Add an element to the left end of a sequence. Mnemonic: a
-- triangle with the single element at the pointy end.
(<|) :: a -> Seq a -> Seq a
infixr 5 <|
-- | O(1). Add an element to the right end of a sequence. Mnemonic:
-- a triangle with the single element at the pointy end.
(|>) :: Seq a -> a -> Seq a
infixl 5 |>
-- | O(log(min(n1,n2))). Concatenate two sequences.
(><) :: Seq a -> Seq a -> Seq a
infixr 5 ><
-- | O(n). Create a sequence from a finite list of elements. There
-- is a function toList in the opposite direction for all
-- instances of the Foldable class, including Seq.
fromList :: [a] -> Seq a
-- | O(n). Convert a given sequence length and a function
-- representing that sequence into a sequence.
fromFunction :: Int -> (Int -> a) -> Seq a
-- | O(n). Create a sequence consisting of the elements of an
-- Array. Note that the resulting sequence elements may be
-- evaluated lazily (as on GHC), so you must force the entire structure
-- to be sure that the original array can be garbage-collected.
fromArray :: Ix i => Array i a -> Seq a
-- | O(log n). replicate n x is a sequence consisting of
-- n copies of x.
replicate :: Int -> a -> Seq a
-- | replicateA is an Applicative version of
-- replicate, and makes O(log n) calls to <*>
-- and pure.
--
--
-- replicateA n x = sequenceA (replicate n x)
--
replicateA :: Applicative f => Int -> f a -> f (Seq a)
-- | replicateM is a sequence counterpart of replicateM.
--
--
-- replicateM n x = sequence (replicate n x)
--
replicateM :: Monad m => Int -> m a -> m (Seq a)
-- | O(log(k)). cycleTaking k xs forms a sequence of
-- length k by repeatedly concatenating xs with itself.
-- xs may only be empty if k is 0.
--
--
-- cycleTaking k = fromList . take k . cycle . toList
--
cycleTaking :: Int -> Seq a -> Seq a
-- | O(n). Constructs a sequence by repeated application of a
-- function to a seed value.
--
--
-- iterateN n f x = fromList (Prelude.take n (Prelude.iterate f x))
--
iterateN :: Int -> (a -> a) -> a -> Seq a
-- | Builds a sequence from a seed value. Takes time linear in the number
-- of generated elements. WARNING: If the number of generated
-- elements is infinite, this method will not terminate.
unfoldr :: (b -> Maybe (a, b)) -> b -> Seq a
-- | unfoldl f x is equivalent to reverse
-- (unfoldr (fmap swap . f) x).
unfoldl :: (b -> Maybe (b, a)) -> b -> Seq a
-- | O(1). Is this the empty sequence?
null :: Seq a -> Bool
-- | O(1). The number of elements in the sequence.
length :: Seq a -> Int
-- | View of the left end of a sequence.
data ViewL a
-- | empty sequence
EmptyL :: ViewL a
-- | leftmost element and the rest of the sequence
(:<) :: a -> Seq a -> ViewL a
-- | O(1). Analyse the left end of a sequence.
viewl :: Seq a -> ViewL a
-- | View of the right end of a sequence.
data ViewR a
-- | empty sequence
EmptyR :: ViewR a
-- | the sequence minus the rightmost element, and the rightmost element
(:>) :: Seq a -> a -> ViewR a
-- | O(1). Analyse the right end of a sequence.
viewr :: Seq a -> ViewR a
-- | scanl is similar to foldl, but returns a sequence of
-- reduced values from the left:
--
--
-- scanl f z (fromList [x1, x2, ...]) = fromList [z, z `f` x1, (z `f` x1) `f` x2, ...]
--
scanl :: (a -> b -> a) -> a -> Seq b -> Seq a
-- | scanl1 is a variant of scanl that has no starting value
-- argument:
--
--
-- scanl1 f (fromList [x1, x2, ...]) = fromList [x1, x1 `f` x2, ...]
--
scanl1 :: (a -> a -> a) -> Seq a -> Seq a
-- | scanr is the right-to-left dual of scanl.
scanr :: (a -> b -> b) -> b -> Seq a -> Seq b
-- | scanr1 is a variant of scanr that has no starting value
-- argument.
scanr1 :: (a -> a -> a) -> Seq a -> Seq a
-- | O(n). Returns a sequence of all suffixes of this sequence,
-- longest first. For example,
--
--
-- tails (fromList "abc") = fromList [fromList "abc", fromList "bc", fromList "c", fromList ""]
--
--
-- Evaluating the ith suffix takes O(log(min(i, n-i))), but
-- evaluating every suffix in the sequence takes O(n) due to
-- sharing.
tails :: Seq a -> Seq (Seq a)
-- | O(n). Returns a sequence of all prefixes of this sequence,
-- shortest first. For example,
--
--
-- inits (fromList "abc") = fromList [fromList "", fromList "a", fromList "ab", fromList "abc"]
--
--
-- Evaluating the ith prefix takes O(log(min(i, n-i))), but
-- evaluating every prefix in the sequence takes O(n) due to
-- sharing.
inits :: Seq a -> Seq (Seq a)
-- | O(n). chunksOf n xs splits xs into chunks of
-- size n>0. If n does not divide the length of
-- xs evenly, then the last element of the result will be short.
chunksOf :: Int -> Seq a -> Seq (Seq a)
-- | O(i) where i is the prefix length. takeWhileL,
-- applied to a predicate p and a sequence xs, returns
-- the longest prefix (possibly empty) of xs of elements that
-- satisfy p.
takeWhileL :: (a -> Bool) -> Seq a -> Seq a
-- | O(i) where i is the suffix length. takeWhileR,
-- applied to a predicate p and a sequence xs, returns
-- the longest suffix (possibly empty) of xs of elements that
-- satisfy p.
--
-- takeWhileR p xs is equivalent to reverse
-- (takeWhileL p (reverse xs)).
takeWhileR :: (a -> Bool) -> Seq a -> Seq a
-- | O(i) where i is the prefix length. dropWhileL
-- p xs returns the suffix remaining after takeWhileL p
-- xs.
dropWhileL :: (a -> Bool) -> Seq a -> Seq a
-- | O(i) where i is the suffix length. dropWhileR
-- p xs returns the prefix remaining after takeWhileR p
-- xs.
--
-- dropWhileR p xs is equivalent to reverse
-- (dropWhileL p (reverse xs)).
dropWhileR :: (a -> Bool) -> Seq a -> Seq a
-- | O(i) where i is the prefix length. spanl, applied
-- to a predicate p and a sequence xs, returns a pair
-- whose first element is the longest prefix (possibly empty) of
-- xs of elements that satisfy p and the second element
-- is the remainder of the sequence.
spanl :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
-- | O(i) where i is the suffix length. spanr, applied
-- to a predicate p and a sequence xs, returns a pair
-- whose first element is the longest suffix (possibly
-- empty) of xs of elements that satisfy p and the
-- second element is the remainder of the sequence.
spanr :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
-- | O(i) where i is the breakpoint index. breakl,
-- applied to a predicate p and a sequence xs, returns
-- a pair whose first element is the longest prefix (possibly empty) of
-- xs of elements that do not satisfy p and the
-- second element is the remainder of the sequence.
--
-- breakl p is equivalent to spanl (not .
-- p).
breakl :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
-- | breakr p is equivalent to spanr (not .
-- p).
breakr :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
-- | O(n). The partition function takes a predicate
-- p and a sequence xs and returns sequences of those
-- elements which do and do not satisfy the predicate.
partition :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
-- | O(n). The filter function takes a predicate p
-- and a sequence xs and returns a sequence of those elements
-- which satisfy the predicate.
filter :: (a -> Bool) -> Seq a -> Seq a
-- | O(n log n). sort sorts the specified Seq by the
-- natural ordering of its elements. The sort is stable. If stability is
-- not required, unstableSort can be considerably faster, and in
-- particular uses less memory.
sort :: Ord a => Seq a -> Seq a
-- | O(n log n). sortBy sorts the specified Seq
-- according to the specified comparator. The sort is stable. If
-- stability is not required, unstableSortBy can be considerably
-- faster, and in particular uses less memory.
sortBy :: (a -> a -> Ordering) -> Seq a -> Seq a
-- | O(n log n). unstableSort sorts the specified Seq
-- by the natural ordering of its elements, but the sort is not stable.
-- This algorithm is frequently faster and uses less memory than
-- sort, and performs extremely well -- frequently twice as fast
-- as sort -- when the sequence is already nearly sorted.
unstableSort :: Ord a => Seq a -> Seq a
-- | O(n log n). A generalization of unstableSort,
-- unstableSortBy takes an arbitrary comparator and sorts the
-- specified sequence. The sort is not stable. This algorithm is
-- frequently faster and uses less memory than sortBy, and
-- performs extremely well -- frequently twice as fast as sortBy
-- -- when the sequence is already nearly sorted.
unstableSortBy :: (a -> a -> Ordering) -> Seq a -> Seq a
-- | O(log(min(i,n-i))). The element at the specified position,
-- counting from 0. If the specified position is negative or at least the
-- length of the sequence, lookup returns Nothing.
--
--
-- 0 <= i < length xs ==> lookup i xs == Just (toList xs !! i)
--
--
--
-- i < 0 || i >= length xs ==> lookup i xs = Nothing
--
--
-- Unlike index, this can be used to retrieve an element without
-- forcing it. For example, to insert the fifth element of a sequence
-- xs into a Map m at key k, you could
-- use
--
--
-- case lookup 5 xs of
-- Nothing -> m
-- Just x -> insert k x m
--
lookup :: Int -> Seq a -> Maybe a
-- | O(log(min(i,n-i))). A flipped, infix version of lookup.
(!?) :: Seq a -> Int -> Maybe a
-- | O(log(min(i,n-i))). The element at the specified position,
-- counting from 0. The argument should thus be a non-negative integer
-- less than the size of the sequence. If the position is out of range,
-- index fails with an error.
--
--
-- xs `index` i = toList xs !! i
--
--
-- Caution: index necessarily delays retrieving the requested
-- element until the result is forced. It can therefore lead to a space
-- leak if the result is stored, unforced, in another structure. To
-- retrieve an element immediately without forcing it, use lookup
-- or '(!?)'.
index :: Seq a -> Int -> a
-- | O(log(min(i,n-i))). Update the element at the specified
-- position. If the position is out of range, the original sequence is
-- returned. adjust can lead to poor performance and even memory
-- leaks, because it does not force the new value before installing it in
-- the sequence. adjust' should usually be preferred.
adjust :: (a -> a) -> Int -> Seq a -> Seq a
-- | O(log(min(i,n-i))). Update the element at the specified
-- position. If the position is out of range, the original sequence is
-- returned. The new value is forced before it is installed in the
-- sequence.
--
--
-- adjust' f i xs =
-- case xs !? i of
-- Nothing -> xs
-- Just x -> let !x' = f x
-- in update i x' xs
--
adjust' :: forall a. (a -> a) -> Int -> Seq a -> Seq a
-- | O(log(min(i,n-i))). Replace the element at the specified
-- position. If the position is out of range, the original sequence is
-- returned.
update :: Int -> a -> Seq a -> Seq a
-- | O(log(min(i,n-i))). The first i elements of a
-- sequence. If i is negative, take i s yields
-- the empty sequence. If the sequence contains fewer than i
-- elements, the whole sequence is returned.
take :: Int -> Seq a -> Seq a
-- | O(log(min(i,n-i))). Elements of a sequence after the first
-- i. If i is negative, drop i s yields
-- the whole sequence. If the sequence contains fewer than i
-- elements, the empty sequence is returned.
drop :: Int -> Seq a -> Seq a
-- | O(log(min(i,n-i))). insertAt i x xs inserts
-- x into xs at the index i, shifting the rest
-- of the sequence over.
--
--
-- insertAt 2 x (fromList [a,b,c,d]) = fromList [a,b,x,c,d]
-- insertAt 4 x (fromList [a,b,c,d]) = insertAt 10 x (fromList [a,b,c,d])
-- = fromList [a,b,c,d,x]
--
--
--
-- insertAt i x xs = take i xs >< singleton x >< drop i xs
--
insertAt :: Int -> a -> Seq a -> Seq a
-- | O(log(min(i,n-i))). Delete the element of a sequence at a given
-- index. Return the original sequence if the index is out of range.
--
--
-- deleteAt 2 [a,b,c,d] = [a,b,d]
-- deleteAt 4 [a,b,c,d] = deleteAt (-1) [a,b,c,d] = [a,b,c,d]
--
deleteAt :: Int -> Seq a -> Seq a
-- | O(log(min(i,n-i))). Split a sequence at a given position.
-- splitAt i s = (take i s, drop i s).
splitAt :: Int -> Seq a -> (Seq a, Seq a)
-- | elemIndexL finds the leftmost index of the specified element,
-- if it is present, and otherwise Nothing.
elemIndexL :: Eq a => a -> Seq a -> Maybe Int
-- | elemIndicesL finds the indices of the specified element, from
-- left to right (i.e. in ascending order).
elemIndicesL :: Eq a => a -> Seq a -> [Int]
-- | elemIndexR finds the rightmost index of the specified element,
-- if it is present, and otherwise Nothing.
elemIndexR :: Eq a => a -> Seq a -> Maybe Int
-- | elemIndicesR finds the indices of the specified element, from
-- right to left (i.e. in descending order).
elemIndicesR :: Eq a => a -> Seq a -> [Int]
-- | findIndexL p xs finds the index of the leftmost
-- element that satisfies p, if any exist.
findIndexL :: (a -> Bool) -> Seq a -> Maybe Int
-- | findIndicesL p finds all indices of elements that
-- satisfy p, in ascending order.
findIndicesL :: (a -> Bool) -> Seq a -> [Int]
-- | findIndexR p xs finds the index of the rightmost
-- element that satisfies p, if any exist.
findIndexR :: (a -> Bool) -> Seq a -> Maybe Int
-- | findIndicesR p finds all indices of elements that
-- satisfy p, in descending order.
findIndicesR :: (a -> Bool) -> Seq a -> [Int]
-- | O(n). A generalization of foldMap,
-- foldMapWithIndex takes a folding function that also depends on
-- the element's index, and applies it to every element in the sequence.
foldMapWithIndex :: Monoid m => (Int -> a -> m) -> Seq a -> m
-- | foldlWithIndex is a version of foldl that also provides
-- access to the index of each element.
foldlWithIndex :: (b -> Int -> a -> b) -> b -> Seq a -> b
-- | foldrWithIndex is a version of foldr that also provides
-- access to the index of each element.
foldrWithIndex :: (Int -> a -> b -> b) -> b -> Seq a -> b
-- | O(n). A generalization of fmap, mapWithIndex
-- takes a mapping function that also depends on the element's index, and
-- applies it to every element in the sequence.
mapWithIndex :: (Int -> a -> b) -> Seq a -> Seq b
-- | traverseWithIndex is a version of traverse that also
-- offers access to the index of each element.
traverseWithIndex :: Applicative f => (Int -> a -> f b) -> Seq a -> f (Seq b)
-- | O(n). The reverse of a sequence.
reverse :: Seq a -> Seq a
-- | Intersperse an element between the elements of a sequence.
--
--
-- intersperse a empty = empty
-- intersperse a (singleton x) = singleton x
-- intersperse a (fromList [x,y]) = fromList [x,a,y]
-- intersperse a (fromList [x,y,z]) = fromList [x,a,y,a,z]
--
intersperse :: a -> Seq a -> Seq a
-- | O(min(n1,n2)). zip takes two sequences and returns a
-- sequence of corresponding pairs. If one input is short, excess
-- elements are discarded from the right end of the longer sequence.
zip :: Seq a -> Seq b -> Seq (a, b)
-- | O(min(n1,n2)). zipWith generalizes zip by zipping
-- with the function given as the first argument, instead of a tupling
-- function. For example, zipWith (+) is applied to two
-- sequences to take the sequence of corresponding sums.
zipWith :: (a -> b -> c) -> Seq a -> Seq b -> Seq c
-- | O(min(n1,n2,n3)). zip3 takes three sequences and returns
-- a sequence of triples, analogous to zip.
zip3 :: Seq a -> Seq b -> Seq c -> Seq (a, b, c)
-- | O(min(n1,n2,n3)). zipWith3 takes a function which
-- combines three elements, as well as three sequences and returns a
-- sequence of their point-wise combinations, analogous to
-- zipWith.
zipWith3 :: (a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
-- | O(min(n1,n2,n3,n4)). zip4 takes four sequences and
-- returns a sequence of quadruples, analogous to zip.
zip4 :: Seq a -> Seq b -> Seq c -> Seq d -> Seq (a, b, c, d)
-- | O(min(n1,n2,n3,n4)). zipWith4 takes a function which
-- combines four elements, as well as four sequences and returns a
-- sequence of their point-wise combinations, analogous to
-- zipWith.
zipWith4 :: (a -> b -> c -> d -> e) -> Seq a -> Seq b -> Seq c -> Seq d -> Seq e
-- | Multi-way trees (aka rose trees) and forests.
module Data.Tree
-- | Multi-way trees, also known as rose trees.
data Tree a
Node :: a -> Forest a -> Tree a
-- | label value
[rootLabel] :: Tree a -> a
-- | zero or more child trees
[subForest] :: Tree a -> Forest a
type Forest a = [Tree a]
-- | Neat 2-dimensional drawing of a tree.
drawTree :: Tree String -> String
-- | Neat 2-dimensional drawing of a forest.
drawForest :: Forest String -> String
-- | The elements of a tree in pre-order.
flatten :: Tree a -> [a]
-- | Lists of nodes at each level of the tree.
levels :: Tree a -> [[a]]
-- | Catamorphism on trees.
foldTree :: (a -> [b] -> b) -> Tree a -> b
-- | Build a tree from a seed value
unfoldTree :: (b -> (a, [b])) -> b -> Tree a
-- | Build a forest from a list of seed values
unfoldForest :: (b -> (a, [b])) -> [b] -> Forest a
-- | Monadic tree builder, in depth-first order
unfoldTreeM :: Monad m => (b -> m (a, [b])) -> b -> m (Tree a)
-- | Monadic forest builder, in depth-first order
unfoldForestM :: Monad m => (b -> m (a, [b])) -> [b] -> m (Forest a)
-- | Monadic tree builder, in breadth-first order, using an algorithm
-- adapted from Breadth-First Numbering: Lessons from a Small Exercise
-- in Algorithm Design, by Chris Okasaki, ICFP'00.
unfoldTreeM_BF :: Monad m => (b -> m (a, [b])) -> b -> m (Tree a)
-- | Monadic forest builder, in breadth-first order, using an algorithm
-- adapted from Breadth-First Numbering: Lessons from a Small Exercise
-- in Algorithm Design, by Chris Okasaki, ICFP'00.
unfoldForestM_BF :: Monad m => (b -> m (a, [b])) -> [b] -> m (Forest a)
instance GHC.Generics.Generic1 Data.Tree.Tree
instance GHC.Generics.Generic (Data.Tree.Tree a)
instance Data.Data.Data a => Data.Data.Data (Data.Tree.Tree a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Tree.Tree a)
instance GHC.Read.Read a => GHC.Read.Read (Data.Tree.Tree a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Tree.Tree a)
instance GHC.Base.Functor Data.Tree.Tree
instance GHC.Base.Applicative Data.Tree.Tree
instance GHC.Base.Monad Data.Tree.Tree
instance Data.Traversable.Traversable Data.Tree.Tree
instance Data.Foldable.Foldable Data.Tree.Tree
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Tree.Tree a)
-- | An efficient implementation of ordered maps from keys to values
-- (dictionaries).
--
-- API of this module is strict in the keys, but lazy in the values. If
-- you need value-strict maps, use Data.Map.Strict instead. The
-- Map type itself is shared between the lazy and strict modules,
-- meaning that the same Map value can be passed to functions in
-- both modules (although that is rarely needed).
--
-- These modules are intended to be imported qualified, to avoid name
-- clashes with Prelude functions, e.g.
--
--
-- import qualified Data.Map.Lazy as Map
--
--
-- The implementation of Map is based on size balanced
-- binary trees (or trees of bounded balance) as described by:
--
--
-- - Stephen Adams, "Efficient sets: a balancing act", Journal
-- of Functional Programming 3(4):553-562, October 1993,
-- http://www.swiss.ai.mit.edu/~adams/BB/.
-- - J. Nievergelt and E.M. Reingold, "Binary search trees of
-- bounded balance", SIAM journal of computing 2(1), March 1973.
--
--
-- Bounds for union, intersection, and difference
-- are as given by
--
--
--
-- Note that the implementation is left-biased -- the elements of
-- a first argument are always preferred to the second, for example in
-- union or insert.
--
-- Warning: The size of the map must not exceed
-- maxBound::Int. Violation of this condition is not detected
-- and if the size limit is exceeded, its behaviour is undefined.
--
-- Operation comments contain the operation time complexity in the Big-O
-- notation (http://en.wikipedia.org/wiki/Big_O_notation).
module Data.Map.Lazy
-- | A Map from keys k to values a.
data Map k a
-- | O(log n). Find the value at a key. Calls error when the
-- element can not be found.
--
--
-- fromList [(5,'a'), (3,'b')] ! 1 Error: element not in the map
-- fromList [(5,'a'), (3,'b')] ! 5 == 'a'
--
(!) :: Ord k => Map k a -> k -> a
infixl 9 !
-- | Same as difference.
(\\) :: Ord k => Map k a -> Map k b -> Map k a
infixl 9 \\
-- | O(1). Is the map empty?
--
--
-- Data.Map.null (empty) == True
-- Data.Map.null (singleton 1 'a') == False
--
null :: Map k a -> Bool
-- | O(1). The number of elements in the map.
--
--
-- size empty == 0
-- size (singleton 1 'a') == 1
-- size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3
--
size :: Map k a -> Int
-- | O(log n). Is the key a member of the map? See also
-- notMember.
--
--
-- member 5 (fromList [(5,'a'), (3,'b')]) == True
-- member 1 (fromList [(5,'a'), (3,'b')]) == False
--
member :: Ord k => k -> Map k a -> Bool
-- | O(log n). Is the key not a member of the map? See also
-- member.
--
--
-- notMember 5 (fromList [(5,'a'), (3,'b')]) == False
-- notMember 1 (fromList [(5,'a'), (3,'b')]) == True
--
notMember :: Ord k => k -> Map k a -> Bool
-- | O(log n). Lookup the value at a key in the map.
--
-- The function will return the corresponding value as (Just
-- value), or Nothing if the key isn't in the map.
--
-- An example of using 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"))
--
--
-- The output of this program:
--
--
-- John's currency: Just "Euro"
-- Pete's currency: Nothing
--
lookup :: Ord k => k -> Map k a -> Maybe a
-- | O(log n). The expression (findWithDefault def k
-- map) returns the value at key k or returns default value
-- def when the key is not in the map.
--
--
-- findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
-- findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
--
findWithDefault :: Ord k => a -> k -> Map k a -> a
-- | O(log n). Find largest key smaller than the given one and
-- return the corresponding (key, value) pair.
--
--
-- lookupLT 3 (fromList [(3,'a'), (5,'b')]) == Nothing
-- lookupLT 4 (fromList [(3,'a'), (5,'b')]) == Just (3, 'a')
--
lookupLT :: Ord k => k -> Map k v -> Maybe (k, v)
-- | O(log n). Find smallest key greater than the given one and
-- return the corresponding (key, value) pair.
--
--
-- lookupGT 4 (fromList [(3,'a'), (5,'b')]) == Just (5, 'b')
-- lookupGT 5 (fromList [(3,'a'), (5,'b')]) == Nothing
--
lookupGT :: Ord k => k -> Map k v -> Maybe (k, v)
-- | O(log n). Find largest key smaller or equal to the given one
-- and return the corresponding (key, value) pair.
--
--
-- 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')
--
lookupLE :: Ord k => k -> Map k v -> Maybe (k, v)
-- | O(log n). Find smallest key greater or equal to the given one
-- and return the corresponding (key, value) pair.
--
--
-- 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
--
lookupGE :: Ord k => k -> Map k v -> Maybe (k, v)
-- | O(1). The empty map.
--
--
-- empty == fromList []
-- size empty == 0
--
empty :: Map k a
-- | O(1). A map with a single element.
--
--
-- singleton 1 'a' == fromList [(1, 'a')]
-- size (singleton 1 'a') == 1
--
singleton :: k -> a -> Map k a
-- | O(log n). Insert a new key and value in the map. If the key is
-- already present in the map, the associated value is replaced with the
-- supplied value. insert is equivalent to 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'
--
insert :: Ord k => k -> a -> Map k a -> Map k a
-- | O(log n). Insert with a function, combining new value and old
-- value. insertWith f key value mp will insert the pair
-- (key, value) into mp if key does not exist in the map. If the
-- key does exist, the function will insert the pair (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"
--
insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
-- | O(log n). Insert with a function, combining key, new value and
-- old value. insertWithKey f key value mp will insert
-- the pair (key, value) into mp if key does not exist in the
-- map. If the key does exist, the function will insert the pair
-- (key,f key new_value old_value). Note that the key passed to
-- f is the same key passed to 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"
--
insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
-- | O(log n). Combines insert operation with old value retrieval.
-- The expression (insertLookupWithKey f k x map) is a
-- pair where the first element is equal to (lookup k
-- map) and the second element equal to (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")
--
--
-- This is how to define insertLookup using
-- 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")])
--
insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
-- | O(log n). Delete a key and its value from the map. When the key
-- is not a member of the map, the original map is returned.
--
--
-- 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
--
delete :: Ord k => k -> Map k a -> Map k a
-- | O(log n). Update a value at a specific key with the result of
-- the provided function. When the key is not a member of the map, the
-- original map is returned.
--
--
-- 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
--
adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k a
-- | O(log n). Adjust a value at a specific key. When the key is not
-- a member of the map, the original map is returned.
--
--
-- 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
--
adjustWithKey :: Ord k => (k -> a -> a) -> k -> Map k a -> Map k a
-- | O(log n). The expression (update f k map)
-- updates the value x at k (if it is in the map). If
-- (f x) is Nothing, the element is deleted. If it is
-- (Just y), the key k is bound to the new value
-- 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"
--
update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
-- | O(log n). The expression (updateWithKey f k
-- map) updates the value x at k (if it is in the
-- map). If (f k x) is Nothing, the element is deleted.
-- If it is (Just y), the key k is bound to the
-- new value 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"
--
updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
-- | O(log n). Lookup and update. See also updateWithKey. The
-- function returns changed value, if it is updated. Returns the original
-- key value if the map entry is deleted.
--
--
-- 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")
--
updateLookupWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
-- | O(log n). The expression (alter f k map) alters
-- the value x at k, or absence thereof. alter
-- can be used to insert, delete, or update a value in a Map. In
-- short : 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")]
--
alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
-- | O(log n). The expression (alterF f k map)
-- alters the value x at k, or absence thereof.
-- alterF can be used to inspect, insert, delete, or update a
-- value in a Map. In short: lookup k <$>
-- alterF f k m = f (lookup k m).
--
-- Example:
--
--
-- interactiveAlter :: Int -> Map Int String -> IO (Map Int String)
-- interactiveAlter k m = alterF f k m where
-- f Nothing -> do
-- putStrLn $ show k ++
-- " was not found in the map. Would you like to add it?"
-- getUserResponse1 :: IO (Maybe String)
-- f (Just old) -> do
-- putStrLn "The key is currently bound to " ++ show old ++
-- ". Would you like to change or delete it?"
-- getUserresponse2 :: IO (Maybe String)
--
--
-- alterF is the most general operation for working with an
-- individual key that may or may not be in a given map. When used with
-- trivial functors like Identity and Const, it is often
-- slightly slower than more specialized combinators like lookup
-- and insert. However, when the functor is non-trivial and key
-- comparison is not particularly cheap, it is the fastest way.
--
-- Note on rewrite rules:
--
-- This module includes GHC rewrite rules to optimize alterF for
-- the Const and Identity functors. In general, these rules
-- improve performance. The sole exception is that when using
-- Identity, deleting a key that is already absent takes longer
-- than it would without the rules. If you expect this to occur a very
-- large fraction of the time, you might consider using a private copy of
-- the Identity type.
--
-- Note: alterF is a flipped version of the at combinator
-- from At.
alterF :: (Functor f, Ord k) => (Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
-- | O(m*log(n/m + 1)), m <= n. The expression (union
-- t1 t2) takes the left-biased union of t1 and
-- t2. It prefers t1 when duplicate keys are
-- encountered, i.e. (union == unionWith
-- const).
--
--
-- union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
--
union :: Ord k => Map k a -> Map k a -> Map k a
-- | O(m*log(n/m + 1)), m <= n. Union with a combining function.
--
--
-- unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
--
unionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
-- | O(m*log(n/m + 1)), m <= n. Union with a combining function.
--
--
-- 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")]
--
unionWithKey :: Ord k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
-- | The union of a list of maps: (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")]
--
unions :: Ord k => [Map k a] -> Map k a
-- | The union of a list of maps, with a combining operation:
-- (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")]
--
unionsWith :: Ord k => (a -> a -> a) -> [Map k a] -> Map k a
-- | O(m*log(n/m + 1)), m <= n. Difference of two maps. Return
-- elements of the first map not existing in the second map.
--
--
-- difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"
--
difference :: Ord k => Map k a -> Map k b -> Map k a
-- | O(n+m). Difference with a combining function. When two equal
-- keys are encountered, the combining function is applied to the values
-- of these keys. If it returns Nothing, the element is discarded
-- (proper set difference). If it returns (Just y), the
-- element is updated with a new value y.
--
--
-- 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"
--
differenceWith :: Ord k => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
-- | O(n+m). Difference with a combining function. When two equal
-- keys are encountered, the combining function is applied to the key and
-- both values. If it returns Nothing, the element is discarded
-- (proper set difference). If it returns (Just y), the
-- element is updated with a new value 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"
--
differenceWithKey :: Ord k => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
-- | O(m*log(n/m + 1)), m <= n. Intersection of two maps. Return
-- data in the first map for the keys existing in both maps.
-- (intersection m1 m2 == intersectionWith const
-- m1 m2).
--
--
-- intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a"
--
intersection :: Ord k => Map k a -> Map k b -> Map k a
-- | O(m*log(n/m + 1)), m <= n. Intersection with a combining
-- function.
--
--
-- intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA"
--
intersectionWith :: Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k c
-- | O(m*log(n/m + 1)), m <= n. Intersection with a combining
-- function.
--
--
-- 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"
--
intersectionWithKey :: Ord k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
-- | O(n+m). An unsafe general combining function.
--
-- WARNING: This function can produce corrupt maps and its results may
-- depend on the internal structures of its inputs. Users should prefer
-- merge or mergeA.
--
-- When mergeWithKey is given three arguments, it is inlined to
-- the call site. You should therefore use mergeWithKey only to
-- define custom combining functions. For example, you could define
-- unionWithKey, differenceWithKey and
-- intersectionWithKey as
--
--
-- 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
--
--
-- When calling mergeWithKey combine only1 only2, a
-- function combining two Maps is created, such that
--
--
-- - if a key is present in both maps, it is passed with both
-- corresponding values to the combine function. Depending on
-- the result, the key is either present in the result with specified
-- value, or is left out;
-- - a nonempty subtree present only in the first map is passed to
-- only1 and the output is added to the result;
-- - a nonempty subtree present only in the second map is passed to
-- only2 and the output is added to the result.
--
--
-- The only1 and only2 methods must return a map
-- with a subset (possibly empty) of the keys of the given map. The
-- values can be modified arbitrarily. Most common variants of
-- only1 and only2 are id and const
-- empty, but for example map f,
-- filterWithKey f, or mapMaybeWithKey f
-- could be used for any f.
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
-- | O(n). Map a function over all values in the map.
--
--
-- map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
--
map :: (a -> b) -> Map k a -> Map k b
-- | O(n). Map a function over all values in the map.
--
--
-- let f key x = (show key) ++ ":" ++ x
-- mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]
--
mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
-- | O(n). traverseWithKey f m == fromList
-- $ traverse ((k, v) -> (,) k $ f k v)
-- (toList m) That is, behaves exactly like a regular
-- traverse except that the traversing function also has access to
-- the key associated with a value.
--
--
-- 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
--
traverseWithKey :: Applicative t => (k -> a -> t b) -> Map k a -> t (Map k b)
-- | O(n). Traverse keys/values and collect the Just results.
traverseMaybeWithKey :: Applicative f => (k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
-- | O(n). The function mapAccum threads an accumulating
-- argument through the map in ascending order of keys.
--
--
-- let f a b = (a ++ b, b ++ "X")
-- mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
--
mapAccum :: (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
-- | 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")])
--
mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
-- | O(n). The function mapAccumR threads an accumulating
-- argument through the map in descending order of keys.
mapAccumRWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
-- | O(n*log n). mapKeys f s is the map obtained by
-- applying f to each key of s.
--
-- The size of the result may be smaller if f maps two or more
-- distinct keys to the same new key. In this case the value at the
-- greatest of the original keys is retained.
--
--
-- 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"
--
mapKeys :: Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
-- | O(n*log n). mapKeysWith c f s is the map
-- obtained by applying f to each key of s.
--
-- The size of the result may be smaller if f maps two or more
-- distinct keys to the same new key. In this case the associated values
-- will be combined using 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"
--
mapKeysWith :: Ord k2 => (a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
-- | O(n). mapKeysMonotonic f s == mapKeys f
-- s, but works only when f is strictly monotonic. That is,
-- for any values x and y, if x <
-- y then f x < f y. The precondition is
-- not checked. Semi-formally, we have:
--
--
-- and [x < y ==> f x < f y | x <- ls, y <- ls]
-- ==> mapKeysMonotonic f s == mapKeys f s
-- where ls = keys s
--
--
-- This means that f maps distinct original keys to distinct
-- resulting keys. This function has better performance than
-- 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
--
mapKeysMonotonic :: (k1 -> k2) -> Map k1 a -> Map k2 a
-- | O(n). Fold the values in the map using the given
-- right-associative binary operator, such that foldr f z ==
-- foldr f z . elems.
--
-- For example,
--
--
-- elems map = foldr (:) [] map
--
--
--
-- let f a len = len + (length a)
-- foldr f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
--
foldr :: (a -> b -> b) -> b -> Map k a -> b
-- | O(n). Fold the values in the map using the given
-- left-associative binary operator, such that foldl f z ==
-- foldl f z . elems.
--
-- For example,
--
--
-- elems = reverse . foldl (flip (:)) []
--
--
--
-- let f len a = len + (length a)
-- foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
--
foldl :: (a -> b -> a) -> a -> Map k b -> a
-- | O(n). Fold the keys and values in the map using the given
-- right-associative binary operator, such that foldrWithKey f
-- z == foldr (uncurry f) z . toAscList.
--
-- For example,
--
--
-- 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)"
--
foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
-- | O(n). Fold the keys and values in the map using the given
-- left-associative binary operator, such that foldlWithKey f
-- z == foldl (\z' (kx, x) -> f z' kx x) z .
-- toAscList.
--
-- For example,
--
--
-- 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)"
--
foldlWithKey :: (a -> k -> b -> a) -> a -> Map k b -> a
-- | O(n). Fold the keys and values in the map using the given
-- monoid, such that
--
--
-- foldMapWithKey f = fold . mapWithKey f
--
--
-- This can be an asymptotically faster than foldrWithKey or
-- foldlWithKey for some monoids.
foldMapWithKey :: Monoid m => (k -> a -> m) -> Map k a -> m
-- | O(n). A strict version of foldr. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> Map k a -> b
-- | O(n). A strict version of foldl. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldl' :: (a -> b -> a) -> a -> Map k b -> a
-- | O(n). A strict version of foldrWithKey. Each application
-- of the operator is evaluated before using the result in the next
-- application. This function is strict in the starting value.
foldrWithKey' :: (k -> a -> b -> b) -> b -> Map k a -> b
-- | O(n). A strict version of foldlWithKey. Each application
-- of the operator is evaluated before using the result in the next
-- application. This function is strict in the starting value.
foldlWithKey' :: (a -> k -> b -> a) -> a -> Map k b -> a
-- | O(n). Return all elements of the map in the ascending order of
-- their keys. Subject to list fusion.
--
--
-- elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]
-- elems empty == []
--
elems :: Map k a -> [a]
-- | O(n). Return all keys of the map in ascending order. Subject to
-- list fusion.
--
--
-- keys (fromList [(5,"a"), (3,"b")]) == [3,5]
-- keys empty == []
--
keys :: Map k a -> [k]
-- | O(n). An alias for toAscList. Return all key/value pairs
-- in the map in ascending key order. Subject to list fusion.
--
--
-- assocs (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
-- assocs empty == []
--
assocs :: Map k a -> [(k, a)]
-- | O(n). The set of all keys of the map.
--
--
-- keysSet (fromList [(5,"a"), (3,"b")]) == Data.Set.fromList [3,5]
-- keysSet empty == Data.Set.empty
--
keysSet :: Map k a -> Set k
-- | O(n). Build a map from a set of keys and a function which for
-- each key computes its value.
--
--
-- fromSet (\k -> replicate k 'a') (Data.Set.fromList [3, 5]) == fromList [(5,"aaaaa"), (3,"aaa")]
-- fromSet undefined Data.Set.empty == empty
--
fromSet :: (k -> a) -> Set k -> Map k a
-- | O(n). Convert the map to a list of key/value pairs. Subject to
-- list fusion.
--
--
-- toList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
-- toList empty == []
--
toList :: Map k a -> [(k, a)]
-- | O(n*log n). Build a map from a list of key/value pairs. See
-- also fromAscList. If the list contains more than one value for
-- the same key, the last value for the key is retained.
--
-- If the keys of the list are ordered, linear-time implementation is
-- used, with the performance equal to 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")]
--
fromList :: Ord k => [(k, a)] -> Map k a
-- | O(n*log n). Build a map from a list of key/value pairs with a
-- combining function. See also fromAscListWith.
--
--
-- fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
-- fromListWith (++) [] == empty
--
fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n*log n). Build a map from a list of key/value pairs with a
-- combining function. See also 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
--
fromListWithKey :: Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n). Convert the map to a list of key/value pairs where the
-- keys are in ascending order. Subject to list fusion.
--
--
-- toAscList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
--
toAscList :: Map k a -> [(k, a)]
-- | O(n). Convert the map to a list of key/value pairs where the
-- keys are in descending order. Subject to list fusion.
--
--
-- toDescList (fromList [(5,"a"), (3,"b")]) == [(5,"a"), (3,"b")]
--
toDescList :: Map k a -> [(k, a)]
-- | O(n). Build a map from an ascending list in linear time. The
-- precondition (input list is ascending) is not checked.
--
--
-- 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
--
fromAscList :: Eq k => [(k, a)] -> Map k a
-- | O(n). Build a map from an ascending list in linear time with a
-- combining function for equal keys. The precondition (input list is
-- ascending) is not checked.
--
--
-- 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
--
fromAscListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n). Build a map from an ascending list in linear time with a
-- combining function for equal keys. The precondition (input list is
-- ascending) is not checked.
--
--
-- 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
--
fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n). Build a map from an ascending list of distinct elements
-- in linear time. The precondition is not checked.
--
--
-- 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
--
fromDistinctAscList :: [(k, a)] -> Map k a
-- | O(n). Build a map from a descending list in linear time. The
-- precondition (input list is descending) is not checked.
--
--
-- fromDescList [(5,"a"), (3,"b")] == fromList [(3, "b"), (5, "a")]
-- fromDescList [(5,"a"), (5,"b"), (3,"b")] == fromList [(3, "b"), (5, "b")]
-- valid (fromDescList [(5,"a"), (5,"b"), (3,"b")]) == True
-- valid (fromDescList [(5,"a"), (3,"b"), (5,"b")]) == False
--
fromDescList :: Eq k => [(k, a)] -> Map k a
-- | O(n). Build a map from a descending list in linear time with a
-- combining function for equal keys. The precondition (input list is
-- descending) is not checked.
--
--
-- fromDescListWith (++) [(5,"a"), (5,"b"), (3,"b")] == fromList [(3, "b"), (5, "ba")]
-- valid (fromDescListWith (++) [(5,"a"), (5,"b"), (3,"b")]) == True
-- valid (fromDescListWith (++) [(5,"a"), (3,"b"), (5,"b")]) == False
--
fromDescListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n). Build a map from a descending list in linear time with a
-- combining function for equal keys. The precondition (input list is
-- descending) is not checked.
--
--
-- let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2
-- fromDescListWithKey f [(5,"a"), (5,"b"), (5,"b"), (3,"b")] == fromList [(3, "b"), (5, "5:b5:ba")]
-- valid (fromDescListWithKey f [(5,"a"), (5,"b"), (5,"b"), (3,"b")]) == True
-- valid (fromDescListWithKey f [(5,"a"), (3,"b"), (5,"b"), (5,"b")]) == False
--
fromDescListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n). Build a map from a descending list of distinct elements
-- in linear time. The precondition is not checked.
--
--
-- fromDistinctDescList [(5,"a"), (3,"b")] == fromList [(3, "b"), (5, "a")]
-- valid (fromDistinctDescList [(5,"a"), (3,"b")]) == True
-- valid (fromDistinctDescList [(5,"a"), (5,"b"), (3,"b")]) == False
--
fromDistinctDescList :: [(k, a)] -> Map k a
-- | O(n). Filter all values that satisfy the predicate.
--
--
-- 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
--
filter :: (a -> Bool) -> Map k a -> Map k a
-- | O(n). Filter all keys/values that satisfy the predicate.
--
--
-- filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--
filterWithKey :: (k -> a -> Bool) -> Map k a -> Map k a
-- | O(m*log(nm + 1)), m <= n/. Restrict a Map to only
-- those keys found in a Set.
--
--
-- m restrictKeys s = filterWithKey (k _ -> k `member' s) m
--
restrictKeys :: Ord k => Map k a -> Set k -> Map k a
-- | O(m*log(nm + 1)), m <= n/. Remove all keys in a Set
-- from a Map.
--
--
-- m withoutKeys s = filterWithKey (k _ -> k `notMember' s) m
--
withoutKeys :: Ord k => Map k a -> Set k -> Map k a
-- | O(n). Partition the map according to a predicate. The first map
-- contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate. See also 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")])
--
partition :: (a -> Bool) -> Map k a -> (Map k a, Map k a)
-- | O(n). Partition the map according to a predicate. The first map
-- contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate. See also 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")])
--
partitionWithKey :: (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
-- | O(log n). Take while a predicate on the keys holds. The user is
-- responsible for ensuring that for all keys j and k
-- in the map, j < k ==> p j >= p k. See note at
-- spanAntitone.
--
--
-- takeWhileAntitone p = fromDistinctAscList . takeWhile (p . fst) . toList
-- takeWhileAntitone p = filterWithKey (k _ -> p k)
--
takeWhileAntitone :: (k -> Bool) -> Map k a -> Map k a
-- | O(log n). Drop while a predicate on the keys holds. The user is
-- responsible for ensuring that for all keys j and k
-- in the map, j < k ==> p j >= p k. See note at
-- spanAntitone.
--
--
-- dropWhileAntitone p = fromDistinctAscList . dropWhile (p . fst) . toList
-- dropWhileAntitone p = filterWithKey (k -> not (p k))
--
dropWhileAntitone :: (k -> Bool) -> Map k a -> Map k a
-- | O(log n). Divide a map at the point where a predicate on the
-- keys stops holding. The user is responsible for ensuring that for all
-- keys j and k in the map, j < k ==> p j
-- >= p k.
--
--
-- spanAntitone p xs = (takeWhileAntitone p xs, dropWhileAntitone p xs)
-- spanAntitone p xs = partition p xs
--
--
-- Note: if p is not actually antitone, then
-- spanAntitone will split the map at some unspecified
-- point where the predicate switches from holding to not holding (where
-- the predicate is seen to hold before the first key and to fail after
-- the last key).
spanAntitone :: (k -> Bool) -> Map k a -> (Map k a, Map k a)
-- | O(n). Map values and collect the Just results.
--
--
-- let f x = if x == "a" then Just "new a" else Nothing
-- mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"
--
mapMaybe :: (a -> Maybe b) -> Map k a -> Map k b
-- | O(n). Map keys/values and collect the Just results.
--
--
-- let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing
-- mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"
--
mapMaybeWithKey :: (k -> a -> Maybe b) -> Map k a -> Map k b
-- | O(n). Map values and separate the Left and Right
-- results.
--
--
-- 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")])
--
mapEither :: (a -> Either b c) -> Map k a -> (Map k b, Map k c)
-- | O(n). Map keys/values and separate the Left and
-- Right results.
--
--
-- 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")])
--
mapEitherWithKey :: (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
-- | O(log n). The expression (split k map) is a
-- pair (map1,map2) where the keys in map1 are smaller
-- than k and the keys in map2 larger than k.
-- Any key equal to k is found in neither map1 nor
-- 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)
--
split :: Ord k => k -> Map k a -> (Map k a, Map k a)
-- | O(log n). The expression (splitLookup k map)
-- splits a map just like split but also returns 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)
--
splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
-- | O(1). Decompose a map into pieces based on the structure of the
-- underlying tree. This function is useful for consuming a map in
-- parallel.
--
-- No guarantee is made as to the sizes of the pieces; an internal, but
-- deterministic process determines this. However, it is guaranteed that
-- the pieces returned will be in ascending order (all elements in the
-- first submap less than all elements in the second, and so on).
--
-- Examples:
--
--
-- splitRoot (fromList (zip [1..6] ['a'..])) ==
-- [fromList [(1,'a'),(2,'b'),(3,'c')],fromList [(4,'d')],fromList [(5,'e'),(6,'f')]]
--
--
--
-- splitRoot empty == []
--
--
-- Note that the current implementation does not return more than three
-- submaps, but you should not depend on this behaviour because it can
-- change in the future without notice.
splitRoot :: Map k b -> [Map k b]
-- | O(m*log(nm + 1)), m <= n/. This function is defined as
-- (isSubmapOf = isSubmapOfBy (==)).
isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
-- | O(m*log(nm + 1)), m <= n/. The expression
-- (isSubmapOfBy f t1 t2) returns True if all keys
-- in t1 are in tree t2, and when f returns
-- True when applied to their respective values. For example, the
-- following expressions are all 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)])
--
--
-- But the following are all 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)])
--
isSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
-- | O(m*log(nm + 1)), m <= n/. Is this a proper submap? (ie. a
-- submap but not equal). Defined as (isProperSubmapOf =
-- isProperSubmapOfBy (==)).
isProperSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
-- | O(m*log(nm + 1)), m <= n/. Is this a proper submap? (ie. a
-- submap but not equal). The expression (isProperSubmapOfBy f
-- m1 m2) returns True when m1 and m2 are
-- not equal, all keys in m1 are in m2, and when
-- f returns True when applied to their respective
-- values. For example, the following expressions are all True:
--
--
-- isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
-- isProperSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
--
--
-- But the following are all 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)])
--
isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
-- | O(log n). Lookup the index of a key, which is its
-- zero-based index in the sequence sorted by keys. The index is a number
-- from 0 up to, but not including, the size of the map.
--
--
-- 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
--
lookupIndex :: Ord k => k -> Map k a -> Maybe Int
-- | O(log n). Return the index of a key, which is its
-- zero-based index in the sequence sorted by keys. The index is a number
-- from 0 up to, but not including, the size of the map.
-- Calls error when the key is not a member of the map.
--
--
-- 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
--
findIndex :: Ord k => k -> Map k a -> Int
-- | O(log n). Retrieve an element by its index, i.e. by its
-- zero-based index in the sequence sorted by keys. If the index
-- is out of range (less than zero, greater or equal to size of
-- the map), error is called.
--
--
-- 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
--
elemAt :: Int -> Map k a -> (k, a)
-- | O(log n). Update the element at index, i.e. by its
-- zero-based index in the sequence sorted by keys. If the index
-- is out of range (less than zero, greater or equal to size of
-- the map), error is called.
--
--
-- 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
--
updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
-- | O(log n). Delete the element at index, i.e. by its
-- zero-based index in the sequence sorted by keys. If the index
-- is out of range (less than zero, greater or equal to size of
-- the map), error is called.
--
--
-- 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
--
deleteAt :: Int -> Map k a -> Map k a
-- | Take a given number of entries in key order, beginning with the
-- smallest keys.
--
--
-- take n = fromDistinctAscList . take n . toAscList
--
take :: Int -> Map k a -> Map k a
-- | Drop a given number of entries in key order, beginning with the
-- smallest keys.
--
--
-- drop n = fromDistinctAscList . drop n . toAscList
--
drop :: Int -> Map k a -> Map k a
-- | O(log n). Split a map at a particular index.
--
--
-- splitAt !n !xs = (take n xs, drop n xs)
--
splitAt :: Int -> Map k a -> (Map k a, Map k a)
-- | O(log n). The minimal key of the map. Calls error if the
-- map is empty.
--
--
-- findMin (fromList [(5,"a"), (3,"b")]) == (3,"b")
-- findMin empty Error: empty map has no minimal element
--
findMin :: Map k a -> (k, a)
-- | O(log n). The maximal key of the map. Calls error if the
-- map is empty.
--
--
-- findMax (fromList [(5,"a"), (3,"b")]) == (5,"a")
-- findMax empty Error: empty map has no maximal element
--
findMax :: Map k a -> (k, a)
-- | O(log n). Delete the minimal key. Returns an empty map if the
-- map is empty.
--
--
-- deleteMin (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(5,"a"), (7,"c")]
-- deleteMin empty == empty
--
deleteMin :: Map k a -> Map k a
-- | O(log n). Delete the maximal key. Returns an empty map if the
-- map is empty.
--
--
-- deleteMax (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(3,"b"), (5,"a")]
-- deleteMax empty == empty
--
deleteMax :: Map k a -> Map k a
-- | O(log n). Delete and find the minimal element.
--
--
-- 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
--
deleteFindMin :: Map k a -> ((k, a), Map k a)
-- | O(log n). Delete and find the maximal element.
--
--
-- 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
--
deleteFindMax :: Map k a -> ((k, a), Map k a)
-- | O(log n). Update the value at the minimal key.
--
--
-- 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"
--
updateMin :: (a -> Maybe a) -> Map k a -> Map k a
-- | O(log n). Update the value at the maximal key.
--
--
-- 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"
--
updateMax :: (a -> Maybe a) -> Map k a -> Map k a
-- | O(log n). Update the value at the minimal key.
--
--
-- 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"
--
updateMinWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a
-- | O(log n). Update the value at the maximal key.
--
--
-- 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"
--
updateMaxWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a
-- | O(log n). Retrieves the value associated with minimal key of
-- the map, and the map stripped of that element, or Nothing if
-- passed an empty map.
--
--
-- minView (fromList [(5,"a"), (3,"b")]) == Just ("b", singleton 5 "a")
-- minView empty == Nothing
--
minView :: Map k a -> Maybe (a, Map k a)
-- | O(log n). Retrieves the value associated with maximal key of
-- the map, and the map stripped of that element, or Nothing if
-- passed an empty map.
--
--
-- maxView (fromList [(5,"a"), (3,"b")]) == Just ("a", singleton 3 "b")
-- maxView empty == Nothing
--
maxView :: Map k a -> Maybe (a, Map k a)
-- | O(log n). Retrieves the minimal (key,value) pair of the map,
-- and the map stripped of that element, or Nothing if passed an
-- empty map.
--
--
-- minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
-- minViewWithKey empty == Nothing
--
minViewWithKey :: Map k a -> Maybe ((k, a), Map k a)
-- | O(log n). Retrieves the maximal (key,value) pair of the map,
-- and the map stripped of that element, or Nothing if passed an
-- empty map.
--
--
-- maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b")
-- maxViewWithKey empty == Nothing
--
maxViewWithKey :: Map k a -> Maybe ((k, a), Map k a)
-- | O(n). Show the tree that implements the map. The tree is shown
-- in a compressed, hanging format. See showTreeWith.
-- | Deprecated: This function is being removed from the public API.
showTree :: (Show k, Show a) => Map k a -> String
-- | O(n). The expression (showTreeWith showelem hang
-- wide map) shows the tree that implements the map. Elements are
-- shown using the showElem function. If hang is
-- True, a hanging tree is shown otherwise a rotated tree
-- is shown. If wide is True, an extra wide version is
-- shown.
--
--
-- 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,())
--
-- | Deprecated: This function is being removed from the public API.
showTreeWith :: (k -> a -> String) -> Bool -> Bool -> Map k a -> String
-- | O(n). Test if the internal map structure is valid.
--
--
-- valid (fromAscList [(3,"b"), (5,"a")]) == True
-- valid (fromAscList [(5,"a"), (3,"b")]) == False
--
valid :: Ord k => Map k a -> Bool
-- | This module defines an API for writing functions that merge two maps.
-- The key functions are merge and mergeA. Each of these
-- can be used with several different "merge tactics".
--
-- The merge and mergeA functions are shared by the lazy
-- and strict modules. Only the choice of merge tactics determines
-- strictness. If you use mapMissing from
-- Data.Map.Strict.Merge then the results will be forced before
-- they are inserted. If you use mapMissing from this module then
-- they will not.
--
-- Efficiency note
--
-- The Category, Applicative, and Monad instances
-- for WhenMissing tactics are included because they are valid.
-- However, they are inefficient in many cases and should usually be
-- avoided. The instances for WhenMatched tactics should not pose
-- any major efficiency problems.
module Data.Map.Lazy.Merge
-- | A tactic for dealing with keys present in one map but not the other in
-- merge.
--
-- A tactic of type SimpleWhenMissing k x z is an abstract
-- representation of a function of type k -> x -> Maybe z
-- .
type SimpleWhenMissing = WhenMissing Identity
-- | A tactic for dealing with keys present in both maps in merge.
--
-- A tactic of type SimpleWhenMatched k x y z is an abstract
-- representation of a function of type k -> x -> y ->
-- Maybe z .
type SimpleWhenMatched = WhenMatched Identity
-- | Merge two maps.
--
-- merge takes two WhenMissing tactics, a
-- WhenMatched tactic and two maps. It uses the tactics to merge
-- the maps. Its behavior is best understood via its fundamental tactics,
-- mapMaybeMissing and zipWithMaybeMatched.
--
-- Consider
--
--
-- merge (mapMaybeMissing g1)
-- (mapMaybeMissing g2)
-- (zipWithMaybeMatched f)
-- m1 m2
--
--
-- Take, for example,
--
--
-- m1 = [(0, a), (1, b), (3,c), (4, d)]
-- m2 = [(1, "one"), (2, "two"), (4, "three")]
--
--
-- merge will first 'align' these maps by key:
--
--
-- m1 = [(0, a), (1, b), (3,c), (4, d)]
-- m2 = [(1, "one"), (2, "two"), (4, "three")]
--
--
-- It will then pass the individual entries and pairs of entries to
-- g1, g2, or f as appropriate:
--
--
-- maybes = [g1 0 a, f 1 b "one", g2 2 "two", g1 3 c, f 4 d "three"]
--
--
-- This produces a Maybe for each key:
--
--
-- keys = 0 1 2 3 4
-- results = [Nothing, Just True, Just False, Nothing, Just True]
--
--
-- Finally, the Just results are collected into a map:
--
--
-- return value = [(1, True), (2, False), (4, True)]
--
--
-- The other tactics below are optimizations or simplifications of
-- mapMaybeMissing for special cases. Most importantly,
--
--
--
-- When merge is given three arguments, it is inlined at the call
-- site. To prevent excessive inlining, you should typically use
-- merge to define your custom combining functions.
--
-- Examples:
--
--
-- unionWithKey f = merge preserveMissing preserveMissing (zipWithMatched f)
--
--
--
-- intersectionWithKey f = merge dropMissing dropMissing (zipWithMatched f)
--
--
--
-- differenceWith f = merge diffPreserve diffDrop f
--
--
--
-- symmetricDifference = merge diffPreserve diffPreserve (\ _ _ _ -> Nothing)
--
--
--
-- mapEachPiece f g h = merge (diffMapWithKey f) (diffMapWithKey g)
--
merge :: Ord k => SimpleWhenMissing k a c -> SimpleWhenMissing k b c -> SimpleWhenMatched k a b c -> Map k a -> Map k b -> Map k c
-- | When a key is found in both maps, apply a function to the key and
-- values and maybe use the result in the merged map.
--
--
-- zipWithMaybeMatched :: (k -> x -> y -> Maybe z)
-- -> SimpleWhenMatched k x y z
--
zipWithMaybeMatched :: Applicative f => (k -> x -> y -> Maybe z) -> WhenMatched f k x y z
-- | When a key is found in both maps, apply a function to the key and
-- values and use the result in the merged map.
--
--
-- zipWithMatched :: (k -> x -> y -> z)
-- -> SimpleWhenMatched k x y z
--
zipWithMatched :: Applicative f => (k -> x -> y -> z) -> WhenMatched f k x y z
-- | Map over the entries whose keys are missing from the other map,
-- optionally removing some. This is the most powerful
-- SimpleWhenMissing tactic, but others are usually more
-- efficient.
--
--
-- mapMaybeMissing :: (k -> x -> Maybe y) -> SimpleWhenMissing k x y
--
--
--
-- mapMaybeMissing f = traverseMaybeMissing (\k x -> pure (f k x))
--
--
-- but mapMaybeMissing uses fewer unnecessary Applicative
-- operations.
mapMaybeMissing :: Applicative f => (k -> x -> Maybe y) -> WhenMissing f k x y
-- | Drop all the entries whose keys are missing from the other map.
--
--
-- dropMissing :: SimpleWhenMissing k x y
--
--
--
-- dropMissing = mapMaybeMissing (\_ _ -> Nothing)
--
--
-- but dropMissing is much faster.
dropMissing :: Applicative f => WhenMissing f k x y
-- | Preserve, unchanged, the entries whose keys are missing from the other
-- map.
--
--
-- preserveMissing :: SimpleWhenMissing k x x
--
--
--
-- preserveMissing = Lazy.Merge.mapMaybeMissing (\_ x -> Just x)
--
--
-- but preserveMissing is much faster.
preserveMissing :: Applicative f => WhenMissing f k x x
-- | Map over the entries whose keys are missing from the other map.
--
--
-- mapMissing :: (k -> x -> y) -> SimpleWhenMissing k x y
--
--
--
-- mapMissing f = mapMaybeMissing (\k x -> Just $ f k x)
--
--
-- but mapMissing is somewhat faster.
mapMissing :: Applicative f => (k -> x -> y) -> WhenMissing f k x y
-- | Filter the entries whose keys are missing from the other map.
--
--
-- filterMissing :: (k -> x -> Bool) -> SimpleWhenMissing k x x
--
--
--
-- filterMissing f = Lazy.Merge.mapMaybeMissing $ \k x -> guard (f k x) *> Just x
--
--
-- but this should be a little faster.
filterMissing :: Applicative f => (k -> x -> Bool) -> WhenMissing f k x x
-- | A tactic for dealing with keys present in one map but not the other in
-- merge or mergeA.
--
-- A tactic of type WhenMissing f k x z is an abstract
-- representation of a function of type k -> x -> f (Maybe z)
-- .
data WhenMissing f k x y
-- | A tactic for dealing with keys present in both maps in merge or
-- mergeA.
--
-- A tactic of type WhenMatched f k x y z is an abstract
-- representation of a function of type k -> x -> y -> f
-- (Maybe z) .
data WhenMatched f k x y z
-- | An applicative version of merge.
--
-- mergeA takes two WhenMissing tactics, a
-- WhenMatched tactic and two maps. It uses the tactics to merge
-- the maps. Its behavior is best understood via its fundamental tactics,
-- traverseMaybeMissing and zipWithMaybeAMatched.
--
-- Consider
--
--
-- mergeA (traverseMaybeMissing g1)
-- (traverseMaybeMissing g2)
-- (zipWithMaybeAMatched f)
-- m1 m2
--
--
-- Take, for example,
--
--
-- m1 = [(0, a), (1, b), (3,c), (4, d)]
-- m2 = [(1, "one"), (2, "two"), (4, "three")]
--
--
-- mergeA will first 'align' these maps by key:
--
--
-- m1 = [(0, a), (1, b), (3,c), (4, d)]
-- m2 = [(1, "one"), (2, "two"), (4, "three")]
--
--
-- It will then pass the individual entries and pairs of entries to
-- g1, g2, or f as appropriate:
--
--
-- actions = [g1 0 a, f 1 b "one", g2 2 "two", g1 3 c, f 4 d "three"]
--
--
-- Next, it will perform the actions in the actions list in
-- order from left to right.
--
--
-- keys = 0 1 2 3 4
-- results = [Nothing, Just True, Just False, Nothing, Just True]
--
--
-- Finally, the Just results are collected into a map:
--
--
-- return value = [(1, True), (2, False), (4, True)]
--
--
-- The other tactics below are optimizations or simplifications of
-- traverseMaybeMissing for special cases. Most importantly,
--
--
--
-- When mergeA is given three arguments, it is inlined at the call
-- site. To prevent excessive inlining, you should generally only use
-- mergeA to define custom combining functions.
mergeA :: (Applicative f, Ord k) => WhenMissing f k a c -> WhenMissing f k b c -> WhenMatched f k a b c -> Map k a -> Map k b -> f (Map k c)
-- | When a key is found in both maps, apply a function to the key and
-- values, perform the resulting action, and maybe use the result in the
-- merged map.
--
-- This is the fundamental WhenMatched tactic.
zipWithMaybeAMatched :: (k -> x -> y -> f (Maybe z)) -> WhenMatched f k x y z
-- | When a key is found in both maps, apply a function to the key and
-- values to produce an action and use its result in the merged map.
zipWithAMatched :: Applicative f => (k -> x -> y -> f z) -> WhenMatched f k x y z
-- | Traverse over the entries whose keys are missing from the other map,
-- optionally producing values to put in the result. This is the most
-- powerful WhenMissing tactic, but others are usually more
-- efficient.
traverseMaybeMissing :: Applicative f => (k -> x -> f (Maybe y)) -> WhenMissing f k x y
-- | Traverse over the entries whose keys are missing from the other map.
traverseMissing :: Applicative f => (k -> x -> f y) -> WhenMissing f k x y
-- | Filter the entries whose keys are missing from the other map using
-- some Applicative action.
--
--
-- filterAMissing f = Lazy.Merge.traverseMaybeMissing $
-- k x -> (b -> guard b *> Just x) $ f k x
--
--
-- but this should be a little faster.
filterAMissing :: Applicative f => (k -> x -> f Bool) -> WhenMissing f k x x
-- | Map covariantly over a WhenMissing f k x.
mapWhenMissing :: (Applicative f, Monad f) => (a -> b) -> WhenMissing f k x a -> WhenMissing f k x b
-- | Map covariantly over a WhenMatched f k x y.
mapWhenMatched :: Functor f => (a -> b) -> WhenMatched f k x y a -> WhenMatched f k x y b
-- | Map contravariantly over a WhenMissing f k _ x.
lmapWhenMissing :: (b -> a) -> WhenMissing f k a x -> WhenMissing f k b x
-- | Map contravariantly over a WhenMatched f k _ y z.
contramapFirstWhenMatched :: (b -> a) -> WhenMatched f k a y z -> WhenMatched f k b y z
-- | Map contravariantly over a WhenMatched f k x _ z.
contramapSecondWhenMatched :: (b -> a) -> WhenMatched f k x a z -> WhenMatched f k x b z
-- | Along with zipWithMaybeAMatched, witnesses the isomorphism between
-- WhenMatched f k x y z and k -> x -> y -> f
-- (Maybe z).
runWhenMatched :: WhenMatched f k x y z -> k -> x -> y -> f (Maybe z)
-- | Along with traverseMaybeMissing, witnesses the isomorphism between
-- WhenMissing f k x y and k -> x -> f (Maybe y).
runWhenMissing :: WhenMissing f k x y -> k -> x -> f (Maybe y)
-- | An efficient implementation of ordered maps from keys to values
-- (dictionaries).
--
-- API of this module is strict in both the keys and the values. If you
-- need value-lazy maps, use Data.Map.Lazy instead. The Map
-- type is shared between the lazy and strict modules, meaning that the
-- same Map value can be passed to functions in both modules
-- (although that is rarely needed).
--
-- These modules are intended to be imported qualified, to avoid name
-- clashes with Prelude functions, e.g.
--
--
-- import qualified Data.Map.Strict as Map
--
--
-- The implementation of Map is based on size balanced
-- binary trees (or trees of bounded balance) as described by:
--
--
-- - Stephen Adams, "Efficient sets: a balancing act", Journal
-- of Functional Programming 3(4):553-562, October 1993,
-- http://www.swiss.ai.mit.edu/~adams/BB/.
-- - J. Nievergelt and E.M. Reingold, "Binary search trees of
-- bounded balance", SIAM journal of computing 2(1), March 1973.
--
--
-- Bounds for union, intersection, and difference
-- are as given by
--
--
--
-- Note that the implementation is left-biased -- the elements of
-- a first argument are always preferred to the second, for example in
-- union or insert.
--
-- Warning: The size of the map must not exceed
-- maxBound::Int. Violation of this condition is not detected
-- and if the size limit is exceeded, its behaviour is undefined.
--
-- Operation comments contain the operation time complexity in the Big-O
-- notation (http://en.wikipedia.org/wiki/Big_O_notation).
--
-- Be aware that the Functor, Traversable and
-- Data instances are the same as for the Data.Map.Lazy
-- module, so if they are used on strict maps, the resulting maps will be
-- lazy.
module Data.Map.Strict
-- | A Map from keys k to values a.
data Map k a
-- | O(log n). Find the value at a key. Calls error when the
-- element can not be found.
--
--
-- fromList [(5,'a'), (3,'b')] ! 1 Error: element not in the map
-- fromList [(5,'a'), (3,'b')] ! 5 == 'a'
--
(!) :: Ord k => Map k a -> k -> a
infixl 9 !
-- | Same as difference.
(\\) :: Ord k => Map k a -> Map k b -> Map k a
infixl 9 \\
-- | O(1). Is the map empty?
--
--
-- Data.Map.null (empty) == True
-- Data.Map.null (singleton 1 'a') == False
--
null :: Map k a -> Bool
-- | O(1). The number of elements in the map.
--
--
-- size empty == 0
-- size (singleton 1 'a') == 1
-- size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3
--
size :: Map k a -> Int
-- | O(log n). Is the key a member of the map? See also
-- notMember.
--
--
-- member 5 (fromList [(5,'a'), (3,'b')]) == True
-- member 1 (fromList [(5,'a'), (3,'b')]) == False
--
member :: Ord k => k -> Map k a -> Bool
-- | O(log n). Is the key not a member of the map? See also
-- member.
--
--
-- notMember 5 (fromList [(5,'a'), (3,'b')]) == False
-- notMember 1 (fromList [(5,'a'), (3,'b')]) == True
--
notMember :: Ord k => k -> Map k a -> Bool
-- | O(log n). Lookup the value at a key in the map.
--
-- The function will return the corresponding value as (Just
-- value), or Nothing if the key isn't in the map.
--
-- An example of using 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"))
--
--
-- The output of this program:
--
--
-- John's currency: Just "Euro"
-- Pete's currency: Nothing
--
lookup :: Ord k => k -> Map k a -> Maybe a
-- | O(log n). The expression (findWithDefault def k
-- map) returns the value at key k or returns default value
-- def when the key is not in the map.
--
--
-- findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
-- findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
--
findWithDefault :: Ord k => a -> k -> Map k a -> a
-- | O(log n). Find largest key smaller than the given one and
-- return the corresponding (key, value) pair.
--
--
-- lookupLT 3 (fromList [(3,'a'), (5,'b')]) == Nothing
-- lookupLT 4 (fromList [(3,'a'), (5,'b')]) == Just (3, 'a')
--
lookupLT :: Ord k => k -> Map k v -> Maybe (k, v)
-- | O(log n). Find smallest key greater than the given one and
-- return the corresponding (key, value) pair.
--
--
-- lookupGT 4 (fromList [(3,'a'), (5,'b')]) == Just (5, 'b')
-- lookupGT 5 (fromList [(3,'a'), (5,'b')]) == Nothing
--
lookupGT :: Ord k => k -> Map k v -> Maybe (k, v)
-- | O(log n). Find largest key smaller or equal to the given one
-- and return the corresponding (key, value) pair.
--
--
-- 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')
--
lookupLE :: Ord k => k -> Map k v -> Maybe (k, v)
-- | O(log n). Find smallest key greater or equal to the given one
-- and return the corresponding (key, value) pair.
--
--
-- 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
--
lookupGE :: Ord k => k -> Map k v -> Maybe (k, v)
-- | O(1). The empty map.
--
--
-- empty == fromList []
-- size empty == 0
--
empty :: Map k a
-- | O(1). A map with a single element.
--
--
-- singleton 1 'a' == fromList [(1, 'a')]
-- size (singleton 1 'a') == 1
--
singleton :: k -> a -> Map k a
-- | O(log n). Insert a new key and value in the map. If the key is
-- already present in the map, the associated value is replaced with the
-- supplied value. insert is equivalent to 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'
--
insert :: Ord k => k -> a -> Map k a -> Map k a
-- | O(log n). Insert with a function, combining new value and old
-- value. insertWith f key value mp will insert the pair
-- (key, value) into mp if key does not exist in the map. If the
-- key does exist, the function will insert the pair (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"
--
insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
-- | O(log n). Insert with a function, combining key, new value and
-- old value. insertWithKey f key value mp will insert
-- the pair (key, value) into mp if key does not exist in the
-- map. If the key does exist, the function will insert the pair
-- (key,f key new_value old_value). Note that the key passed to
-- f is the same key passed to 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"
--
insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
-- | O(log n). Combines insert operation with old value retrieval.
-- The expression (insertLookupWithKey f k x map) is a
-- pair where the first element is equal to (lookup k
-- map) and the second element equal to (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")
--
--
-- This is how to define insertLookup using
-- 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")])
--
insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
-- | O(log n). Delete a key and its value from the map. When the key
-- is not a member of the map, the original map is returned.
--
--
-- 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
--
delete :: Ord k => k -> Map k a -> Map k a
-- | O(log n). Update a value at a specific key with the result of
-- the provided function. When the key is not a member of the map, the
-- original map is returned.
--
--
-- 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
--
adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k a
-- | O(log n). Adjust a value at a specific key. When the key is not
-- a member of the map, the original map is returned.
--
--
-- 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
--
adjustWithKey :: Ord k => (k -> a -> a) -> k -> Map k a -> Map k a
-- | O(log n). The expression (update f k map)
-- updates the value x at k (if it is in the map). If
-- (f x) is Nothing, the element is deleted. If it is
-- (Just y), the key k is bound to the new value
-- 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"
--
update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
-- | O(log n). The expression (updateWithKey f k
-- map) updates the value x at k (if it is in the
-- map). If (f k x) is Nothing, the element is deleted.
-- If it is (Just y), the key k is bound to the
-- new value 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"
--
updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
-- | O(log n). Lookup and update. See also updateWithKey. The
-- function returns changed value, if it is updated. Returns the original
-- key value if the map entry is deleted.
--
--
-- 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")
--
updateLookupWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
-- | O(log n). The expression (alter f k map) alters
-- the value x at k, or absence thereof. alter
-- can be used to insert, delete, or update a value in a Map. In
-- short : 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")]
--
alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
-- | O(log n). The expression (alterF f k map)
-- alters the value x at k, or absence thereof.
-- alterF can be used to inspect, insert, delete, or update a
-- value in a Map. In short: lookup k <$>
-- alterF f k m = f (lookup k m).
--
-- Example:
--
--
-- interactiveAlter :: Int -> Map Int String -> IO (Map Int String)
-- interactiveAlter k m = alterF f k m where
-- f Nothing -> do
-- putStrLn $ show k ++
-- " was not found in the map. Would you like to add it?"
-- getUserResponse1 :: IO (Maybe String)
-- f (Just old) -> do
-- putStrLn "The key is currently bound to " ++ show old ++
-- ". Would you like to change or delete it?"
-- getUserresponse2 :: IO (Maybe String)
--
--
-- alterF is the most general operation for working with an
-- individual key that may or may not be in a given map. When used with
-- trivial functors like Identity and Const, it is often
-- slightly slower than more specialized combinators like lookup
-- and insert. However, when the functor is non-trivial and key
-- comparison is not particularly cheap, it is the fastest way.
--
-- Note on rewrite rules:
--
-- This module includes GHC rewrite rules to optimize alterF for
-- the Const and Identity functors. In general, these rules
-- improve performance. The sole exception is that when using
-- Identity, deleting a key that is already absent takes longer
-- than it would without the rules. If you expect this to occur a very
-- large fraction of the time, you might consider using a private copy of
-- the Identity type.
--
-- Note: alterF is a flipped version of the at combinator
-- from At.
alterF :: (Functor f, Ord k) => (Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
-- | O(m*log(n/m + 1)), m <= n. The expression (union
-- t1 t2) takes the left-biased union of t1 and
-- t2. It prefers t1 when duplicate keys are
-- encountered, i.e. (union == unionWith
-- const).
--
--
-- union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
--
union :: Ord k => Map k a -> Map k a -> Map k a
-- | O(m*log(n/m + 1)), m <= n. Union with a combining function.
--
--
-- unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
--
unionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
-- | O(m*log(n/m + 1)), m <= n. Union with a combining function.
--
--
-- 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")]
--
unionWithKey :: Ord k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
-- | The union of a list of maps: (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")]
--
unions :: Ord k => [Map k a] -> Map k a
-- | The union of a list of maps, with a combining operation:
-- (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")]
--
unionsWith :: Ord k => (a -> a -> a) -> [Map k a] -> Map k a
-- | O(m*log(n/m + 1)), m <= n. Difference of two maps. Return
-- elements of the first map not existing in the second map.
--
--
-- difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"
--
difference :: Ord k => Map k a -> Map k b -> Map k a
-- | O(n+m). Difference with a combining function. When two equal
-- keys are encountered, the combining function is applied to the values
-- of these keys. If it returns Nothing, the element is discarded
-- (proper set difference). If it returns (Just y), the
-- element is updated with a new value y.
--
--
-- 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"
--
differenceWith :: Ord k => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
-- | O(n+m). Difference with a combining function. When two equal
-- keys are encountered, the combining function is applied to the key and
-- both values. If it returns Nothing, the element is discarded
-- (proper set difference). If it returns (Just y), the
-- element is updated with a new value 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"
--
differenceWithKey :: Ord k => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
-- | O(m*log(n/m + 1)), m <= n. Intersection of two maps. Return
-- data in the first map for the keys existing in both maps.
-- (intersection m1 m2 == intersectionWith const
-- m1 m2).
--
--
-- intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a"
--
intersection :: Ord k => Map k a -> Map k b -> Map k a
-- | O(m*log(n/m + 1)), m <= n. Intersection with a combining
-- function.
--
--
-- intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA"
--
intersectionWith :: Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k c
-- | O(m*log(n/m + 1)), m <= n. Intersection with a combining
-- function.
--
--
-- 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"
--
intersectionWithKey :: Ord k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
-- | O(n+m). An unsafe universal combining function.
--
-- WARNING: This function can produce corrupt maps and its results may
-- depend on the internal structures of its inputs. Users should prefer
-- merge or mergeA.
--
-- When mergeWithKey is given three arguments, it is inlined to
-- the call site. You should therefore use mergeWithKey only to
-- define custom combining functions. For example, you could define
-- unionWithKey, differenceWithKey and
-- intersectionWithKey as
--
--
-- 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
--
--
-- When calling mergeWithKey combine only1 only2, a
-- function combining two Maps is created, such that
--
--
-- - if a key is present in both maps, it is passed with both
-- corresponding values to the combine function. Depending on
-- the result, the key is either present in the result with specified
-- value, or is left out;
-- - a nonempty subtree present only in the first map is passed to
-- only1 and the output is added to the result;
-- - a nonempty subtree present only in the second map is passed to
-- only2 and the output is added to the result.
--
--
-- The only1 and only2 methods must return a map
-- with a subset (possibly empty) of the keys of the given map. The
-- values can be modified arbitrarily. Most common variants of
-- only1 and only2 are id and const
-- empty, but for example map f or
-- filterWithKey f could be used for any f.
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
-- | O(n). Map a function over all values in the map.
--
--
-- map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
--
map :: (a -> b) -> Map k a -> Map k b
-- | O(n). Map a function over all values in the map.
--
--
-- let f key x = (show key) ++ ":" ++ x
-- mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]
--
mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
-- | O(n). traverseWithKey f m == fromList
-- $ traverse ((k, v) -> (v' -> v' seq (k,v'))
-- $ f k v) (toList m) That is, it behaves much like a
-- regular traverse except that the traversing function also has
-- access to the key associated with a value and the values are forced
-- before they are installed in the result map.
--
--
-- 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
--
traverseWithKey :: Applicative t => (k -> a -> t b) -> Map k a -> t (Map k b)
-- | O(n). Traverse keys/values and collect the Just results.
traverseMaybeWithKey :: Applicative f => (k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
-- | O(n). The function mapAccum threads an accumulating
-- argument through the map in ascending order of keys.
--
--
-- let f a b = (a ++ b, b ++ "X")
-- mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
--
mapAccum :: (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
-- | 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")])
--
mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
-- | O(n). The function mapAccumR threads an accumulating
-- argument through the map in descending order of keys.
mapAccumRWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
-- | O(n*log n). mapKeys f s is the map obtained by
-- applying f to each key of s.
--
-- The size of the result may be smaller if f maps two or more
-- distinct keys to the same new key. In this case the value at the
-- greatest of the original keys is retained.
--
--
-- 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"
--
mapKeys :: Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
-- | O(n*log n). mapKeysWith c f s is the map
-- obtained by applying f to each key of s.
--
-- The size of the result may be smaller if f maps two or more
-- distinct keys to the same new key. In this case the associated values
-- will be combined using 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"
--
mapKeysWith :: Ord k2 => (a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
-- | O(n). mapKeysMonotonic f s == mapKeys f
-- s, but works only when f is strictly monotonic. That is,
-- for any values x and y, if x <
-- y then f x < f y. The precondition is
-- not checked. Semi-formally, we have:
--
--
-- and [x < y ==> f x < f y | x <- ls, y <- ls]
-- ==> mapKeysMonotonic f s == mapKeys f s
-- where ls = keys s
--
--
-- This means that f maps distinct original keys to distinct
-- resulting keys. This function has better performance than
-- 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
--
mapKeysMonotonic :: (k1 -> k2) -> Map k1 a -> Map k2 a
-- | O(n). Fold the values in the map using the given
-- right-associative binary operator, such that foldr f z ==
-- foldr f z . elems.
--
-- For example,
--
--
-- elems map = foldr (:) [] map
--
--
--
-- let f a len = len + (length a)
-- foldr f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
--
foldr :: (a -> b -> b) -> b -> Map k a -> b
-- | O(n). Fold the values in the map using the given
-- left-associative binary operator, such that foldl f z ==
-- foldl f z . elems.
--
-- For example,
--
--
-- elems = reverse . foldl (flip (:)) []
--
--
--
-- let f len a = len + (length a)
-- foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
--
foldl :: (a -> b -> a) -> a -> Map k b -> a
-- | O(n). Fold the keys and values in the map using the given
-- right-associative binary operator, such that foldrWithKey f
-- z == foldr (uncurry f) z . toAscList.
--
-- For example,
--
--
-- 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)"
--
foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
-- | O(n). Fold the keys and values in the map using the given
-- left-associative binary operator, such that foldlWithKey f
-- z == foldl (\z' (kx, x) -> f z' kx x) z .
-- toAscList.
--
-- For example,
--
--
-- 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)"
--
foldlWithKey :: (a -> k -> b -> a) -> a -> Map k b -> a
-- | O(n). Fold the keys and values in the map using the given
-- monoid, such that
--
--
-- foldMapWithKey f = fold . mapWithKey f
--
--
-- This can be an asymptotically faster than foldrWithKey or
-- foldlWithKey for some monoids.
foldMapWithKey :: Monoid m => (k -> a -> m) -> Map k a -> m
-- | O(n). A strict version of foldr. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> Map k a -> b
-- | O(n). A strict version of foldl. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldl' :: (a -> b -> a) -> a -> Map k b -> a
-- | O(n). A strict version of foldrWithKey. Each application
-- of the operator is evaluated before using the result in the next
-- application. This function is strict in the starting value.
foldrWithKey' :: (k -> a -> b -> b) -> b -> Map k a -> b
-- | O(n). A strict version of foldlWithKey. Each application
-- of the operator is evaluated before using the result in the next
-- application. This function is strict in the starting value.
foldlWithKey' :: (a -> k -> b -> a) -> a -> Map k b -> a
-- | O(n). Return all elements of the map in the ascending order of
-- their keys. Subject to list fusion.
--
--
-- elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]
-- elems empty == []
--
elems :: Map k a -> [a]
-- | O(n). Return all keys of the map in ascending order. Subject to
-- list fusion.
--
--
-- keys (fromList [(5,"a"), (3,"b")]) == [3,5]
-- keys empty == []
--
keys :: Map k a -> [k]
-- | O(n). An alias for toAscList. Return all key/value pairs
-- in the map in ascending key order. Subject to list fusion.
--
--
-- assocs (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
-- assocs empty == []
--
assocs :: Map k a -> [(k, a)]
-- | O(n). The set of all keys of the map.
--
--
-- keysSet (fromList [(5,"a"), (3,"b")]) == Data.Set.fromList [3,5]
-- keysSet empty == Data.Set.empty
--
keysSet :: Map k a -> Set k
-- | O(n). Build a map from a set of keys and a function which for
-- each key computes its value.
--
--
-- fromSet (\k -> replicate k 'a') (Data.Set.fromList [3, 5]) == fromList [(5,"aaaaa"), (3,"aaa")]
-- fromSet undefined Data.Set.empty == empty
--
fromSet :: (k -> a) -> Set k -> Map k a
-- | O(n). Convert the map to a list of key/value pairs. Subject to
-- list fusion.
--
--
-- toList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
-- toList empty == []
--
toList :: Map k a -> [(k, a)]
-- | O(n*log n). Build a map from a list of key/value pairs. See
-- also fromAscList. If the list contains more than one value for
-- the same key, the last value for the key is retained.
--
-- If the keys of the list are ordered, linear-time implementation is
-- used, with the performance equal to 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")]
--
fromList :: Ord k => [(k, a)] -> Map k a
-- | O(n*log n). Build a map from a list of key/value pairs with a
-- combining function. See also fromAscListWith.
--
--
-- fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
-- fromListWith (++) [] == empty
--
fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n*log n). Build a map from a list of key/value pairs with a
-- combining function. See also 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
--
fromListWithKey :: Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n). Convert the map to a list of key/value pairs where the
-- keys are in ascending order. Subject to list fusion.
--
--
-- toAscList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
--
toAscList :: Map k a -> [(k, a)]
-- | O(n). Convert the map to a list of key/value pairs where the
-- keys are in descending order. Subject to list fusion.
--
--
-- toDescList (fromList [(5,"a"), (3,"b")]) == [(5,"a"), (3,"b")]
--
toDescList :: Map k a -> [(k, a)]
-- | O(n). Build a map from an ascending list in linear time. The
-- precondition (input list is ascending) is not checked.
--
--
-- 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
--
fromAscList :: Eq k => [(k, a)] -> Map k a
-- | O(n). Build a map from an ascending list in linear time with a
-- combining function for equal keys. The precondition (input list is
-- ascending) is not checked.
--
--
-- 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
--
fromAscListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n). Build a map from an ascending list in linear time with a
-- combining function for equal keys. The precondition (input list is
-- ascending) is not checked.
--
--
-- 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
--
fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n). Build a map from an ascending list of distinct elements
-- in linear time. The precondition is not checked.
--
--
-- 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
--
fromDistinctAscList :: [(k, a)] -> Map k a
-- | O(n). Build a map from a descending list in linear time. The
-- precondition (input list is descending) is not checked.
--
--
-- fromDescList [(5,"a"), (3,"b")] == fromList [(3, "b"), (5, "a")]
-- fromDescList [(5,"a"), (5,"b"), (3,"a")] == fromList [(3, "b"), (5, "b")]
-- valid (fromDescList [(5,"a"), (5,"b"), (3,"b")]) == True
-- valid (fromDescList [(5,"a"), (3,"b"), (5,"b")]) == False
--
fromDescList :: Eq k => [(k, a)] -> Map k a
-- | O(n). Build a map from a descending list in linear time with a
-- combining function for equal keys. The precondition (input list is
-- descending) is not checked.
--
--
-- fromDescListWith (++) [(5,"a"), (5,"b"), (3,"b")] == fromList [(3, "b"), (5, "ba")]
-- valid (fromDescListWith (++) [(5,"a"), (5,"b"), (3,"b")]) == True
-- valid (fromDescListWith (++) [(5,"a"), (3,"b"), (5,"b")]) == False
--
fromDescListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n). Build a map from a descending list in linear time with a
-- combining function for equal keys. The precondition (input list is
-- descending) is not checked.
--
--
-- let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2
-- fromDescListWithKey f [(5,"a"), (5,"b"), (5,"b"), (3,"b")] == fromList [(3, "b"), (5, "5:b5:ba")]
-- valid (fromDescListWithKey f [(5,"a"), (5,"b"), (5,"b"), (3,"b")]) == True
-- valid (fromDescListWithKey f [(5,"a"), (3,"b"), (5,"b"), (5,"b")]) == False
--
fromDescListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n). Build a map from a descending list of distinct elements
-- in linear time. The precondition is not checked.
--
--
-- fromDistinctDescList [(5,"a"), (3,"b")] == fromList [(3, "b"), (5, "a")]
-- valid (fromDistinctDescList [(5,"a"), (3,"b")]) == True
-- valid (fromDistinctDescList [(5,"a"), (3,"b"), (3,"a")]) == False
--
fromDistinctDescList :: [(k, a)] -> Map k a
-- | O(n). Filter all values that satisfy the predicate.
--
--
-- 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
--
filter :: (a -> Bool) -> Map k a -> Map k a
-- | O(n). Filter all keys/values that satisfy the predicate.
--
--
-- filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--
filterWithKey :: (k -> a -> Bool) -> Map k a -> Map k a
-- | O(m*log(nm + 1)), m <= n/. Restrict a Map to only
-- those keys found in a Set.
--
--
-- m restrictKeys s = filterWithKey (k _ -> k `member' s) m
--
restrictKeys :: Ord k => Map k a -> Set k -> Map k a
-- | O(m*log(nm + 1)), m <= n/. Remove all keys in a Set
-- from a Map.
--
--
-- m withoutKeys s = filterWithKey (k _ -> k `notMember' s) m
--
withoutKeys :: Ord k => Map k a -> Set k -> Map k a
-- | O(n). Partition the map according to a predicate. The first map
-- contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate. See also 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")])
--
partition :: (a -> Bool) -> Map k a -> (Map k a, Map k a)
-- | O(n). Partition the map according to a predicate. The first map
-- contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate. See also 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")])
--
partitionWithKey :: (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
-- | O(log n). Take while a predicate on the keys holds. The user is
-- responsible for ensuring that for all keys j and k
-- in the map, j < k ==> p j >= p k. See note at
-- spanAntitone.
--
--
-- takeWhileAntitone p = fromDistinctAscList . takeWhile (p . fst) . toList
-- takeWhileAntitone p = filterWithKey (k _ -> p k)
--
takeWhileAntitone :: (k -> Bool) -> Map k a -> Map k a
-- | O(log n). Drop while a predicate on the keys holds. The user is
-- responsible for ensuring that for all keys j and k
-- in the map, j < k ==> p j >= p k. See note at
-- spanAntitone.
--
--
-- dropWhileAntitone p = fromDistinctAscList . dropWhile (p . fst) . toList
-- dropWhileAntitone p = filterWithKey (k -> not (p k))
--
dropWhileAntitone :: (k -> Bool) -> Map k a -> Map k a
-- | O(log n). Divide a map at the point where a predicate on the
-- keys stops holding. The user is responsible for ensuring that for all
-- keys j and k in the map, j < k ==> p j
-- >= p k.
--
--
-- spanAntitone p xs = (takeWhileAntitone p xs, dropWhileAntitone p xs)
-- spanAntitone p xs = partition p xs
--
--
-- Note: if p is not actually antitone, then
-- spanAntitone will split the map at some unspecified
-- point where the predicate switches from holding to not holding (where
-- the predicate is seen to hold before the first key and to fail after
-- the last key).
spanAntitone :: (k -> Bool) -> Map k a -> (Map k a, Map k a)
-- | O(n). Map values and collect the Just results.
--
--
-- let f x = if x == "a" then Just "new a" else Nothing
-- mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"
--
mapMaybe :: (a -> Maybe b) -> Map k a -> Map k b
-- | O(n). Map keys/values and collect the Just results.
--
--
-- let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing
-- mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"
--
mapMaybeWithKey :: (k -> a -> Maybe b) -> Map k a -> Map k b
-- | O(n). Map values and separate the Left and Right
-- results.
--
--
-- 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")])
--
mapEither :: (a -> Either b c) -> Map k a -> (Map k b, Map k c)
-- | O(n). Map keys/values and separate the Left and
-- Right results.
--
--
-- 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")])
--
mapEitherWithKey :: (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
-- | O(log n). The expression (split k map) is a
-- pair (map1,map2) where the keys in map1 are smaller
-- than k and the keys in map2 larger than k.
-- Any key equal to k is found in neither map1 nor
-- 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)
--
split :: Ord k => k -> Map k a -> (Map k a, Map k a)
-- | O(log n). The expression (splitLookup k map)
-- splits a map just like split but also returns 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)
--
splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
-- | O(1). Decompose a map into pieces based on the structure of the
-- underlying tree. This function is useful for consuming a map in
-- parallel.
--
-- No guarantee is made as to the sizes of the pieces; an internal, but
-- deterministic process determines this. However, it is guaranteed that
-- the pieces returned will be in ascending order (all elements in the
-- first submap less than all elements in the second, and so on).
--
-- Examples:
--
--
-- splitRoot (fromList (zip [1..6] ['a'..])) ==
-- [fromList [(1,'a'),(2,'b'),(3,'c')],fromList [(4,'d')],fromList [(5,'e'),(6,'f')]]
--
--
--
-- splitRoot empty == []
--
--
-- Note that the current implementation does not return more than three
-- submaps, but you should not depend on this behaviour because it can
-- change in the future without notice.
splitRoot :: Map k b -> [Map k b]
-- | O(m*log(nm + 1)), m <= n/. This function is defined as
-- (isSubmapOf = isSubmapOfBy (==)).
isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
-- | O(m*log(nm + 1)), m <= n/. The expression
-- (isSubmapOfBy f t1 t2) returns True if all keys
-- in t1 are in tree t2, and when f returns
-- True when applied to their respective values. For example, the
-- following expressions are all 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)])
--
--
-- But the following are all 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)])
--
isSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
-- | O(m*log(nm + 1)), m <= n/. Is this a proper submap? (ie. a
-- submap but not equal). Defined as (isProperSubmapOf =
-- isProperSubmapOfBy (==)).
isProperSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
-- | O(m*log(nm + 1)), m <= n/. Is this a proper submap? (ie. a
-- submap but not equal). The expression (isProperSubmapOfBy f
-- m1 m2) returns True when m1 and m2 are
-- not equal, all keys in m1 are in m2, and when
-- f returns True when applied to their respective
-- values. For example, the following expressions are all True:
--
--
-- isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
-- isProperSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
--
--
-- But the following are all 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)])
--
isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
-- | O(log n). Lookup the index of a key, which is its
-- zero-based index in the sequence sorted by keys. The index is a number
-- from 0 up to, but not including, the size of the map.
--
--
-- 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
--
lookupIndex :: Ord k => k -> Map k a -> Maybe Int
-- | O(log n). Return the index of a key, which is its
-- zero-based index in the sequence sorted by keys. The index is a number
-- from 0 up to, but not including, the size of the map.
-- Calls error when the key is not a member of the map.
--
--
-- 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
--
findIndex :: Ord k => k -> Map k a -> Int
-- | O(log n). Retrieve an element by its index, i.e. by its
-- zero-based index in the sequence sorted by keys. If the index
-- is out of range (less than zero, greater or equal to size of
-- the map), error is called.
--
--
-- 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
--
elemAt :: Int -> Map k a -> (k, a)
-- | O(log n). Update the element at index. Calls
-- error when an invalid index is used.
--
--
-- 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
--
updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
-- | O(log n). Delete the element at index, i.e. by its
-- zero-based index in the sequence sorted by keys. If the index
-- is out of range (less than zero, greater or equal to size of
-- the map), error is called.
--
--
-- 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
--
deleteAt :: Int -> Map k a -> Map k a
-- | Take a given number of entries in key order, beginning with the
-- smallest keys.
--
--
-- take n = fromDistinctAscList . take n . toAscList
--
take :: Int -> Map k a -> Map k a
-- | Drop a given number of entries in key order, beginning with the
-- smallest keys.
--
--
-- drop n = fromDistinctAscList . drop n . toAscList
--
drop :: Int -> Map k a -> Map k a
-- | O(log n). Split a map at a particular index.
--
--
-- splitAt !n !xs = (take n xs, drop n xs)
--
splitAt :: Int -> Map k a -> (Map k a, Map k a)
-- | O(log n). The minimal key of the map. Calls error if the
-- map is empty.
--
--
-- findMin (fromList [(5,"a"), (3,"b")]) == (3,"b")
-- findMin empty Error: empty map has no minimal element
--
findMin :: Map k a -> (k, a)
-- | O(log n). The maximal key of the map. Calls error if the
-- map is empty.
--
--
-- findMax (fromList [(5,"a"), (3,"b")]) == (5,"a")
-- findMax empty Error: empty map has no maximal element
--
findMax :: Map k a -> (k, a)
-- | O(log n). Delete the minimal key. Returns an empty map if the
-- map is empty.
--
--
-- deleteMin (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(5,"a"), (7,"c")]
-- deleteMin empty == empty
--
deleteMin :: Map k a -> Map k a
-- | O(log n). Delete the maximal key. Returns an empty map if the
-- map is empty.
--
--
-- deleteMax (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(3,"b"), (5,"a")]
-- deleteMax empty == empty
--
deleteMax :: Map k a -> Map k a
-- | O(log n). Delete and find the minimal element.
--
--
-- 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
--
deleteFindMin :: Map k a -> ((k, a), Map k a)
-- | O(log n). Delete and find the maximal element.
--
--
-- 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
--
deleteFindMax :: Map k a -> ((k, a), Map k a)
-- | O(log n). Update the value at the minimal key.
--
--
-- 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"
--
updateMin :: (a -> Maybe a) -> Map k a -> Map k a
-- | O(log n). Update the value at the maximal key.
--
--
-- 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"
--
updateMax :: (a -> Maybe a) -> Map k a -> Map k a
-- | O(log n). Update the value at the minimal key.
--
--
-- 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"
--
updateMinWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a
-- | O(log n). Update the value at the maximal key.
--
--
-- 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"
--
updateMaxWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a
-- | O(log n). Retrieves the value associated with minimal key of
-- the map, and the map stripped of that element, or Nothing if
-- passed an empty map.
--
--
-- minView (fromList [(5,"a"), (3,"b")]) == Just ("b", singleton 5 "a")
-- minView empty == Nothing
--
minView :: Map k a -> Maybe (a, Map k a)
-- | O(log n). Retrieves the value associated with maximal key of
-- the map, and the map stripped of that element, or Nothing if
-- passed an empty map.
--
--
-- maxView (fromList [(5,"a"), (3,"b")]) == Just ("a", singleton 3 "b")
-- maxView empty == Nothing
--
maxView :: Map k a -> Maybe (a, Map k a)
-- | O(log n). Retrieves the minimal (key,value) pair of the map,
-- and the map stripped of that element, or Nothing if passed an
-- empty map.
--
--
-- minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
-- minViewWithKey empty == Nothing
--
minViewWithKey :: Map k a -> Maybe ((k, a), Map k a)
-- | O(log n). Retrieves the maximal (key,value) pair of the map,
-- and the map stripped of that element, or Nothing if passed an
-- empty map.
--
--
-- maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b")
-- maxViewWithKey empty == Nothing
--
maxViewWithKey :: Map k a -> Maybe ((k, a), Map k a)
-- | O(n). Show the tree that implements the map. The tree is shown
-- in a compressed, hanging format. See showTreeWith.
-- | Deprecated: This function is being removed from the public API.
showTree :: (Show k, Show a) => Map k a -> String
-- | O(n). The expression (showTreeWith showelem hang
-- wide map) shows the tree that implements the map. Elements are
-- shown using the showElem function. If hang is
-- True, a hanging tree is shown otherwise a rotated tree
-- is shown. If wide is True, an extra wide version is
-- shown.
--
--
-- 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,())
--
-- | Deprecated: This function is being removed from the public API.
showTreeWith :: (k -> a -> String) -> Bool -> Bool -> Map k a -> String
-- | O(n). Test if the internal map structure is valid.
--
--
-- valid (fromAscList [(3,"b"), (5,"a")]) == True
-- valid (fromAscList [(5,"a"), (3,"b")]) == False
--
valid :: Ord k => Map k a -> Bool
-- | This module defines an API for writing functions that merge two maps.
-- The key functions are merge and mergeA. Each of these
-- can be used with several different "merge tactics".
--
-- The merge and mergeA functions are shared by the lazy
-- and strict modules. Only the choice of merge tactics determines
-- strictness. If you use mapMissing from this module then the
-- results will be forced before they are inserted. If you use
-- mapMissing from Data.Map.Lazy.Merge then they will not.
--
-- Efficiency note
--
-- The Category, Applicative, and Monad instances
-- for WhenMissing tactics are included because they are valid.
-- However, they are inefficient in many cases and should usually be
-- avoided. The instances for WhenMatched tactics should not pose
-- any major efficiency problems.
module Data.Map.Strict.Merge
-- | A tactic for dealing with keys present in one map but not the other in
-- merge.
--
-- A tactic of type SimpleWhenMissing k x z is an abstract
-- representation of a function of type k -> x -> Maybe z
-- .
type SimpleWhenMissing = WhenMissing Identity
-- | A tactic for dealing with keys present in both maps in merge.
--
-- A tactic of type SimpleWhenMatched k x y z is an abstract
-- representation of a function of type k -> x -> y ->
-- Maybe z .
type SimpleWhenMatched = WhenMatched Identity
-- | Merge two maps.
--
-- merge takes two WhenMissing tactics, a
-- WhenMatched tactic and two maps. It uses the tactics to merge
-- the maps. Its behavior is best understood via its fundamental tactics,
-- mapMaybeMissing and zipWithMaybeMatched.
--
-- Consider
--
--
-- merge (mapMaybeMissing g1)
-- (mapMaybeMissing g2)
-- (zipWithMaybeMatched f)
-- m1 m2
--
--
-- Take, for example,
--
--
-- m1 = [(0, a), (1, b), (3,c), (4, d)]
-- m2 = [(1, "one"), (2, "two"), (4, "three")]
--
--
-- merge will first 'align' these maps by key:
--
--
-- m1 = [(0, a), (1, b), (3,c), (4, d)]
-- m2 = [(1, "one"), (2, "two"), (4, "three")]
--
--
-- It will then pass the individual entries and pairs of entries to
-- g1, g2, or f as appropriate:
--
--
-- maybes = [g1 0 a, f 1 b "one", g2 2 "two", g1 3 c, f 4 d "three"]
--
--
-- This produces a Maybe for each key:
--
--
-- keys = 0 1 2 3 4
-- results = [Nothing, Just True, Just False, Nothing, Just True]
--
--
-- Finally, the Just results are collected into a map:
--
--
-- return value = [(1, True), (2, False), (4, True)]
--
--
-- The other tactics below are optimizations or simplifications of
-- mapMaybeMissing for special cases. Most importantly,
--
--
--
-- When merge is given three arguments, it is inlined at the call
-- site. To prevent excessive inlining, you should typically use
-- merge to define your custom combining functions.
--
-- Examples:
--
--
-- unionWithKey f = merge preserveMissing preserveMissing (zipWithMatched f)
--
--
--
-- intersectionWithKey f = merge dropMissing dropMissing (zipWithMatched f)
--
--
--
-- differenceWith f = merge diffPreserve diffDrop f
--
--
--
-- symmetricDifference = merge diffPreserve diffPreserve (\ _ _ _ -> Nothing)
--
--
--
-- mapEachPiece f g h = merge (diffMapWithKey f) (diffMapWithKey g)
--
merge :: Ord k => SimpleWhenMissing k a c -> SimpleWhenMissing k b c -> SimpleWhenMatched k a b c -> Map k a -> Map k b -> Map k c
-- | When a key is found in both maps, apply a function to the key and
-- values and maybe use the result in the merged map.
--
--
-- zipWithMaybeMatched :: (k -> x -> y -> Maybe z)
-- -> SimpleWhenMatched k x y z
--
zipWithMaybeMatched :: Applicative f => (k -> x -> y -> Maybe z) -> WhenMatched f k x y z
-- | When a key is found in both maps, apply a function to the key and
-- values and use the result in the merged map.
--
--
-- zipWithMatched :: (k -> x -> y -> z)
-- -> SimpleWhenMatched k x y z
--
zipWithMatched :: Applicative f => (k -> x -> y -> z) -> WhenMatched f k x y z
-- | Map over the entries whose keys are missing from the other map,
-- optionally removing some. This is the most powerful
-- SimpleWhenMissing tactic, but others are usually more
-- efficient.
--
--
-- mapMaybeMissing :: (k -> x -> Maybe y) -> SimpleWhenMissing k x y
--
--
--
-- mapMaybeMissing f = traverseMaybeMissing (\k x -> pure (f k x))
--
--
-- but mapMaybeMissing uses fewer unnecessary Applicative
-- operations.
mapMaybeMissing :: Applicative f => (k -> x -> Maybe y) -> WhenMissing f k x y
-- | Drop all the entries whose keys are missing from the other map.
--
--
-- dropMissing :: SimpleWhenMissing k x y
--
--
--
-- dropMissing = mapMaybeMissing (\_ _ -> Nothing)
--
--
-- but dropMissing is much faster.
dropMissing :: Applicative f => WhenMissing f k x y
-- | Preserve, unchanged, the entries whose keys are missing from the other
-- map.
--
--
-- preserveMissing :: SimpleWhenMissing k x x
--
--
--
-- preserveMissing = Lazy.Merge.mapMaybeMissing (\_ x -> Just x)
--
--
-- but preserveMissing is much faster.
preserveMissing :: Applicative f => WhenMissing f k x x
-- | Map over the entries whose keys are missing from the other map.
--
--
-- mapMissing :: (k -> x -> y) -> SimpleWhenMissing k x y
--
--
--
-- mapMissing f = mapMaybeMissing (\k x -> Just $ f k x)
--
--
-- but mapMissing is somewhat faster.
mapMissing :: Applicative f => (k -> x -> y) -> WhenMissing f k x y
-- | Filter the entries whose keys are missing from the other map.
--
--
-- filterMissing :: (k -> x -> Bool) -> SimpleWhenMissing k x x
--
--
--
-- filterMissing f = Lazy.Merge.mapMaybeMissing $ \k x -> guard (f k x) *> Just x
--
--
-- but this should be a little faster.
filterMissing :: Applicative f => (k -> x -> Bool) -> WhenMissing f k x x
-- | A tactic for dealing with keys present in one map but not the other in
-- merge or mergeA.
--
-- A tactic of type WhenMissing f k x z is an abstract
-- representation of a function of type k -> x -> f (Maybe z)
-- .
data WhenMissing f k x y
-- | A tactic for dealing with keys present in both maps in merge or
-- mergeA.
--
-- A tactic of type WhenMatched f k x y z is an abstract
-- representation of a function of type k -> x -> y -> f
-- (Maybe z) .
data WhenMatched f k x y z
-- | An applicative version of merge.
--
-- mergeA takes two WhenMissing tactics, a
-- WhenMatched tactic and two maps. It uses the tactics to merge
-- the maps. Its behavior is best understood via its fundamental tactics,
-- traverseMaybeMissing and zipWithMaybeAMatched.
--
-- Consider
--
--
-- mergeA (traverseMaybeMissing g1)
-- (traverseMaybeMissing g2)
-- (zipWithMaybeAMatched f)
-- m1 m2
--
--
-- Take, for example,
--
--
-- m1 = [(0, a), (1, b), (3,c), (4, d)]
-- m2 = [(1, "one"), (2, "two"), (4, "three")]
--
--
-- mergeA will first 'align' these maps by key:
--
--
-- m1 = [(0, a), (1, b), (3,c), (4, d)]
-- m2 = [(1, "one"), (2, "two"), (4, "three")]
--
--
-- It will then pass the individual entries and pairs of entries to
-- g1, g2, or f as appropriate:
--
--
-- actions = [g1 0 a, f 1 b "one", g2 2 "two", g1 3 c, f 4 d "three"]
--
--
-- Next, it will perform the actions in the actions list in
-- order from left to right.
--
--
-- keys = 0 1 2 3 4
-- results = [Nothing, Just True, Just False, Nothing, Just True]
--
--
-- Finally, the Just results are collected into a map:
--
--
-- return value = [(1, True), (2, False), (4, True)]
--
--
-- The other tactics below are optimizations or simplifications of
-- traverseMaybeMissing for special cases. Most importantly,
--
--
--
-- When mergeA is given three arguments, it is inlined at the call
-- site. To prevent excessive inlining, you should generally only use
-- mergeA to define custom combining functions.
mergeA :: (Applicative f, Ord k) => WhenMissing f k a c -> WhenMissing f k b c -> WhenMatched f k a b c -> Map k a -> Map k b -> f (Map k c)
-- | When a key is found in both maps, apply a function to the key and
-- values, perform the resulting action, and maybe use the result in the
-- merged map.
--
-- This is the fundamental WhenMatched tactic.
zipWithMaybeAMatched :: Applicative f => (k -> x -> y -> f (Maybe z)) -> WhenMatched f k x y z
-- | When a key is found in both maps, apply a function to the key and
-- values to produce an action and use its result in the merged map.
zipWithAMatched :: Applicative f => (k -> x -> y -> f z) -> WhenMatched f k x y z
-- | Traverse over the entries whose keys are missing from the other map,
-- optionally producing values to put in the result. This is the most
-- powerful WhenMissing tactic, but others are usually more
-- efficient.
traverseMaybeMissing :: Applicative f => (k -> x -> f (Maybe y)) -> WhenMissing f k x y
-- | Traverse over the entries whose keys are missing from the other map.
traverseMissing :: Applicative f => (k -> x -> f y) -> WhenMissing f k x y
-- | Filter the entries whose keys are missing from the other map using
-- some Applicative action.
--
--
-- filterAMissing f = Lazy.Merge.traverseMaybeMissing $
-- k x -> (b -> guard b *> Just x) $ f k x
--
--
-- but this should be a little faster.
filterAMissing :: Applicative f => (k -> x -> f Bool) -> WhenMissing f k x x
-- | Map covariantly over a WhenMissing f k x.
mapWhenMissing :: Functor f => (a -> b) -> WhenMissing f k x a -> WhenMissing f k x b
-- | Map covariantly over a WhenMatched f k x y.
mapWhenMatched :: Functor f => (a -> b) -> WhenMatched f k x y a -> WhenMatched f k x y b
-- | Along with zipWithMaybeAMatched, witnesses the isomorphism between
-- WhenMatched f k x y z and k -> x -> y -> f
-- (Maybe z).
runWhenMatched :: WhenMatched f k x y z -> k -> x -> y -> f (Maybe z)
-- | Along with traverseMaybeMissing, witnesses the isomorphism between
-- WhenMissing f k x y and k -> x -> f (Maybe y).
runWhenMissing :: WhenMissing f k x y -> k -> x -> f (Maybe y)
-- | Note: You should use Data.Map.Strict instead of this
-- module if:
--
--
-- - You will eventually need all the values stored.
-- - The stored values don't represent large virtual data structures to
-- be lazily computed.
--
--
-- An efficient implementation of ordered maps from keys to values
-- (dictionaries).
--
-- These modules are intended to be imported qualified, to avoid name
-- clashes with Prelude functions, e.g.
--
--
-- import qualified Data.Map as Map
--
--
-- The implementation of Map is based on size balanced
-- binary trees (or trees of bounded balance) as described by:
--
--
-- - Stephen Adams, "Efficient sets: a balancing act", Journal
-- of Functional Programming 3(4):553-562, October 1993,
-- http://www.swiss.ai.mit.edu/~adams/BB/.
-- - J. Nievergelt and E.M. Reingold, "Binary search trees of
-- bounded balance", SIAM journal of computing 2(1), March 1973.
--
--
-- Bounds for union, intersection, and difference
-- are as given by
--
--
--
-- Note that the implementation is left-biased -- the elements of
-- a first argument are always preferred to the second, for example in
-- union or insert.
--
-- Warning: The size of the map must not exceed
-- maxBound::Int. Violation of this condition is not detected
-- and if the size limit is exceeded, its behaviour is undefined.
--
-- Operation comments contain the operation time complexity in the Big-O
-- notation (http://en.wikipedia.org/wiki/Big_O_notation).
module Data.Map
-- | O(log n). Same as insertWith, but the value being
-- inserted to the map is evaluated to WHNF beforehand.
--
-- For example, to update a counter:
--
--
-- insertWith' (+) k 1 m
--
-- | Deprecated: As of version 0.5, replaced by insertWith.
insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
-- | O(log n). Same as insertWithKey, but the value being
-- inserted to the map is evaluated to WHNF beforehand.
-- | Deprecated: As of version 0.5, replaced by
-- insertWithKey.
insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
-- | O(log n). Same as insertLookupWithKey, but the value
-- being inserted to the map is evaluated to WHNF beforehand.
-- | Deprecated: As of version 0.5, replaced by
-- insertLookupWithKey.
insertLookupWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
-- | O(n). Fold the values in the map using the given
-- right-associative binary operator. This function is an equivalent of
-- foldr and is present for compatibility only.
-- | Deprecated: As of version 0.5, replaced by foldr.
fold :: (a -> b -> b) -> b -> Map k a -> b
-- | O(n). Fold the keys and values in the map using the given
-- right-associative binary operator. This function is an equivalent of
-- foldrWithKey and is present for compatibility only.
-- | Deprecated: As of version 0.4, replaced by foldrWithKey.
foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
-- | An efficient implementation of integer sets.
--
-- These modules are intended to be imported qualified, to avoid name
-- clashes with Prelude functions, e.g.
--
--
-- import Data.IntSet (IntSet)
-- import qualified Data.IntSet as IntSet
--
--
-- The implementation is based on big-endian patricia trees. This
-- data structure performs especially well on binary operations like
-- union and intersection. However, my benchmarks show that
-- it is also (much) faster on insertions and deletions when compared to
-- a generic size-balanced set implementation (see Data.Set).
--
--
-- - Chris Okasaki and Andy Gill, "Fast Mergeable Integer Maps",
-- Workshop on ML, September 1998, pages 77-86,
-- http://citeseer.ist.psu.edu/okasaki98fast.html
-- - D.R. Morrison, "/PATRICIA -- Practical Algorithm To Retrieve
-- Information Coded In Alphanumeric/", Journal of the ACM, 15(4),
-- October 1968, pages 514-534.
--
--
-- Additionally, this implementation places bitmaps in the leaves of the
-- tree. Their size is the natural size of a machine word (32 or 64 bits)
-- and greatly reduce memory footprint and execution times for dense
-- sets, e.g. sets where it is likely that many values lie close to each
-- other. The asymptotics are not affected by this optimization.
--
-- Many operations have a worst-case complexity of O(min(n,W)).
-- This means that the operation can become linear in the number of
-- elements with a maximum of W -- the number of bits in an
-- Int (32 or 64).
module Data.IntSet
-- | A set of integers.
data IntSet
type Key = Int
-- | O(n+m). See difference.
(\\) :: IntSet -> IntSet -> IntSet
infixl 9 \\
-- | O(1). Is the set empty?
null :: IntSet -> Bool
-- | O(n). Cardinality of the set.
size :: IntSet -> Int
-- | O(min(n,W)). Is the value a member of the set?
member :: Key -> IntSet -> Bool
-- | O(min(n,W)). Is the element not in the set?
notMember :: Key -> IntSet -> Bool
-- | O(log n). Find largest element smaller than the given one.
--
--
-- lookupLT 3 (fromList [3, 5]) == Nothing
-- lookupLT 5 (fromList [3, 5]) == Just 3
--
lookupLT :: Key -> IntSet -> Maybe Key
-- | O(log n). Find smallest element greater than the given one.
--
--
-- lookupGT 4 (fromList [3, 5]) == Just 5
-- lookupGT 5 (fromList [3, 5]) == Nothing
--
lookupGT :: Key -> IntSet -> Maybe Key
-- | O(log n). Find largest element smaller or equal to the given
-- one.
--
--
-- lookupLE 2 (fromList [3, 5]) == Nothing
-- lookupLE 4 (fromList [3, 5]) == Just 3
-- lookupLE 5 (fromList [3, 5]) == Just 5
--
lookupLE :: Key -> IntSet -> Maybe Key
-- | O(log n). Find smallest element greater or equal to the given
-- one.
--
--
-- lookupGE 3 (fromList [3, 5]) == Just 3
-- lookupGE 4 (fromList [3, 5]) == Just 5
-- lookupGE 6 (fromList [3, 5]) == Nothing
--
lookupGE :: Key -> IntSet -> Maybe Key
-- | O(n+m). Is this a subset? (s1 isSubsetOf s2)
-- tells whether s1 is a subset of s2.
isSubsetOf :: IntSet -> IntSet -> Bool
-- | O(n+m). Is this a proper subset? (ie. a subset but not equal).
isProperSubsetOf :: IntSet -> IntSet -> Bool
-- | O(1). The empty set.
empty :: IntSet
-- | O(1). A set of one element.
singleton :: Key -> IntSet
-- | O(min(n,W)). Add a value to the set. There is no left- or right
-- bias for IntSets.
insert :: Key -> IntSet -> IntSet
-- | O(min(n,W)). Delete a value in the set. Returns the original
-- set when the value was not present.
delete :: Key -> IntSet -> IntSet
-- | O(n+m). The union of two sets.
union :: IntSet -> IntSet -> IntSet
-- | The union of a list of sets.
unions :: [IntSet] -> IntSet
-- | O(n+m). Difference between two sets.
difference :: IntSet -> IntSet -> IntSet
-- | O(n+m). The intersection of two sets.
intersection :: IntSet -> IntSet -> IntSet
-- | O(n). Filter all elements that satisfy some predicate.
filter :: (Key -> Bool) -> IntSet -> IntSet
-- | O(n). partition the set according to some predicate.
partition :: (Key -> Bool) -> IntSet -> (IntSet, IntSet)
-- | O(min(n,W)). The expression (split x set) is a
-- pair (set1,set2) where set1 comprises the elements
-- of set less than x and set2 comprises the
-- elements of set greater than x.
--
--
-- split 3 (fromList [1..5]) == (fromList [1,2], fromList [4,5])
--
split :: Key -> IntSet -> (IntSet, IntSet)
-- | O(min(n,W)). Performs a split but also returns whether
-- the pivot element was found in the original set.
splitMember :: Key -> IntSet -> (IntSet, Bool, IntSet)
-- | O(1). Decompose a set into pieces based on the structure of the
-- underlying tree. This function is useful for consuming a set in
-- parallel.
--
-- No guarantee is made as to the sizes of the pieces; an internal, but
-- deterministic process determines this. However, it is guaranteed that
-- the pieces returned will be in ascending order (all elements in the
-- first submap less than all elements in the second, and so on).
--
-- Examples:
--
--
-- splitRoot (fromList [1..120]) == [fromList [1..63],fromList [64..120]]
-- splitRoot empty == []
--
--
-- Note that the current implementation does not return more than two
-- subsets, but you should not depend on this behaviour because it can
-- change in the future without notice. Also, the current version does
-- not continue splitting all the way to individual singleton sets -- it
-- stops at some point.
splitRoot :: IntSet -> [IntSet]
-- | O(n*min(n,W)). map f s is the set obtained by
-- applying f to each element of s.
--
-- It's worth noting that the size of the result may be smaller if, for
-- some (x,y), x /= y && f x == f y
map :: (Key -> Key) -> IntSet -> IntSet
-- | O(n). Fold the elements in the set using the given
-- right-associative binary operator, such that foldr f z ==
-- foldr f z . toAscList.
--
-- For example,
--
--
-- toAscList set = foldr (:) [] set
--
foldr :: (Key -> b -> b) -> b -> IntSet -> b
-- | O(n). Fold the elements in the set using the given
-- left-associative binary operator, such that foldl f z ==
-- foldl f z . toAscList.
--
-- For example,
--
--
-- toDescList set = foldl (flip (:)) [] set
--
foldl :: (a -> Key -> a) -> a -> IntSet -> a
-- | O(n). A strict version of foldr. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldr' :: (Key -> b -> b) -> b -> IntSet -> b
-- | O(n). A strict version of foldl. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldl' :: (a -> Key -> a) -> a -> IntSet -> a
-- | O(n). Fold the elements in the set using the given
-- right-associative binary operator. This function is an equivalent of
-- foldr and is present for compatibility only.
--
-- Please note that fold will be deprecated in the future and
-- removed.
fold :: (Key -> b -> b) -> b -> IntSet -> b
-- | O(min(n,W)). The minimal element of the set.
findMin :: IntSet -> Key
-- | O(min(n,W)). The maximal element of a set.
findMax :: IntSet -> Key
-- | O(min(n,W)). Delete the minimal element. Returns an empty set
-- if the set is empty.
--
-- Note that this is a change of behaviour for consistency with
-- Set – versions prior to 0.5 threw an error if the IntSet
-- was already empty.
deleteMin :: IntSet -> IntSet
-- | O(min(n,W)). Delete the maximal element. Returns an empty set
-- if the set is empty.
--
-- Note that this is a change of behaviour for consistency with
-- Set – versions prior to 0.5 threw an error if the IntSet
-- was already empty.
deleteMax :: IntSet -> IntSet
-- | O(min(n,W)). Delete and find the minimal element.
--
--
-- deleteFindMin set = (findMin set, deleteMin set)
--
deleteFindMin :: IntSet -> (Key, IntSet)
-- | O(min(n,W)). Delete and find the maximal element.
--
--
-- deleteFindMax set = (findMax set, deleteMax set)
--
deleteFindMax :: IntSet -> (Key, IntSet)
-- | O(min(n,W)). Retrieves the maximal key of the set, and the set
-- stripped of that element, or Nothing if passed an empty set.
maxView :: IntSet -> Maybe (Key, IntSet)
-- | O(min(n,W)). Retrieves the minimal key of the set, and the set
-- stripped of that element, or Nothing if passed an empty set.
minView :: IntSet -> Maybe (Key, IntSet)
-- | O(n). An alias of toAscList. The elements of a set in
-- ascending order. Subject to list fusion.
elems :: IntSet -> [Key]
-- | O(n). Convert the set to a list of elements. Subject to list
-- fusion.
toList :: IntSet -> [Key]
-- | O(n*min(n,W)). Create a set from a list of integers.
fromList :: [Key] -> IntSet
-- | O(n). Convert the set to an ascending list of elements. Subject
-- to list fusion.
toAscList :: IntSet -> [Key]
-- | O(n). Convert the set to a descending list of elements. Subject
-- to list fusion.
toDescList :: IntSet -> [Key]
-- | O(n). Build a set from an ascending list of elements. The
-- precondition (input list is ascending) is not checked.
fromAscList :: [Key] -> IntSet
-- | O(n). Build a set from an ascending list of distinct elements.
-- The precondition (input list is strictly ascending) is not
-- checked.
fromDistinctAscList :: [Key] -> IntSet
-- | O(n). Show the tree that implements the set. The tree is shown
-- in a compressed, hanging format.
showTree :: IntSet -> String
-- | O(n). The expression (showTreeWith hang wide
-- map) shows the tree that implements the set. If hang is
-- True, a hanging tree is shown otherwise a rotated tree
-- is shown. If wide is True, an extra wide version is
-- shown.
showTreeWith :: Bool -> Bool -> IntSet -> String
-- | An efficient implementation of maps from integer keys to values
-- (dictionaries).
--
-- API of this module is strict in the keys, but lazy in the values. If
-- you need value-strict maps, use Data.IntMap.Strict instead. The
-- IntMap type itself is shared between the lazy and strict
-- modules, meaning that the same IntMap value can be passed to
-- functions in both modules (although that is rarely needed).
--
-- These modules are intended to be imported qualified, to avoid name
-- clashes with Prelude functions, e.g.
--
--
-- import Data.IntMap.Lazy (IntMap)
-- import qualified Data.IntMap.Lazy as IntMap
--
--
-- The implementation is based on big-endian patricia trees. This
-- data structure performs especially well on binary operations like
-- union and intersection. However, my benchmarks show that
-- it is also (much) faster on insertions and deletions when compared to
-- a generic size-balanced map implementation (see Data.Map).
--
--
-- - Chris Okasaki and Andy Gill, "Fast Mergeable Integer Maps",
-- Workshop on ML, September 1998, pages 77-86,
-- http://citeseer.ist.psu.edu/okasaki98fast.html
-- - D.R. Morrison, "/PATRICIA -- Practical Algorithm To Retrieve
-- Information Coded In Alphanumeric/", Journal of the ACM, 15(4),
-- October 1968, pages 514-534.
--
--
-- Operation comments contain the operation time complexity in the Big-O
-- notation http://en.wikipedia.org/wiki/Big_O_notation. Many
-- operations have a worst-case complexity of O(min(n,W)). This
-- means that the operation can become linear in the number of elements
-- with a maximum of W -- the number of bits in an Int (32
-- or 64).
module Data.IntMap.Lazy
-- | A map of integers to values a.
data IntMap a
type Key = Int
-- | O(min(n,W)). Find the value at a key. Calls error when
-- the element can not be found.
--
--
-- fromList [(5,'a'), (3,'b')] ! 1 Error: element not in the map
-- fromList [(5,'a'), (3,'b')] ! 5 == 'a'
--
(!) :: IntMap a -> Key -> a
-- | Same as difference.
(\\) :: IntMap a -> IntMap b -> IntMap a
infixl 9 \\
-- | O(1). Is the map empty?
--
--
-- Data.IntMap.null (empty) == True
-- Data.IntMap.null (singleton 1 'a') == False
--
null :: IntMap a -> Bool
-- | O(n). Number of elements in the map.
--
--
-- size empty == 0
-- size (singleton 1 'a') == 1
-- size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3
--
size :: IntMap a -> Int
-- | O(min(n,W)). Is the key a member of the map?
--
--
-- member 5 (fromList [(5,'a'), (3,'b')]) == True
-- member 1 (fromList [(5,'a'), (3,'b')]) == False
--
member :: Key -> IntMap a -> Bool
-- | O(min(n,W)). Is the key not a member of the map?
--
--
-- notMember 5 (fromList [(5,'a'), (3,'b')]) == False
-- notMember 1 (fromList [(5,'a'), (3,'b')]) == True
--
notMember :: Key -> IntMap a -> Bool
-- | O(min(n,W)). Lookup the value at a key in the map. See also
-- lookup.
lookup :: Key -> IntMap a -> Maybe a
-- | O(min(n,W)). The expression (findWithDefault def k
-- map) returns the value at key k or returns def
-- when the key is not an element of the map.
--
--
-- findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
-- findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
--
findWithDefault :: a -> Key -> IntMap a -> a
-- | O(log n). Find largest key smaller than the given one and
-- return the corresponding (key, value) pair.
--
--
-- lookupLT 3 (fromList [(3,'a'), (5,'b')]) == Nothing
-- lookupLT 4 (fromList [(3,'a'), (5,'b')]) == Just (3, 'a')
--
lookupLT :: Key -> IntMap a -> Maybe (Key, a)
-- | O(log n). Find smallest key greater than the given one and
-- return the corresponding (key, value) pair.
--
--
-- lookupGT 4 (fromList [(3,'a'), (5,'b')]) == Just (5, 'b')
-- lookupGT 5 (fromList [(3,'a'), (5,'b')]) == Nothing
--
lookupGT :: Key -> IntMap a -> Maybe (Key, a)
-- | O(log n). Find largest key smaller or equal to the given one
-- and return the corresponding (key, value) pair.
--
--
-- 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')
--
lookupLE :: Key -> IntMap a -> Maybe (Key, a)
-- | O(log n). Find smallest key greater or equal to the given one
-- and return the corresponding (key, value) pair.
--
--
-- 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
--
lookupGE :: Key -> IntMap a -> Maybe (Key, a)
-- | O(1). The empty map.
--
--
-- empty == fromList []
-- size empty == 0
--
empty :: IntMap a
-- | O(1). A map of one element.
--
--
-- singleton 1 'a' == fromList [(1, 'a')]
-- size (singleton 1 'a') == 1
--
singleton :: Key -> a -> IntMap a
-- | O(min(n,W)). Insert a new key/value pair in the map. If the key
-- is already present in the map, the associated value is replaced with
-- the supplied value, i.e. insert is equivalent to
-- 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'
--
insert :: Key -> a -> IntMap a -> IntMap a
-- | O(min(n,W)). Insert with a combining function.
-- insertWith f key value mp will insert the pair (key,
-- value) into mp if key does not exist in the map. If the key
-- does exist, the function will insert 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"
--
insertWith :: (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
-- | O(min(n,W)). Insert with a combining function.
-- insertWithKey f key value mp will insert the pair
-- (key, value) into mp if key does not exist in the map. If the
-- key does exist, the function will insert 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"
--
insertWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
-- | O(min(n,W)). The expression (insertLookupWithKey f k
-- x map) is a pair where the first element is equal to
-- (lookup k map) and the second element equal to
-- (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")
--
--
-- This is how to define insertLookup using
-- 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")])
--
insertLookupWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> (Maybe a, IntMap a)
-- | O(min(n,W)). Delete a key and its value from the map. When the
-- key is not a member of the map, the original map is returned.
--
--
-- 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
--
delete :: Key -> IntMap a -> IntMap a
-- | O(min(n,W)). Adjust a value at a specific key. When the key is
-- not a member of the map, the original map is returned.
--
--
-- 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
--
adjust :: (a -> a) -> Key -> IntMap a -> IntMap a
-- | O(min(n,W)). Adjust a value at a specific key. When the key is
-- not a member of the map, the original map is returned.
--
--
-- 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
--
adjustWithKey :: (Key -> a -> a) -> Key -> IntMap a -> IntMap a
-- | O(min(n,W)). The expression (update f k map)
-- updates the value x at k (if it is in the map). If
-- (f x) is Nothing, the element is deleted. If it is
-- (Just y), the key k is bound to the new value
-- 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"
--
update :: (a -> Maybe a) -> Key -> IntMap a -> IntMap a
-- | O(min(n,W)). The expression (update f k map)
-- updates the value x at k (if it is in the map). If
-- (f k x) is Nothing, the element is deleted. If it is
-- (Just y), the key k is bound to the new value
-- 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"
--
updateWithKey :: (Key -> a -> Maybe a) -> Key -> IntMap a -> IntMap a
-- | O(min(n,W)). Lookup and update. The function returns original
-- value, if it is updated. This is different behavior than
-- updateLookupWithKey. Returns the original key value if the map
-- entry is deleted.
--
--
-- 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")
--
updateLookupWithKey :: (Key -> a -> Maybe a) -> Key -> IntMap a -> (Maybe a, IntMap a)
-- | O(min(n,W)). The expression (alter f k map)
-- alters the value x at k, or absence thereof.
-- alter can be used to insert, delete, or update a value in an
-- IntMap. In short : lookup k (alter f k m) = f
-- (lookup k m).
alter :: (Maybe a -> Maybe a) -> Key -> IntMap a -> IntMap a
-- | O(log n). The expression (alterF f k map)
-- alters the value x at k, or absence thereof.
-- alterF can be used to inspect, insert, delete, or update a
-- value in an IntMap. In short : lookup k $
-- alterF f k m = f (lookup k m).
--
-- Example:
--
--
-- interactiveAlter :: Int -> IntMap String -> IO (IntMap String)
-- interactiveAlter k m = alterF f k m where
-- f Nothing -> do
-- putStrLn $ show k ++
-- " was not found in the map. Would you like to add it?"
-- getUserResponse1 :: IO (Maybe String)
-- f (Just old) -> do
-- putStrLn "The key is currently bound to " ++ show old ++
-- ". Would you like to change or delete it?"
-- getUserresponse2 :: IO (Maybe String)
--
--
-- alterF is the most general operation for working with an
-- individual key that may or may not be in a given map.
--
-- Note: alterF is a flipped version of the at combinator
-- from At.
alterF :: Functor f => (Maybe a -> f (Maybe a)) -> Key -> IntMap a -> f (IntMap a)
-- | O(n+m). The (left-biased) union of two maps. It prefers the
-- first map when duplicate keys are encountered, i.e. (union
-- == unionWith const).
--
--
-- union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
--
union :: IntMap a -> IntMap a -> IntMap a
-- | O(n+m). The union with a combining function.
--
--
-- unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
--
unionWith :: (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
-- | O(n+m). The union with a combining function.
--
--
-- 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")]
--
unionWithKey :: (Key -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
-- | The union of a list of maps.
--
--
-- 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")]
--
unions :: [IntMap a] -> IntMap a
-- | The union of a list of maps, with a combining operation.
--
--
-- unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
-- == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
--
unionsWith :: (a -> a -> a) -> [IntMap a] -> IntMap a
-- | O(n+m). Difference between two maps (based on keys).
--
--
-- difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"
--
difference :: IntMap a -> IntMap b -> IntMap a
-- | O(n+m). Difference with a combining function.
--
--
-- 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"
--
differenceWith :: (a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
-- | O(n+m). Difference with a combining function. When two equal
-- keys are encountered, the combining function is applied to the key and
-- both values. If it returns Nothing, the element is discarded
-- (proper set difference). If it returns (Just y), the
-- element is updated with a new value 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"
--
differenceWithKey :: (Key -> a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
-- | O(n+m). The (left-biased) intersection of two maps (based on
-- keys).
--
--
-- intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a"
--
intersection :: IntMap a -> IntMap b -> IntMap a
-- | O(n+m). The intersection with a combining function.
--
--
-- intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA"
--
intersectionWith :: (a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
-- | O(n+m). The intersection with a combining function.
--
--
-- 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"
--
intersectionWithKey :: (Key -> a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
-- | O(n+m). A high-performance universal combining function. Using
-- mergeWithKey, all combining functions can be defined without
-- any loss of efficiency (with exception of union,
-- difference and intersection, where sharing of some nodes
-- is lost with mergeWithKey).
--
-- Please make sure you know what is going on when using
-- mergeWithKey, otherwise you can be surprised by unexpected code
-- growth or even corruption of the data structure.
--
-- When mergeWithKey is given three arguments, it is inlined to
-- the call site. You should therefore use mergeWithKey only to
-- define your custom combining functions. For example, you could define
-- unionWithKey, differenceWithKey and
-- intersectionWithKey as
--
--
-- 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
--
--
-- When calling mergeWithKey combine only1 only2, a
-- function combining two IntMaps is created, such that
--
--
-- - if a key is present in both maps, it is passed with both
-- corresponding values to the combine function. Depending on
-- the result, the key is either present in the result with specified
-- value, or is left out;
-- - a nonempty subtree present only in the first map is passed to
-- only1 and the output is added to the result;
-- - a nonempty subtree present only in the second map is passed to
-- only2 and the output is added to the result.
--
--
-- The only1 and only2 methods must return a map
-- with a subset (possibly empty) of the keys of the given map. The
-- values can be modified arbitrarily. Most common variants of
-- only1 and only2 are id and const
-- empty, but for example map f or
-- filterWithKey f could be used for any f.
mergeWithKey :: (Key -> a -> b -> Maybe c) -> (IntMap a -> IntMap c) -> (IntMap b -> IntMap c) -> IntMap a -> IntMap b -> IntMap c
-- | O(n). Map a function over all values in the map.
--
--
-- map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
--
map :: (a -> b) -> IntMap a -> IntMap b
-- | O(n). Map a function over all values in the map.
--
--
-- let f key x = (show key) ++ ":" ++ x
-- mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]
--
mapWithKey :: (Key -> a -> b) -> IntMap a -> IntMap b
-- | O(n). traverseWithKey f s == fromList
-- $ traverse ((k, v) -> (,) k $ f k v)
-- (toList m) That is, behaves exactly like a regular
-- traverse except that the traversing function also has access to
-- the key associated with a value.
--
--
-- 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
--
traverseWithKey :: Applicative t => (Key -> a -> t b) -> IntMap a -> t (IntMap b)
-- | O(n). The function mapAccum threads an
-- accumulating argument through the map in ascending order of keys.
--
--
-- let f a b = (a ++ b, b ++ "X")
-- mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
--
mapAccum :: (a -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
-- | 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")])
--
mapAccumWithKey :: (a -> Key -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
-- | O(n). The function mapAccumR threads an
-- accumulating argument through the map in descending order of keys.
mapAccumRWithKey :: (a -> Key -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
-- | O(n*min(n,W)). mapKeys f s is the map obtained
-- by applying f to each key of s.
--
-- The size of the result may be smaller if f maps two or more
-- distinct keys to the same new key. In this case the value at the
-- greatest of the original keys is retained.
--
--
-- 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"
--
mapKeys :: (Key -> Key) -> IntMap a -> IntMap a
-- | O(n*min(n,W)). mapKeysWith c f s is the map
-- obtained by applying f to each key of s.
--
-- The size of the result may be smaller if f maps two or more
-- distinct keys to the same new key. In this case the associated values
-- will be combined using 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"
--
mapKeysWith :: (a -> a -> a) -> (Key -> Key) -> IntMap a -> IntMap a
-- | O(n*min(n,W)). mapKeysMonotonic f s ==
-- mapKeys f s, but works only when f is strictly
-- monotonic. That is, for any values x and y, if
-- x < y then f x < f y. The
-- precondition is not checked. Semi-formally, we have:
--
--
-- and [x < y ==> f x < f y | x <- ls, y <- ls]
-- ==> mapKeysMonotonic f s == mapKeys f s
-- where ls = keys s
--
--
-- This means that f maps distinct original keys to distinct
-- resulting keys. This function has slightly better performance than
-- mapKeys.
--
--
-- mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
--
mapKeysMonotonic :: (Key -> Key) -> IntMap a -> IntMap a
-- | O(n). Fold the values in the map using the given
-- right-associative binary operator, such that foldr f z ==
-- foldr f z . elems.
--
-- For example,
--
--
-- elems map = foldr (:) [] map
--
--
--
-- let f a len = len + (length a)
-- foldr f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
--
foldr :: (a -> b -> b) -> b -> IntMap a -> b
-- | O(n). Fold the values in the map using the given
-- left-associative binary operator, such that foldl f z ==
-- foldl f z . elems.
--
-- For example,
--
--
-- elems = reverse . foldl (flip (:)) []
--
--
--
-- let f len a = len + (length a)
-- foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
--
foldl :: (a -> b -> a) -> a -> IntMap b -> a
-- | O(n). Fold the keys and values in the map using the given
-- right-associative binary operator, such that foldrWithKey f
-- z == foldr (uncurry f) z . toAscList.
--
-- For example,
--
--
-- 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)"
--
foldrWithKey :: (Key -> a -> b -> b) -> b -> IntMap a -> b
-- | O(n). Fold the keys and values in the map using the given
-- left-associative binary operator, such that foldlWithKey f
-- z == foldl (\z' (kx, x) -> f z' kx x) z .
-- toAscList.
--
-- For example,
--
--
-- 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)"
--
foldlWithKey :: (a -> Key -> b -> a) -> a -> IntMap b -> a
-- | O(n). Fold the keys and values in the map using the given
-- monoid, such that
--
--
-- foldMapWithKey f = fold . mapWithKey f
--
--
-- This can be an asymptotically faster than foldrWithKey or
-- foldlWithKey for some monoids.
foldMapWithKey :: Monoid m => (Key -> a -> m) -> IntMap a -> m
-- | O(n). A strict version of foldr. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> IntMap a -> b
-- | O(n). A strict version of foldl. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldl' :: (a -> b -> a) -> a -> IntMap b -> a
-- | O(n). A strict version of foldrWithKey. Each application
-- of the operator is evaluated before using the result in the next
-- application. This function is strict in the starting value.
foldrWithKey' :: (Key -> a -> b -> b) -> b -> IntMap a -> b
-- | O(n). A strict version of foldlWithKey. Each application
-- of the operator is evaluated before using the result in the next
-- application. This function is strict in the starting value.
foldlWithKey' :: (a -> Key -> b -> a) -> a -> IntMap b -> a
-- | O(n). Return all elements of the map in the ascending order of
-- their keys. Subject to list fusion.
--
--
-- elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]
-- elems empty == []
--
elems :: IntMap a -> [a]
-- | O(n). Return all keys of the map in ascending order. Subject to
-- list fusion.
--
--
-- keys (fromList [(5,"a"), (3,"b")]) == [3,5]
-- keys empty == []
--
keys :: IntMap a -> [Key]
-- | O(n). An alias for toAscList. Returns all key/value
-- pairs in the map in ascending key order. Subject to list fusion.
--
--
-- assocs (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
-- assocs empty == []
--
assocs :: IntMap a -> [(Key, a)]
-- | O(n*min(n,W)). The set of all keys of the map.
--
--
-- keysSet (fromList [(5,"a"), (3,"b")]) == Data.IntSet.fromList [3,5]
-- keysSet empty == Data.IntSet.empty
--
keysSet :: IntMap a -> IntSet
-- | O(n). Build a map from a set of keys and a function which for
-- each key computes its value.
--
--
-- fromSet (\k -> replicate k 'a') (Data.IntSet.fromList [3, 5]) == fromList [(5,"aaaaa"), (3,"aaa")]
-- fromSet undefined Data.IntSet.empty == empty
--
fromSet :: (Key -> a) -> IntSet -> IntMap a
-- | O(n). Convert the map to a list of key/value pairs. Subject to
-- list fusion.
--
--
-- toList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
-- toList empty == []
--
toList :: IntMap a -> [(Key, a)]
-- | O(n*min(n,W)). Create a map from a list of key/value pairs.
--
--
-- 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")]
--
fromList :: [(Key, a)] -> IntMap a
-- | O(n*min(n,W)). Create a map from a list of key/value pairs with
-- a combining function. See also fromAscListWith.
--
--
-- fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")] == fromList [(3, "ab"), (5, "cba")]
-- fromListWith (++) [] == empty
--
fromListWith :: (a -> a -> a) -> [(Key, a)] -> IntMap a
-- | O(n*min(n,W)). Build a map from a list of key/value pairs with
-- a combining function. See also 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
--
fromListWithKey :: (Key -> a -> a -> a) -> [(Key, a)] -> IntMap a
-- | O(n). Convert the map to a list of key/value pairs where the
-- keys are in ascending order. Subject to list fusion.
--
--
-- toAscList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
--
toAscList :: IntMap a -> [(Key, a)]
-- | O(n). Convert the map to a list of key/value pairs where the
-- keys are in descending order. Subject to list fusion.
--
--
-- toDescList (fromList [(5,"a"), (3,"b")]) == [(5,"a"), (3,"b")]
--
toDescList :: IntMap a -> [(Key, a)]
-- | O(n). Build a map from a list of key/value pairs where the keys
-- are in ascending order.
--
--
-- fromAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
-- fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")]
--
fromAscList :: [(Key, a)] -> IntMap a
-- | O(n). Build a map from a list of key/value pairs where the keys
-- are in ascending order, with a combining function on equal keys.
-- The precondition (input list is ascending) is not checked.
--
--
-- fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
--
fromAscListWith :: (a -> a -> a) -> [(Key, a)] -> IntMap a
-- | O(n). Build a map from a list of key/value pairs where the keys
-- are in ascending order, with a combining function on equal keys.
-- The precondition (input list is ascending) is not checked.
--
--
-- 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")]
--
fromAscListWithKey :: (Key -> a -> a -> a) -> [(Key, a)] -> IntMap a
-- | O(n). Build a map from a list of key/value pairs where the keys
-- are in ascending order and all distinct. The precondition (input
-- list is strictly ascending) is not checked.
--
--
-- fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
--
fromDistinctAscList :: forall a. [(Key, a)] -> IntMap a
-- | O(n). Filter all values that satisfy some predicate.
--
--
-- 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
--
filter :: (a -> Bool) -> IntMap a -> IntMap a
-- | O(n). Filter all keys/values that satisfy some predicate.
--
--
-- filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--
filterWithKey :: (Key -> a -> Bool) -> IntMap a -> IntMap a
-- | O(n+m). The restriction of a map to the keys in a set.
--
--
-- m restrictKeys s = filterWithKey (k _ -> k `member' s) m
--
restrictKeys :: IntMap a -> IntSet -> IntMap a
-- | Remove all the keys in a given set from a map.
--
--
-- m withoutKeys s = filterWithKey (k _ -> k `notMember' s) m
--
withoutKeys :: IntMap a -> IntSet -> IntMap a
-- | O(n). Partition the map according to some predicate. The first
-- map contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate. See also 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")])
--
partition :: (a -> Bool) -> IntMap a -> (IntMap a, IntMap a)
-- | O(n). Partition the map according to some predicate. The first
-- map contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate. See also 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")])
--
partitionWithKey :: (Key -> a -> Bool) -> IntMap a -> (IntMap a, IntMap a)
-- | O(n). Map values and collect the Just results.
--
--
-- let f x = if x == "a" then Just "new a" else Nothing
-- mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"
--
mapMaybe :: (a -> Maybe b) -> IntMap a -> IntMap b
-- | O(n). Map keys/values and collect the Just results.
--
--
-- let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing
-- mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"
--
mapMaybeWithKey :: (Key -> a -> Maybe b) -> IntMap a -> IntMap b
-- | O(n). Map values and separate the Left and Right
-- results.
--
--
-- 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")])
--
mapEither :: (a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)
-- | O(n). Map keys/values and separate the Left and
-- Right results.
--
--
-- 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")])
--
mapEitherWithKey :: (Key -> a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)
-- | O(min(n,W)). The expression (split k map) is a
-- pair (map1,map2) where all keys in map1 are lower
-- than k and all keys in map2 larger than k.
-- Any key equal to k is found in neither map1 nor
-- 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)
--
split :: Key -> IntMap a -> (IntMap a, IntMap a)
-- | O(min(n,W)). Performs a split but also returns whether
-- the pivot key was found in the original 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)
--
splitLookup :: Key -> IntMap a -> (IntMap a, Maybe a, IntMap a)
-- | O(1). Decompose a map into pieces based on the structure of the
-- underlying tree. This function is useful for consuming a map in
-- parallel.
--
-- No guarantee is made as to the sizes of the pieces; an internal, but
-- deterministic process determines this. However, it is guaranteed that
-- the pieces returned will be in ascending order (all elements in the
-- first submap less than all elements in the second, and so on).
--
-- Examples:
--
--
-- splitRoot (fromList (zip [1..6::Int] ['a'..])) ==
-- [fromList [(1,'a'),(2,'b'),(3,'c')],fromList [(4,'d'),(5,'e'),(6,'f')]]
--
--
--
-- splitRoot empty == []
--
--
-- Note that the current implementation does not return more than two
-- submaps, but you should not depend on this behaviour because it can
-- change in the future without notice.
splitRoot :: IntMap a -> [IntMap a]
-- | O(n+m). Is this a submap? Defined as (isSubmapOf =
-- isSubmapOfBy (==)).
isSubmapOf :: Eq a => IntMap a -> IntMap a -> Bool
-- | O(n+m). The expression (isSubmapOfBy f m1 m2)
-- returns True if all keys in m1 are in m2, and
-- when f returns True when applied to their respective
-- values. For example, the following expressions are all 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)])
--
--
-- But the following are all 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)])
--
isSubmapOfBy :: (a -> b -> Bool) -> IntMap a -> IntMap b -> Bool
-- | O(n+m). Is this a proper submap? (ie. a submap but not equal).
-- Defined as (isProperSubmapOf = isProperSubmapOfBy
-- (==)).
isProperSubmapOf :: Eq a => IntMap a -> IntMap a -> Bool
-- | O(n+m). Is this a proper submap? (ie. a submap but not equal).
-- The expression (isProperSubmapOfBy f m1 m2) returns
-- True when m1 and m2 are not equal, all keys
-- in m1 are in m2, and when f returns
-- True when applied to their respective values. For example, the
-- following expressions are all True:
--
--
-- isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
-- isProperSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
--
--
-- But the following are all 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)])
--
isProperSubmapOfBy :: (a -> b -> Bool) -> IntMap a -> IntMap b -> Bool
-- | O(min(n,W)). The minimal key of the map.
findMin :: IntMap a -> (Key, a)
-- | O(min(n,W)). The maximal key of the map.
findMax :: IntMap a -> (Key, a)
-- | O(min(n,W)). Delete the minimal key. Returns an empty map if
-- the map is empty.
--
-- Note that this is a change of behaviour for consistency with
-- Map – versions prior to 0.5 threw an error if the IntMap
-- was already empty.
deleteMin :: IntMap a -> IntMap a
-- | O(min(n,W)). Delete the maximal key. Returns an empty map if
-- the map is empty.
--
-- Note that this is a change of behaviour for consistency with
-- Map – versions prior to 0.5 threw an error if the IntMap
-- was already empty.
deleteMax :: IntMap a -> IntMap a
-- | O(min(n,W)). Delete and find the minimal element.
deleteFindMin :: IntMap a -> ((Key, a), IntMap a)
-- | O(min(n,W)). Delete and find the maximal element.
deleteFindMax :: IntMap a -> ((Key, a), IntMap a)
-- | O(min(n,W)). Update the value at the minimal key.
--
--
-- 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"
--
updateMin :: (a -> Maybe a) -> IntMap a -> IntMap a
-- | O(min(n,W)). Update the value at the maximal key.
--
--
-- 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"
--
updateMax :: (a -> Maybe a) -> IntMap a -> IntMap a
-- | O(min(n,W)). Update the value at the minimal key.
--
--
-- 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"
--
updateMinWithKey :: (Key -> a -> Maybe a) -> IntMap a -> IntMap a
-- | O(min(n,W)). Update the value at the maximal key.
--
--
-- 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"
--
updateMaxWithKey :: (Key -> a -> Maybe a) -> IntMap a -> IntMap a
-- | O(min(n,W)). Retrieves the minimal key of the map, and the map
-- stripped of that element, or Nothing if passed an empty map.
minView :: IntMap a -> Maybe (a, IntMap a)
-- | O(min(n,W)). Retrieves the maximal key of the map, and the map
-- stripped of that element, or Nothing if passed an empty map.
maxView :: IntMap a -> Maybe (a, IntMap a)
-- | O(min(n,W)). Retrieves the minimal (key,value) pair of the map,
-- and the map stripped of that element, or Nothing if passed an
-- empty map.
--
--
-- minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
-- minViewWithKey empty == Nothing
--
minViewWithKey :: IntMap a -> Maybe ((Key, a), IntMap a)
-- | O(min(n,W)). Retrieves the maximal (key,value) pair of the map,
-- and the map stripped of that element, or Nothing if passed an
-- empty map.
--
--
-- maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b")
-- maxViewWithKey empty == Nothing
--
maxViewWithKey :: IntMap a -> Maybe ((Key, a), IntMap a)
-- | O(n). Show the tree that implements the map. The tree is shown
-- in a compressed, hanging format.
showTree :: Show a => IntMap a -> String
-- | O(n). The expression (showTreeWith hang wide
-- map) shows the tree that implements the map. If hang is
-- True, a hanging tree is shown otherwise a rotated tree
-- is shown. If wide is True, an extra wide version is
-- shown.
showTreeWith :: Show a => Bool -> Bool -> IntMap a -> String
-- | An efficient implementation of maps from integer keys to values
-- (dictionaries).
--
-- API of this module is strict in both the keys and the values. If you
-- need value-lazy maps, use Data.IntMap.Lazy instead. The
-- IntMap type itself is shared between the lazy and strict
-- modules, meaning that the same IntMap value can be passed to
-- functions in both modules (although that is rarely needed).
--
-- These modules are intended to be imported qualified, to avoid name
-- clashes with Prelude functions, e.g.
--
--
-- import Data.IntMap.Strict (IntMap)
-- import qualified Data.IntMap.Strict as IntMap
--
--
-- The implementation is based on big-endian patricia trees. This
-- data structure performs especially well on binary operations like
-- union and intersection. However, my benchmarks show that
-- it is also (much) faster on insertions and deletions when compared to
-- a generic size-balanced map implementation (see Data.Map).
--
--
-- - Chris Okasaki and Andy Gill, "Fast Mergeable Integer Maps",
-- Workshop on ML, September 1998, pages 77-86,
-- http://citeseer.ist.psu.edu/okasaki98fast.html
-- - D.R. Morrison, "/PATRICIA -- Practical Algorithm To Retrieve
-- Information Coded In Alphanumeric/", Journal of the ACM, 15(4),
-- October 1968, pages 514-534.
--
--
-- Operation comments contain the operation time complexity in the Big-O
-- notation http://en.wikipedia.org/wiki/Big_O_notation. Many
-- operations have a worst-case complexity of O(min(n,W)). This
-- means that the operation can become linear in the number of elements
-- with a maximum of W -- the number of bits in an Int (32
-- or 64).
--
-- Be aware that the Functor, Traversable and Data
-- instances are the same as for the Data.IntMap.Lazy module, so
-- if they are used on strict maps, the resulting maps will be lazy.
module Data.IntMap.Strict
-- | A map of integers to values a.
data IntMap a
type Key = Int
-- | O(min(n,W)). Find the value at a key. Calls error when
-- the element can not be found.
--
--
-- fromList [(5,'a'), (3,'b')] ! 1 Error: element not in the map
-- fromList [(5,'a'), (3,'b')] ! 5 == 'a'
--
(!) :: IntMap a -> Key -> a
-- | Same as difference.
(\\) :: IntMap a -> IntMap b -> IntMap a
infixl 9 \\
-- | O(1). Is the map empty?
--
--
-- Data.IntMap.null (empty) == True
-- Data.IntMap.null (singleton 1 'a') == False
--
null :: IntMap a -> Bool
-- | O(n). Number of elements in the map.
--
--
-- size empty == 0
-- size (singleton 1 'a') == 1
-- size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3
--
size :: IntMap a -> Int
-- | O(min(n,W)). Is the key a member of the map?
--
--
-- member 5 (fromList [(5,'a'), (3,'b')]) == True
-- member 1 (fromList [(5,'a'), (3,'b')]) == False
--
member :: Key -> IntMap a -> Bool
-- | O(min(n,W)). Is the key not a member of the map?
--
--
-- notMember 5 (fromList [(5,'a'), (3,'b')]) == False
-- notMember 1 (fromList [(5,'a'), (3,'b')]) == True
--
notMember :: Key -> IntMap a -> Bool
-- | O(min(n,W)). Lookup the value at a key in the map. See also
-- lookup.
lookup :: Key -> IntMap a -> Maybe a
-- | O(min(n,W)). The expression (findWithDefault def k
-- map) returns the value at key k or returns def
-- when the key is not an element of the map.
--
--
-- findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
-- findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
--
findWithDefault :: a -> Key -> IntMap a -> a
-- | O(log n). Find largest key smaller than the given one and
-- return the corresponding (key, value) pair.
--
--
-- lookupLT 3 (fromList [(3,'a'), (5,'b')]) == Nothing
-- lookupLT 4 (fromList [(3,'a'), (5,'b')]) == Just (3, 'a')
--
lookupLT :: Key -> IntMap a -> Maybe (Key, a)
-- | O(log n). Find smallest key greater than the given one and
-- return the corresponding (key, value) pair.
--
--
-- lookupGT 4 (fromList [(3,'a'), (5,'b')]) == Just (5, 'b')
-- lookupGT 5 (fromList [(3,'a'), (5,'b')]) == Nothing
--
lookupGT :: Key -> IntMap a -> Maybe (Key, a)
-- | O(log n). Find largest key smaller or equal to the given one
-- and return the corresponding (key, value) pair.
--
--
-- 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')
--
lookupLE :: Key -> IntMap a -> Maybe (Key, a)
-- | O(log n). Find smallest key greater or equal to the given one
-- and return the corresponding (key, value) pair.
--
--
-- 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
--
lookupGE :: Key -> IntMap a -> Maybe (Key, a)
-- | O(1). The empty map.
--
--
-- empty == fromList []
-- size empty == 0
--
empty :: IntMap a
-- | O(1). A map of one element.
--
--
-- singleton 1 'a' == fromList [(1, 'a')]
-- size (singleton 1 'a') == 1
--
singleton :: Key -> a -> IntMap a
-- | O(min(n,W)). Insert a new key/value pair in the map. If the key
-- is already present in the map, the associated value is replaced with
-- the supplied value, i.e. insert is equivalent to
-- 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'
--
insert :: Key -> a -> IntMap a -> IntMap a
-- | O(min(n,W)). Insert with a combining function.
-- insertWith f key value mp will insert the pair (key,
-- value) into mp if key does not exist in the map. If the key
-- does exist, the function will insert 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"
--
insertWith :: (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
-- | O(min(n,W)). Insert with a combining function.
-- insertWithKey f key value mp will insert the pair
-- (key, value) into mp if key does not exist in the map. If the
-- key does exist, the function will insert 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"
--
--
-- If the key exists in the map, this function is lazy in x but
-- strict in the result of f.
insertWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
-- | O(min(n,W)). The expression (insertLookupWithKey f k
-- x map) is a pair where the first element is equal to
-- (lookup k map) and the second element equal to
-- (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")
--
--
-- This is how to define insertLookup using
-- 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")])
--
insertLookupWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> (Maybe a, IntMap a)
-- | O(min(n,W)). Delete a key and its value from the map. When the
-- key is not a member of the map, the original map is returned.
--
--
-- 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
--
delete :: Key -> IntMap a -> IntMap a
-- | O(min(n,W)). Adjust a value at a specific key. When the key is
-- not a member of the map, the original map is returned.
--
--
-- 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
--
adjust :: (a -> a) -> Key -> IntMap a -> IntMap a
-- | O(min(n,W)). Adjust a value at a specific key. When the key is
-- not a member of the map, the original map is returned.
--
--
-- 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
--
adjustWithKey :: (Key -> a -> a) -> Key -> IntMap a -> IntMap a
-- | O(min(n,W)). The expression (update f k map)
-- updates the value x at k (if it is in the map). If
-- (f x) is Nothing, the element is deleted. If it is
-- (Just y), the key k is bound to the new value
-- 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"
--
update :: (a -> Maybe a) -> Key -> IntMap a -> IntMap a
-- | O(min(n,W)). The expression (update f k map)
-- updates the value x at k (if it is in the map). If
-- (f k x) is Nothing, the element is deleted. If it is
-- (Just y), the key k is bound to the new value
-- 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"
--
updateWithKey :: (Key -> a -> Maybe a) -> Key -> IntMap a -> IntMap a
-- | O(min(n,W)). Lookup and update. The function returns original
-- value, if it is updated. This is different behavior than
-- updateLookupWithKey. Returns the original key value if the map
-- entry is deleted.
--
--
-- 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")
--
updateLookupWithKey :: (Key -> a -> Maybe a) -> Key -> IntMap a -> (Maybe a, IntMap a)
-- | O(min(n,W)). The expression (alter f k map)
-- alters the value x at k, or absence thereof.
-- alter can be used to insert, delete, or update a value in an
-- IntMap. In short : lookup k (alter f k m) = f
-- (lookup k m).
alter :: (Maybe a -> Maybe a) -> Key -> IntMap a -> IntMap a
-- | O(log n). The expression (alterF f k map)
-- alters the value x at k, or absence thereof.
-- alterF can be used to inspect, insert, delete, or update a
-- value in an IntMap. In short : lookup k $
-- alterF f k m = f (lookup k m).
--
-- Example:
--
--
-- interactiveAlter :: Int -> IntMap String -> IO (IntMap String)
-- interactiveAlter k m = alterF f k m where
-- f Nothing -> do
-- putStrLn $ show k ++
-- " was not found in the map. Would you like to add it?"
-- getUserResponse1 :: IO (Maybe String)
-- f (Just old) -> do
-- putStrLn "The key is currently bound to " ++ show old ++
-- ". Would you like to change or delete it?"
-- getUserresponse2 :: IO (Maybe String)
--
--
-- alterF is the most general operation for working with an
-- individual key that may or may not be in a given map.
alterF :: Functor f => (Maybe a -> f (Maybe a)) -> Key -> IntMap a -> f (IntMap a)
-- | O(n+m). The (left-biased) union of two maps. It prefers the
-- first map when duplicate keys are encountered, i.e. (union
-- == unionWith const).
--
--
-- union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
--
union :: IntMap a -> IntMap a -> IntMap a
-- | O(n+m). The union with a combining function.
--
--
-- unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
--
unionWith :: (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
-- | O(n+m). The union with a combining function.
--
--
-- 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")]
--
unionWithKey :: (Key -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
-- | The union of a list of maps.
--
--
-- 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")]
--
unions :: [IntMap a] -> IntMap a
-- | The union of a list of maps, with a combining operation.
--
--
-- unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
-- == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
--
unionsWith :: (a -> a -> a) -> [IntMap a] -> IntMap a
-- | O(n+m). Difference between two maps (based on keys).
--
--
-- difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"
--
difference :: IntMap a -> IntMap b -> IntMap a
-- | O(n+m). Difference with a combining function.
--
--
-- 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"
--
differenceWith :: (a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
-- | O(n+m). Difference with a combining function. When two equal
-- keys are encountered, the combining function is applied to the key and
-- both values. If it returns Nothing, the element is discarded
-- (proper set difference). If it returns (Just y), the
-- element is updated with a new value 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"
--
differenceWithKey :: (Key -> a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
-- | O(n+m). The (left-biased) intersection of two maps (based on
-- keys).
--
--
-- intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a"
--
intersection :: IntMap a -> IntMap b -> IntMap a
-- | O(n+m). The intersection with a combining function.
--
--
-- intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA"
--
intersectionWith :: (a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
-- | O(n+m). The intersection with a combining function.
--
--
-- 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"
--
intersectionWithKey :: (Key -> a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
-- | O(n+m). A high-performance universal combining function. Using
-- mergeWithKey, all combining functions can be defined without
-- any loss of efficiency (with exception of union,
-- difference and intersection, where sharing of some nodes
-- is lost with mergeWithKey).
--
-- Please make sure you know what is going on when using
-- mergeWithKey, otherwise you can be surprised by unexpected code
-- growth or even corruption of the data structure.
--
-- When mergeWithKey is given three arguments, it is inlined to
-- the call site. You should therefore use mergeWithKey only to
-- define your custom combining functions. For example, you could define
-- unionWithKey, differenceWithKey and
-- intersectionWithKey as
--
--
-- 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
--
--
-- When calling mergeWithKey combine only1 only2, a
-- function combining two IntMaps is created, such that
--
--
-- - if a key is present in both maps, it is passed with both
-- corresponding values to the combine function. Depending on
-- the result, the key is either present in the result with specified
-- value, or is left out;
-- - a nonempty subtree present only in the first map is passed to
-- only1 and the output is added to the result;
-- - a nonempty subtree present only in the second map is passed to
-- only2 and the output is added to the result.
--
--
-- The only1 and only2 methods must return a map
-- with a subset (possibly empty) of the keys of the given map. The
-- values can be modified arbitrarily. Most common variants of
-- only1 and only2 are id and const
-- empty, but for example map f or
-- filterWithKey f could be used for any f.
mergeWithKey :: (Key -> a -> b -> Maybe c) -> (IntMap a -> IntMap c) -> (IntMap b -> IntMap c) -> IntMap a -> IntMap b -> IntMap c
-- | O(n). Map a function over all values in the map.
--
--
-- map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
--
map :: (a -> b) -> IntMap a -> IntMap b
-- | O(n). Map a function over all values in the map.
--
--
-- let f key x = (show key) ++ ":" ++ x
-- mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]
--
mapWithKey :: (Key -> a -> b) -> IntMap a -> IntMap b
-- | O(n). traverseWithKey f s == fromList
-- $ traverse ((k, v) -> (,) k $ f k v)
-- (toList m) That is, behaves exactly like a regular
-- traverse except that the traversing function also has access to
-- the key associated with a value.
--
--
-- 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
--
traverseWithKey :: Applicative t => (Key -> a -> t b) -> IntMap a -> t (IntMap b)
-- | O(n). The function mapAccum threads an
-- accumulating argument through the map in ascending order of keys.
--
--
-- let f a b = (a ++ b, b ++ "X")
-- mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
--
mapAccum :: (a -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
-- | 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")])
--
mapAccumWithKey :: (a -> Key -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
-- | O(n). The function mapAccumR threads an
-- accumulating argument through the map in descending order of keys.
mapAccumRWithKey :: (a -> Key -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
-- | O(n*min(n,W)). mapKeys f s is the map obtained
-- by applying f to each key of s.
--
-- The size of the result may be smaller if f maps two or more
-- distinct keys to the same new key. In this case the value at the
-- greatest of the original keys is retained.
--
--
-- 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"
--
mapKeys :: (Key -> Key) -> IntMap a -> IntMap a
-- | O(n*log n). mapKeysWith c f s is the map
-- obtained by applying f to each key of s.
--
-- The size of the result may be smaller if f maps two or more
-- distinct keys to the same new key. In this case the associated values
-- will be combined using 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"
--
mapKeysWith :: (a -> a -> a) -> (Key -> Key) -> IntMap a -> IntMap a
-- | O(n*min(n,W)). mapKeysMonotonic f s ==
-- mapKeys f s, but works only when f is strictly
-- monotonic. That is, for any values x and y, if
-- x < y then f x < f y. The
-- precondition is not checked. Semi-formally, we have:
--
--
-- and [x < y ==> f x < f y | x <- ls, y <- ls]
-- ==> mapKeysMonotonic f s == mapKeys f s
-- where ls = keys s
--
--
-- This means that f maps distinct original keys to distinct
-- resulting keys. This function has slightly better performance than
-- mapKeys.
--
--
-- mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
--
mapKeysMonotonic :: (Key -> Key) -> IntMap a -> IntMap a
-- | O(n). Fold the values in the map using the given
-- right-associative binary operator, such that foldr f z ==
-- foldr f z . elems.
--
-- For example,
--
--
-- elems map = foldr (:) [] map
--
--
--
-- let f a len = len + (length a)
-- foldr f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
--
foldr :: (a -> b -> b) -> b -> IntMap a -> b
-- | O(n). Fold the values in the map using the given
-- left-associative binary operator, such that foldl f z ==
-- foldl f z . elems.
--
-- For example,
--
--
-- elems = reverse . foldl (flip (:)) []
--
--
--
-- let f len a = len + (length a)
-- foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
--
foldl :: (a -> b -> a) -> a -> IntMap b -> a
-- | O(n). Fold the keys and values in the map using the given
-- right-associative binary operator, such that foldrWithKey f
-- z == foldr (uncurry f) z . toAscList.
--
-- For example,
--
--
-- 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)"
--
foldrWithKey :: (Key -> a -> b -> b) -> b -> IntMap a -> b
-- | O(n). Fold the keys and values in the map using the given
-- left-associative binary operator, such that foldlWithKey f
-- z == foldl (\z' (kx, x) -> f z' kx x) z .
-- toAscList.
--
-- For example,
--
--
-- 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)"
--
foldlWithKey :: (a -> Key -> b -> a) -> a -> IntMap b -> a
-- | O(n). Fold the keys and values in the map using the given
-- monoid, such that
--
--
-- foldMapWithKey f = fold . mapWithKey f
--
--
-- This can be an asymptotically faster than foldrWithKey or
-- foldlWithKey for some monoids.
foldMapWithKey :: Monoid m => (Key -> a -> m) -> IntMap a -> m
-- | O(n). A strict version of foldr. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> IntMap a -> b
-- | O(n). A strict version of foldl. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldl' :: (a -> b -> a) -> a -> IntMap b -> a
-- | O(n). A strict version of foldrWithKey. Each application
-- of the operator is evaluated before using the result in the next
-- application. This function is strict in the starting value.
foldrWithKey' :: (Key -> a -> b -> b) -> b -> IntMap a -> b
-- | O(n). A strict version of foldlWithKey. Each application
-- of the operator is evaluated before using the result in the next
-- application. This function is strict in the starting value.
foldlWithKey' :: (a -> Key -> b -> a) -> a -> IntMap b -> a
-- | O(n). Return all elements of the map in the ascending order of
-- their keys. Subject to list fusion.
--
--
-- elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]
-- elems empty == []
--
elems :: IntMap a -> [a]
-- | O(n). Return all keys of the map in ascending order. Subject to
-- list fusion.
--
--
-- keys (fromList [(5,"a"), (3,"b")]) == [3,5]
-- keys empty == []
--
keys :: IntMap a -> [Key]
-- | O(n). An alias for toAscList. Returns all key/value
-- pairs in the map in ascending key order. Subject to list fusion.
--
--
-- assocs (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
-- assocs empty == []
--
assocs :: IntMap a -> [(Key, a)]
-- | O(n*min(n,W)). The set of all keys of the map.
--
--
-- keysSet (fromList [(5,"a"), (3,"b")]) == Data.IntSet.fromList [3,5]
-- keysSet empty == Data.IntSet.empty
--
keysSet :: IntMap a -> IntSet
-- | O(n). Build a map from a set of keys and a function which for
-- each key computes its value.
--
--
-- fromSet (\k -> replicate k 'a') (Data.IntSet.fromList [3, 5]) == fromList [(5,"aaaaa"), (3,"aaa")]
-- fromSet undefined Data.IntSet.empty == empty
--
fromSet :: (Key -> a) -> IntSet -> IntMap a
-- | O(n). Convert the map to a list of key/value pairs. Subject to
-- list fusion.
--
--
-- toList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
-- toList empty == []
--
toList :: IntMap a -> [(Key, a)]
-- | O(n*min(n,W)). Create a map from a list of key/value pairs.
--
--
-- 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")]
--
fromList :: [(Key, a)] -> IntMap a
-- | O(n*min(n,W)). Create a map from a list of key/value pairs with
-- a combining function. See also fromAscListWith.
--
--
-- fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
-- fromListWith (++) [] == empty
--
fromListWith :: (a -> a -> a) -> [(Key, a)] -> IntMap a
-- | O(n*min(n,W)). Build a map from a list of key/value pairs with
-- a combining function. See also fromAscListWithKey'.
--
--
-- 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
-- | O(n). Convert the map to a list of key/value pairs where the
-- keys are in ascending order. Subject to list fusion.
--
--
-- toAscList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
--
toAscList :: IntMap a -> [(Key, a)]
-- | O(n). Convert the map to a list of key/value pairs where the
-- keys are in descending order. Subject to list fusion.
--
--
-- toDescList (fromList [(5,"a"), (3,"b")]) == [(5,"a"), (3,"b")]
--
toDescList :: IntMap a -> [(Key, a)]
-- | O(n). Build a map from a list of key/value pairs where the keys
-- are in ascending order.
--
--
-- fromAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
-- fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")]
--
fromAscList :: [(Key, a)] -> IntMap a
-- | O(n). Build a map from a list of key/value pairs where the keys
-- are in ascending order, with a combining function on equal keys.
-- The precondition (input list is ascending) is not checked.
--
--
-- fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
--
fromAscListWith :: (a -> a -> a) -> [(Key, a)] -> IntMap a
-- | O(n). Build a map from a list of key/value pairs where the keys
-- are in ascending order, with a combining function on equal keys.
-- The precondition (input list is ascending) is not checked.
--
--
-- fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
--
fromAscListWithKey :: (Key -> a -> a -> a) -> [(Key, a)] -> IntMap a
-- | O(n). Build a map from a list of key/value pairs where the keys
-- are in ascending order and all distinct. The precondition (input
-- list is strictly ascending) is not checked.
--
--
-- fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
--
fromDistinctAscList :: [(Key, a)] -> IntMap a
-- | O(n). Filter all values that satisfy some predicate.
--
--
-- 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
--
filter :: (a -> Bool) -> IntMap a -> IntMap a
-- | O(n). Filter all keys/values that satisfy some predicate.
--
--
-- filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--
filterWithKey :: (Key -> a -> Bool) -> IntMap a -> IntMap a
-- | O(n+m). The restriction of a map to the keys in a set.
--
--
-- m restrictKeys s = filterWithKey (k _ -> k `member' s) m
--
restrictKeys :: IntMap a -> IntSet -> IntMap a
-- | Remove all the keys in a given set from a map.
--
--
-- m withoutKeys s = filterWithKey (k _ -> k `notMember' s) m
--
withoutKeys :: IntMap a -> IntSet -> IntMap a
-- | O(n). Partition the map according to some predicate. The first
-- map contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate. See also 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")])
--
partition :: (a -> Bool) -> IntMap a -> (IntMap a, IntMap a)
-- | O(n). Partition the map according to some predicate. The first
-- map contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate. See also 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")])
--
partitionWithKey :: (Key -> a -> Bool) -> IntMap a -> (IntMap a, IntMap a)
-- | O(n). Map values and collect the Just results.
--
--
-- let f x = if x == "a" then Just "new a" else Nothing
-- mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"
--
mapMaybe :: (a -> Maybe b) -> IntMap a -> IntMap b
-- | O(n). Map keys/values and collect the Just results.
--
--
-- let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing
-- mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"
--
mapMaybeWithKey :: (Key -> a -> Maybe b) -> IntMap a -> IntMap b
-- | O(n). Map values and separate the Left and Right
-- results.
--
--
-- 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")])
--
mapEither :: (a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)
-- | O(n). Map keys/values and separate the Left and
-- Right results.
--
--
-- 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")])
--
mapEitherWithKey :: (Key -> a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)
-- | O(min(n,W)). The expression (split k map) is a
-- pair (map1,map2) where all keys in map1 are lower
-- than k and all keys in map2 larger than k.
-- Any key equal to k is found in neither map1 nor
-- 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)
--
split :: Key -> IntMap a -> (IntMap a, IntMap a)
-- | O(min(n,W)). Performs a split but also returns whether
-- the pivot key was found in the original 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)
--
splitLookup :: Key -> IntMap a -> (IntMap a, Maybe a, IntMap a)
-- | O(1). Decompose a map into pieces based on the structure of the
-- underlying tree. This function is useful for consuming a map in
-- parallel.
--
-- No guarantee is made as to the sizes of the pieces; an internal, but
-- deterministic process determines this. However, it is guaranteed that
-- the pieces returned will be in ascending order (all elements in the
-- first submap less than all elements in the second, and so on).
--
-- Examples:
--
--
-- splitRoot (fromList (zip [1..6::Int] ['a'..])) ==
-- [fromList [(1,'a'),(2,'b'),(3,'c')],fromList [(4,'d'),(5,'e'),(6,'f')]]
--
--
--
-- splitRoot empty == []
--
--
-- Note that the current implementation does not return more than two
-- submaps, but you should not depend on this behaviour because it can
-- change in the future without notice.
splitRoot :: IntMap a -> [IntMap a]
-- | O(n+m). Is this a submap? Defined as (isSubmapOf =
-- isSubmapOfBy (==)).
isSubmapOf :: Eq a => IntMap a -> IntMap a -> Bool
-- | O(n+m). The expression (isSubmapOfBy f m1 m2)
-- returns True if all keys in m1 are in m2, and
-- when f returns True when applied to their respective
-- values. For example, the following expressions are all 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)])
--
--
-- But the following are all 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)])
--
isSubmapOfBy :: (a -> b -> Bool) -> IntMap a -> IntMap b -> Bool
-- | O(n+m). Is this a proper submap? (ie. a submap but not equal).
-- Defined as (isProperSubmapOf = isProperSubmapOfBy
-- (==)).
isProperSubmapOf :: Eq a => IntMap a -> IntMap a -> Bool
-- | O(n+m). Is this a proper submap? (ie. a submap but not equal).
-- The expression (isProperSubmapOfBy f m1 m2) returns
-- True when m1 and m2 are not equal, all keys
-- in m1 are in m2, and when f returns
-- True when applied to their respective values. For example, the
-- following expressions are all True:
--
--
-- isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
-- isProperSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
--
--
-- But the following are all 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)])
--
isProperSubmapOfBy :: (a -> b -> Bool) -> IntMap a -> IntMap b -> Bool
-- | O(min(n,W)). The minimal key of the map.
findMin :: IntMap a -> (Key, a)
-- | O(min(n,W)). The maximal key of the map.
findMax :: IntMap a -> (Key, a)
-- | O(min(n,W)). Delete the minimal key. Returns an empty map if
-- the map is empty.
--
-- Note that this is a change of behaviour for consistency with
-- Map – versions prior to 0.5 threw an error if the IntMap
-- was already empty.
deleteMin :: IntMap a -> IntMap a
-- | O(min(n,W)). Delete the maximal key. Returns an empty map if
-- the map is empty.
--
-- Note that this is a change of behaviour for consistency with
-- Map – versions prior to 0.5 threw an error if the IntMap
-- was already empty.
deleteMax :: IntMap a -> IntMap a
-- | O(min(n,W)). Delete and find the minimal element.
deleteFindMin :: IntMap a -> ((Key, a), IntMap a)
-- | O(min(n,W)). Delete and find the maximal element.
deleteFindMax :: IntMap a -> ((Key, a), IntMap a)
-- | O(log n). Update the value at the minimal key.
--
--
-- 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"
--
updateMin :: (a -> Maybe a) -> IntMap a -> IntMap a
-- | O(log n). Update the value at the maximal key.
--
--
-- 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"
--
updateMax :: (a -> Maybe a) -> IntMap a -> IntMap a
-- | O(log n). Update the value at the minimal key.
--
--
-- 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"
--
updateMinWithKey :: (Key -> a -> Maybe a) -> IntMap a -> IntMap a
-- | O(log n). Update the value at the maximal key.
--
--
-- 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"
--
updateMaxWithKey :: (Key -> a -> Maybe a) -> IntMap a -> IntMap a
-- | O(min(n,W)). Retrieves the minimal key of the map, and the map
-- stripped of that element, or Nothing if passed an empty map.
minView :: IntMap a -> Maybe (a, IntMap a)
-- | O(min(n,W)). Retrieves the maximal key of the map, and the map
-- stripped of that element, or Nothing if passed an empty map.
maxView :: IntMap a -> Maybe (a, IntMap a)
-- | O(min(n,W)). Retrieves the minimal (key,value) pair of the map,
-- and the map stripped of that element, or Nothing if passed an
-- empty map.
--
--
-- minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
-- minViewWithKey empty == Nothing
--
minViewWithKey :: IntMap a -> Maybe ((Key, a), IntMap a)
-- | O(min(n,W)). Retrieves the maximal (key,value) pair of the map,
-- and the map stripped of that element, or Nothing if passed an
-- empty map.
--
--
-- maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b")
-- maxViewWithKey empty == Nothing
--
maxViewWithKey :: IntMap a -> Maybe ((Key, a), IntMap a)
-- | O(n). Show the tree that implements the map. The tree is shown
-- in a compressed, hanging format.
showTree :: Show a => IntMap a -> String
-- | O(n). The expression (showTreeWith hang wide
-- map) shows the tree that implements the map. If hang is
-- True, a hanging tree is shown otherwise a rotated tree
-- is shown. If wide is True, an extra wide version is
-- shown.
showTreeWith :: Show a => Bool -> Bool -> IntMap a -> String
-- | An efficient implementation of maps from integer keys to values
-- (dictionaries).
--
-- This module re-exports the value lazy Data.IntMap.Lazy API,
-- plus several deprecated value strict functions. Please note that these
-- functions have different strictness properties than those in
-- Data.IntMap.Strict: they only evaluate the result of the
-- combining function. For example, the default value to
-- insertWith' is only evaluated if the combining function is
-- called and uses it.
--
-- These modules are intended to be imported qualified, to avoid name
-- clashes with Prelude functions, e.g.
--
--
-- import Data.IntMap (IntMap)
-- import qualified Data.IntMap as IntMap
--
--
-- The implementation is based on big-endian patricia trees. This
-- data structure performs especially well on binary operations like
-- union and intersection. However, my benchmarks show that
-- it is also (much) faster on insertions and deletions when compared to
-- a generic size-balanced map implementation (see Data.Map).
--
--
-- - Chris Okasaki and Andy Gill, "Fast Mergeable Integer Maps",
-- Workshop on ML, September 1998, pages 77-86,
-- http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452
-- - D.R. Morrison, "/PATRICIA -- Practical Algorithm To Retrieve
-- Information Coded In Alphanumeric/", Journal of the ACM, 15(4),
-- October 1968, pages 514-534.
--
--
-- Operation comments contain the operation time complexity in the Big-O
-- notation http://en.wikipedia.org/wiki/Big_O_notation. Many
-- operations have a worst-case complexity of O(min(n,W)). This
-- means that the operation can become linear in the number of elements
-- with a maximum of W -- the number of bits in an Int
-- (32 or 64).
module Data.IntMap
-- | Deprecated. As of version 0.5, replaced by insertWith.
--
-- O(log n). Same as insertWith, but the result of the
-- combining function is evaluated to WHNF before inserted to the map.
insertWith' :: (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
-- | Deprecated. As of version 0.5, replaced by
-- insertWithKey.
--
-- O(log n). Same as insertWithKey, but the result of the
-- combining function is evaluated to WHNF before inserted to the map.
insertWithKey' :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
-- | Deprecated. As of version 0.5, replaced by foldr.
--
-- O(n). Fold the values in the map using the given
-- right-associative binary operator. This function is an equivalent of
-- foldr and is present for compatibility only.
fold :: (a -> b -> b) -> b -> IntMap a -> b
-- | Deprecated. As of version 0.5, replaced by foldrWithKey.
--
-- O(n). Fold the keys and values in the map using the given
-- right-associative binary operator. This function is an equivalent of
-- foldrWithKey and is present for compatibility only.
foldWithKey :: (Key -> a -> b -> b) -> b -> IntMap a -> b
-- | A version of the graph algorithms described in:
--
-- Structuring Depth-First Search Algorithms in Haskell, by David
-- King and John Launchbury.
module Data.Graph
-- | The strongly connected components of a directed graph, topologically
-- sorted.
stronglyConnComp :: Ord key => [(node, key, [key])] -> [SCC node]
-- | The strongly connected components of a directed graph, topologically
-- sorted. The function is the same as stronglyConnComp, except
-- that all the information about each node retained. This interface is
-- used when you expect to apply SCC to (some of) the result of
-- SCC, so you don't want to lose the dependency information.
stronglyConnCompR :: Ord key => [(node, key, [key])] -> [SCC (node, key, [key])]
-- | Strongly connected component.
data SCC vertex
-- | A single vertex that is not in any cycle.
AcyclicSCC :: vertex -> SCC vertex
-- | A maximal set of mutually reachable vertices.
CyclicSCC :: [vertex] -> SCC vertex
-- | The vertices of a strongly connected component.
flattenSCC :: SCC vertex -> [vertex]
-- | The vertices of a list of strongly connected components.
flattenSCCs :: [SCC a] -> [a]
-- | Adjacency list representation of a graph, mapping each vertex to its
-- list of successors.
type Graph = Table [Vertex]
-- | Table indexed by a contiguous set of vertices.
type Table a = Array Vertex a
-- | The bounds of a Table.
type Bounds = (Vertex, Vertex)
-- | An edge from the first vertex to the second.
type Edge = (Vertex, Vertex)
-- | Abstract representation of vertices.
type Vertex = Int
-- | Build a graph from a list of nodes uniquely identified by keys, with a
-- list of keys of nodes this node should have edges to. The out-list may
-- contain keys that don't correspond to nodes of the graph; they are
-- ignored.
graphFromEdges :: Ord key => [(node, key, [key])] -> (Graph, Vertex -> (node, key, [key]), key -> Maybe Vertex)
-- | Identical to graphFromEdges, except that the return value does
-- not include the function which maps keys to vertices. This version of
-- graphFromEdges is for backwards compatibility.
graphFromEdges' :: Ord key => [(node, key, [key])] -> (Graph, Vertex -> (node, key, [key]))
-- | Build a graph from a list of edges.
buildG :: Bounds -> [Edge] -> Graph
-- | The graph obtained by reversing all edges.
transposeG :: Graph -> Graph
-- | All vertices of a graph.
vertices :: Graph -> [Vertex]
-- | All edges of a graph.
edges :: Graph -> [Edge]
-- | A table of the count of edges from each node.
outdegree :: Graph -> Table Int
-- | A table of the count of edges into each node.
indegree :: Graph -> Table Int
-- | A spanning forest of the part of the graph reachable from the listed
-- vertices, obtained from a depth-first search of the graph starting at
-- each of the listed vertices in order.
dfs :: Graph -> [Vertex] -> Forest Vertex
-- | A spanning forest of the graph, obtained from a depth-first search of
-- the graph starting from each vertex in an unspecified order.
dff :: Graph -> Forest Vertex
-- | A topological sort of the graph. The order is partially specified by
-- the condition that a vertex i precedes j whenever
-- j is reachable from i but not vice versa.
topSort :: Graph -> [Vertex]
-- | The connected components of a graph. Two vertices are connected if
-- there is a path between them, traversing edges in either direction.
components :: Graph -> Forest Vertex
-- | The strongly connected components of a graph.
scc :: Graph -> Forest Vertex
-- | The biconnected components of a graph. An undirected graph is
-- biconnected if the deletion of any vertex leaves it connected.
bcc :: Graph -> Forest [Vertex]
-- | A list of vertices reachable from a given vertex.
reachable :: Graph -> Vertex -> [Vertex]
-- | Is the second vertex reachable from the first?
path :: Graph -> Vertex -> Vertex -> Bool
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Graph.SCC a)
instance GHC.Base.Functor Data.Graph.SCC
instance GHC.Base.Monad (Data.Graph.SetM s)
instance GHC.Base.Functor (Data.Graph.SetM s)
instance GHC.Base.Applicative (Data.Graph.SetM s)