Data.IntMap.NonEmpty.Internal

A non-empty (by construction) map from integer keys to values a. At least one key-value pair exists in an NEIntMap v at all times.

Functions that take an NEIntMap can safely operate on it with the assumption that it has at least one key-value pair.

Functions that return an NEIntMap provide an assurance that the result has at least one key-value pair.

Data.IntMap.NonEmpty re-exports the API of Data.IntMap, faithfully reproducing asymptotics, typeclass constraints, and semantics. Functions that ensure that input and output maps are both non-empty (like insert) return NEIntMap, but functions that might potentially return an empty map (like delete) return a IntMap instead.

You can directly construct an NEIntMap with the API from Data.IntMap.NonEmpty; it's more or less the same as constructing a normal IntMap, except you don't have access to Data.IntMap.empty. There are also a few ways to construct an NEIntMap from a IntMap:

1. The nonEmptyMap smart constructor will convert a IntMap k a into a Maybe (NEIntMap k a), returning Nothing if the original IntMap was empty.

2. You can use the Data.IntMap.NonEmpty.insertIntMap family of functions to insert a value into a IntMap to create a guaranteed NEIntMap.

3. You can use the IsNonEmpty and IsEmpty patterns to "pattern match" on a IntMap to reveal it as either containing a NEIntMap or an empty map.

4. withNonEmpty offers a continuation-based interface for deconstructing a IntMap and treating it as if it were an NEIntMap.

You can convert an NEIntMap into a IntMap with toMap or IsNonEmpty, essentially "obscuring" the non-empty property from the type.

O(1). A map with a single element.

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

O(log n). Smart constructor for an NEIntMap from a IntMap. Returns Nothing if the IntMap was originally actually empty, and Just n with an NEIntMap, if the IntMap was not empty.

nonEmptyMap and maybe Data.IntMap.empty toMap form an isomorphism: they are perfect structure-preserving inverses of eachother.

See IsNonEmpty for a pattern synonym that lets you "match on" the possiblity of a IntMap being an NEIntMap.

nonEmptyMap (Data.IntMap.fromList [(3,"a"), (5,"b")]) == Just (fromList ((3,"a") :| [(5,"b")]))

O(log n). A general continuation-based way to consume a IntMap as if it were an NEIntMap. withNonEmpty def f will take a IntMap. If map is empty, it will evaluate to def. Otherwise, a non-empty map NEIntMap will be fed to the function f instead.

nonEmptyMap == withNonEmpty Nothing Just

O(n*log n). Build a non-empty map from a non-empty 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.

fromList ((5,"a") :| [(3,"b"), (5, "c")]) == fromList ((5,"c") :| [(3,"b")])
fromList ((5,"c") :| [(3,"b"), (5, "a")]) == fromList ((5,"a") :| [(3,"b")])

O(n). Convert the map to a non-empty list of key/value pairs.

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

O(n). IntMap a function over all values in the map.

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

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

See Data.IntMap.NonEmpty.insertIntMapWith for a version where the first argument is a IntMap.

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

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

The left-biased union of a non-empty 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")])

O(n). Return all elements of the map in the ascending order of their keys.

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

O(1). The number of elements in the map. Guaranteed to be greater than zero.

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

O(log n). Convert a non-empty map back into a normal possibly-empty map, for usage with functions that expect IntMap.

Can be thought of as "obscuring" the non-emptiness of the map in its type. See the Data.IntMap.NonEmpty.IsNotEmpty pattern.

nonEmptyMap and maybe Data.IntMap.empty toMap form an isomorphism: they are perfect structure-preserving inverses of eachother.

toMap (fromList ((3,"a") :| [(5,"b")])) == Data.IntMap.fromList [(3,"a"), (5,"b")]

O(n). Fold the values in the map using the given right-associative binary operator, such that foldr f z == foldr f z . elems.

elemsList map = foldr (:) [] map

let f a len = len + (length a)
foldr f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4

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.

O(n). A version of foldr that uses the value at the maximal key in the map as the starting value.

Note that, unlike foldr1 for IntMap, this function is total if the input function is total.

O(n). Fold the values in the map using the given left-associative binary operator, such that foldl f z == foldl f z . elems.

elemsList = reverse . foldl (flip (:)) []

let f len a = len + (length a)
foldl f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4

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.

O(n). A version of foldl that uses the value at the minimal key in the map as the starting value.

Note that, unlike foldl1 for IntMap, this function is total if the input function is total.

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.

Use traverseWithKey1 whenever possible (if your Applicative also has Apply instance). This version is provided only for types that do not have Apply instance, since Apply is not at the moment (and might not ever be) an official superclass of Applicative.

WARNING: Differs from Data.IntMap.traverseWithKey, which traverses positive items first, then negative items.

traverseWithKey f = unwrapApplicative . traverseWithKey1 (\k -> WrapApplicative . f k)

O(n). traverseWithKey1 f m == fromList $ traverse1 ((k, v) -> (,) k $ f k v) (toList m)

That is, behaves exactly like a regular traverse1 except that the traversing function also has access to the key associated with a value.

WARNING: Differs from Data.IntMap.traverseWithKey, which traverses positive items first, then negative items.

Is more general than traverseWithKey, since works with all Apply, and not just Applicative.

O(n). Fold the keys and values in the map using the given semigroup, such that

foldMapWithKey f = fold1 . mapWithKey f

WARNING: Differs from Data.IntMap.foldMapWithKey, which traverses positive items first, then negative items.

This can be an asymptotically faster than foldrWithKey or foldlWithKey for some monoids.

O(log n). Insert new key and value into a map where keys are strictly greater than the new key. That is, the new key must be strictly less than all keys present in the IntMap. /The precondition is not checked./

At the moment this is simply an alias for Data.IntSet.insert, but it's left here as a placeholder in case this eventually gets implemented in a more efficient way.

O(log n). Insert new key and value into a map where keys are strictly less than the new key. That is, the new key must be strictly greater than all keys present in the IntMap. /The precondition is not checked./

At the moment this is simply an alias for Data.IntSet.insert, but it's left here as a placeholder in case this eventually gets implemented in a more efficient way.

O(n). Test if the internal map structure is valid.