Allows us to abstract over value-strictness in a zero-cost manner. GHC should always be able to specialise the two instances of this and consequently inline areWeStrict.

It's a little sad we can't just use regular singletons, for reasons outlined here.

Should be inlined and specialised at all call sites.

A map from partially-ordered keys k to values v.

Internal smart constructor so that we can be sure that we are always spine-strict, discard empty maps and have appropriate size information.

\(\mathcal{O}(1)\). The number of elements in this map.

\(\mathcal{O}(w)\). The width \(w\) of the chain decomposition in the internal data structure. This is always at least as big as the size of the biggest possible anti-chain.

\(\mathcal{O}(w\log n)\). Is the key a member of the map?

\(\mathcal{O}(w\log n)\). Is the key a member of the map? See also notMember.

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

\(\mathcal{O}(w\log n)\). Is the key not a member of the map? See also member.

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

\(\mathcal{O}(w\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'
True
>>> findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
True

\(\mathcal{O}(w\log n)\). Find the largest set of keys smaller than the given one and return the corresponding list of (key, value) pairs.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupLT 3  (fromList [(3,'a'), (5,'b')])
[]
>>> lookupLT 9 (fromList [(3,'a'), (5,'b')])
[(3,'a')]

\(\mathcal{O}(w\log n)\). Find the largest key smaller or equal to the given one and return the corresponding list of (key, value) pairs.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupLE 2 (fromList [(3,'a'), (5,'b')])
[]
>>> lookupLE 3 (fromList [(3,'a'), (5,'b')])
[(3,'a')]
>>> lookupLE 10 (fromList [(3,'a'), (5,'b')])
[(5,'b')]

\(\mathcal{O}(w\log n)\). Find the smallest key greater or equal to the given one and return the corresponding list of (key, value) pairs.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupGE 3 (fromList [(3,'a'), (5,'b')])
[(3,'a')]
>>> lookupGE 5 (fromList [(3,'a'), (10,'b')])
[(10,'b')]
>>> lookupGE 6 (fromList [(3,'a'), (5,'b')])
[]

\(\mathcal{O}(w\log n)\). Find the smallest key greater than the given one and return the corresponding list of (key, value) pairs.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupGT 5 (fromList [(3,'a'), (10,'b')])
[(10,'b')]
>>> lookupGT 5 (fromList [(3,'a'), (5,'b')])
[]

\(\mathcal{O}(1)\). The empty map.

>>> empty
fromList []
>>> size empty
0

\(\mathcal{O}(w\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")])
fromList [(3,"b")]
>>> delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
True
>>> delete 5 empty
fromList []

\(\mathcal{O}(w\log n)\). Simultaneous delete and lookup.

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). 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")]
True

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Union with a combining function.

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

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). 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")]
True

\(\mathcal{O}(wn\log n)\), where \(n=\max_i n_i\) and \(w=\max_i w_i\). 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")]
:}
True

>>> :{
 unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])]
     == fromList [(3, "B3"), (5, "A3"), (7, "C")]
:}
True

\(\mathcal{O}(wn\log n)\), where \(n=\max_i n_i\) and \(w=\max_i w_i\). 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")]
:}
True

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). 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")])
fromList [(3,"b")]

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). 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")])
fromList [(3,"b:B")]

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). 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")])
fromList [(3,"3:b|B")]

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). 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")])
fromList [(5,"a")]

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Intersection with a combining function.

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

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). 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")])
fromList [(5,"5:a|A")]

\(\mathcal{O}(wn\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")]
True
>>> mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
fromList [(1,"c")]
>>> mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
fromList [(3,"c")]

\(\mathcal{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, for every chain ls in s we have:

and [x < y ==> f x < f y | x <- ls, y <- ls]
                    ==> mapKeysMonotonic f s == mapKeys f 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")]
True

\(\mathcal{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.

\(\mathcal{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)"
True

\(\mathcal{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.

\(\mathcal{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.

\(\mathcal{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.

>>> 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)"
True

\(\mathcal{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.

\(\mathcal{O}(n)\). Fold the keys and values in the map using the given monoid, such that

foldMapWithKey f = fold . mapWithKey f

\(\mathcal{O}(n)\). Return all elements of the map in unspecified order.

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

\(\mathcal{O}(n)\). Return all keys of the map in unspecified order.

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

\(\mathcal{O}(n)\). Return all key/value pairs in the map in unspecified order.

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

\(\mathcal{O}(n)\). Return all key/value pairs in the map in unspecified order.

Currently, toList = assocs.

Intentionally named this way, to disambiguate it from fromList. This is so that we can doctest this module.

\(\mathcal{O}(n)\). Filter all values that satisfy the predicate.

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

\(\mathcal{O}(n)\). Filter all keys/values that satisfy the predicate.

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

\(\mathcal{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")]) == (fromList [(3, "b")], fromList [(5, "a")])
True
>>> partition (< "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
True
>>> partition (> "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
True

\(\mathcal{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 (\ (Div k) _ -> k > 3) (fromList [(5,"a"), (3,"b")]) == (fromList [(5, "a")], fromList [(3, "b")])
True
>>> partitionWithKey (\ (Div k) _ -> k < 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
True
>>> partitionWithKey (\ (Div k) _ -> k > 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
True

\(\mathcal{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 = filterWithKey (k _ -> p k)

Since: 0.0.1.0

\(\mathcal{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 = filterWithKey (k -> not (p k))

Since: 0.0.1.0

\(\mathcal{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 = partitionWithKey (k _ -> p k) 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).

Since: 0.0.1.0

\(\mathcal{O}(n_2 w_1 n_1 \log n_1)\). This function is defined as (isSubmapOf = isSubmapOfBy (==)).

\(\mathcal{O}(n_2 w_1 n_1 \log n_1)\). 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 [(1,'a')]) (fromList [(1,'a'),(2,'b')])
True
>>> isSubmapOfBy (<=) (fromList [(1,'a')]) (fromList [(1,'b'),(2,'c')])
True
>>> isSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a'),(2,'b')])
True

But the following are all False:

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

\(\mathcal{O}(n_2 w_1 n_1 \log n_1)\). Is this a proper submap? (ie. a submap but not equal). Defined as (isProperSubmapOf = isProperSubmapOfBy (==)).

\(\mathcal{O}(n_2 w_1 n_1 \log n_1)\). 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,'a')]) (fromList [(1,'a'),(2,'b')])
True
>>> isProperSubmapOfBy (<=) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
True

But the following are all False:

>>> isProperSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a'),(2,'b')])
False
>>> isProperSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a')])
False
>>> isProperSubmapOfBy (<)  (fromList [(1,'a')])         (fromList [(1,'a'),(2,'b')])
False

\(\mathcal{O}(w\log n)\). The minimal keys of the map.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupMin (fromList [(6,"a"), (3,"b")])
[(3,"b")]
>>> lookupMin empty
[]

\(\mathcal{O}(w\log n)\). The maximal keys of the map.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupMax (fromList [(6,"a"), (3,"b")])
[(6,"a")]
>>> lookupMax empty
[]