Data.Map.NonEmpty.Internal

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

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

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

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

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

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

2. You can use the insertMap family of functions to insert a value into a Map to create a guaranteed NEMap.

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

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

You can convert an NEMap into a Map 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 NEMap from a Map. Returns Nothing if the Map was originally actually empty, and Just n with an NEMap, if the Map was not empty.

nonEmptyMap and maybe Data.Map.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 Map being an NEMap.

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

O(log n). A general continuation-based way to consume a Map as if it were an NEMap. withNonEmpty def f will take a Map. If map is empty, it will evaluate to def. Otherwise, a non-empty map NEMap 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). Map 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 insertMapWith for a version where the first argument is a Map.

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

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

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

toMap (fromList ((3,"a") :| [(5,"b")])) == Data.Map.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 Map, 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 Map, 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.

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.

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

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 Map. /The precondition is not checked./

While this has the same asymptotics as Data.Map.insert, it saves a constant factor for key comparison (so may be helpful if comparison is expensive) and also does not require an Ord instance for the key type.

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 Map. /The precondition is not checked./

While this has the same asymptotics as Data.Map.insert, it saves a constant factor for key comparison (so may be helpful if comparison is expensive) and also does not require an Ord instance for the key type.

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