Data.Map.NonEmpty.Internal

Unsafe internal-use functions used in the implementation of Data.Map.NonEmpty. These functions can potentially be used to break the abstraction of NEMap and produce unsound maps, so be wary!

Non-Empty Map type

data NEMap k a

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

Constructors

NEMap

Fields

• nemK0 :: !k

  invariant: must be smaller than smallest key in map

• nemV0 :: a
• nemMap :: !(Map k a)

Instances

Eq2 NEMap

Defined in Data.Map.NonEmpty.Internal

Methods

liftEq2 :: (a -> b -> Bool) -> (c -> d -> Bool) -> NEMap a c -> NEMap b d -> Bool

Ord2 NEMap

Defined in Data.Map.NonEmpty.Internal

Methods

liftCompare2 :: (a -> b -> Ordering) -> (c -> d -> Ordering) -> NEMap a c -> NEMap b d -> Ordering

Show2 NEMap

Defined in Data.Map.NonEmpty.Internal

Methods

liftShowsPrec2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> Int -> NEMap a b -> ShowS

liftShowList2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> [NEMap a b] -> ShowS

Functor (NEMap k)

Defined in Data.Map.NonEmpty.Internal

Methods

fmap :: (a -> b) -> NEMap k a -> NEMap k b

(<$) :: a -> NEMap k b -> NEMap k a

Foldable (NEMap k)

Traverses elements in order of ascending keys

foldr1, foldl1, minimum, maximum are all total.

Defined in Data.Map.NonEmpty.Internal

Methods

fold :: Monoid m => NEMap k m -> m

foldMap :: Monoid m => (a -> m) -> NEMap k a -> m

foldr :: (a -> b -> b) -> b -> NEMap k a -> b

foldr' :: (a -> b -> b) -> b -> NEMap k a -> b

foldl :: (b -> a -> b) -> b -> NEMap k a -> b

foldl' :: (b -> a -> b) -> b -> NEMap k a -> b

foldr1 :: (a -> a -> a) -> NEMap k a -> a

foldl1 :: (a -> a -> a) -> NEMap k a -> a

toList :: NEMap k a -> [a]

null :: NEMap k a -> Bool

length :: NEMap k a -> Int

elem :: Eq a => a -> NEMap k a -> Bool

maximum :: Ord a => NEMap k a -> a

minimum :: Ord a => NEMap k a -> a

sum :: Num a => NEMap k a -> a

product :: Num a => NEMap k a -> a

Traversable (NEMap k)

Traverses elements in order of ascending keys

Defined in Data.Map.NonEmpty.Internal

Methods

traverse :: Applicative f => (a -> f b) -> NEMap k a -> f (NEMap k b)

sequenceA :: Applicative f => NEMap k (f a) -> f (NEMap k a)

mapM :: Monad m => (a -> m b) -> NEMap k a -> m (NEMap k b)

sequence :: Monad m => NEMap k (m a) -> m (NEMap k a)

Eq k => Eq1 (NEMap k)

Defined in Data.Map.NonEmpty.Internal

Methods

liftEq :: (a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool

Ord k => Ord1 (NEMap k)

Defined in Data.Map.NonEmpty.Internal

Methods

liftCompare :: (a -> b -> Ordering) -> NEMap k a -> NEMap k b -> Ordering

(Ord k, Read k) => Read1 (NEMap k)

Defined in Data.Map.NonEmpty.Internal

Methods

liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (NEMap k a)

liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [NEMap k a]

liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (NEMap k a)

liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [NEMap k a]

Show k => Show1 (NEMap k)

Defined in Data.Map.NonEmpty.Internal

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> NEMap k a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [NEMap k a] -> ShowS

Comonad (NEMap k)

extract gets the value at the minimal key, and duplicate produces a map of maps comprised of all keys from the original map greater than or equal to the current key.

Since: 0.1.1.0

Defined in Data.Map.NonEmpty.Internal

Methods

extract :: NEMap k a -> a

duplicate :: NEMap k a -> NEMap k (NEMap k a)

extend :: (NEMap k a -> b) -> NEMap k a -> NEMap k b

Traversable1 (NEMap k)

Traverses elements in order of ascending keys

Defined in Data.Map.NonEmpty.Internal

Methods

traverse1 :: Apply f => (a -> f b) -> NEMap k a -> f (NEMap k b)

sequence1 :: Apply f => NEMap k (f b) -> f (NEMap k b)

Foldable1 (NEMap k)

Traverses elements in order of ascending keys

Defined in Data.Map.NonEmpty.Internal

Methods

fold1 :: Semigroup m => NEMap k m -> m

foldMap1 :: Semigroup m => (a -> m) -> NEMap k a -> m

toNonEmpty :: NEMap k a -> NonEmpty a

(Eq k, Eq a) => Eq (NEMap k a)

Defined in Data.Map.NonEmpty.Internal

Methods

(==) :: NEMap k a -> NEMap k a -> Bool

(/=) :: NEMap k a -> NEMap k a -> Bool

(Data k, Data a, Ord k) => Data (NEMap k a)

Defined in Data.Map.NonEmpty.Internal

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> NEMap k a -> c (NEMap k a)

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (NEMap k a)

toConstr :: NEMap k a -> Constr

dataTypeOf :: NEMap k a -> DataType

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (NEMap k a))

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (NEMap k a))

gmapT :: (forall b. Data b => b -> b) -> NEMap k a -> NEMap k a

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> NEMap k a -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> NEMap k a -> r

gmapQ :: (forall d. Data d => d -> u) -> NEMap k a -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> NEMap k a -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> NEMap k a -> m (NEMap k a)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> NEMap k a -> m (NEMap k a)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> NEMap k a -> m (NEMap k a)

(Ord k, Ord a) => Ord (NEMap k a)

Defined in Data.Map.NonEmpty.Internal

Methods

compare :: NEMap k a -> NEMap k a -> Ordering

(<) :: NEMap k a -> NEMap k a -> Bool

(<=) :: NEMap k a -> NEMap k a -> Bool

(>) :: NEMap k a -> NEMap k a -> Bool

(>=) :: NEMap k a -> NEMap k a -> Bool

max :: NEMap k a -> NEMap k a -> NEMap k a

min :: NEMap k a -> NEMap k a -> NEMap k a

(Ord k, Read k, Read e) => Read (NEMap k e)

Defined in Data.Map.NonEmpty.Internal

Methods

readsPrec :: Int -> ReadS (NEMap k e)

readList :: ReadS [NEMap k e]

readPrec :: ReadPrec (NEMap k e)

readListPrec :: ReadPrec [NEMap k e]

(Show k, Show a) => Show (NEMap k a)

Defined in Data.Map.NonEmpty.Internal

Methods

showsPrec :: Int -> NEMap k a -> ShowS

show :: NEMap k a -> String

showList :: [NEMap k a] -> ShowS

Ord k => Semigroup (NEMap k a)

Left-biased union

Defined in Data.Map.NonEmpty.Internal

Methods

(<>) :: NEMap k a -> NEMap k a -> NEMap k a

sconcat :: NonEmpty (NEMap k a) -> NEMap k a

stimes :: Integral b => b -> NEMap k a -> NEMap k a

(NFData k, NFData a) => NFData (NEMap k a)

Defined in Data.Map.NonEmpty.Internal

Methods

rnf :: NEMap k a -> ()

singleton :: k -> a -> NEMap k a

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

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

nonEmptyMap :: Map k a -> Maybe (NEMap k a)

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

withNonEmpty

Arguments

:: r

value to return if map is empty

-> (NEMap k a -> r)

function to apply if map is not empty

-> Map k a

-> r

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

fromList :: Ord k => NonEmpty (k, a) -> NEMap k a

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

toList :: NEMap k a -> NonEmpty (k, a)

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

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

map :: (a -> b) -> NEMap k a -> NEMap k b

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

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

insertWith :: Ord k => (a -> a -> a) -> k -> a -> NEMap k a -> NEMap 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).

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

union :: Ord k => NEMap k a -> NEMap k a -> NEMap 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")])

unions :: (Foldable1 f, Ord k) => f (NEMap k a) -> NEMap k a

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

elems :: NEMap k a -> NonEmpty a

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

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

size :: NEMap k a -> Int

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

toMap :: NEMap k a -> Map k a

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 IsNotEmpty pattern.

nonEmptyMap and maybe 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")]

Folds

foldr :: (a -> b -> b) -> b -> NEMap k a -> 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

foldr' :: (a -> b -> b) -> b -> NEMap k a -> b

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.

foldr1 :: (a -> a -> a) -> NEMap k a -> a

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.

foldl :: (a -> b -> a) -> a -> NEMap k b -> a

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

foldl' :: (a -> b -> a) -> a -> NEMap k b -> a

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.

foldl1 :: (a -> a -> a) -> NEMap k a -> a

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.

Traversals

traverseWithKey :: Applicative t => (k -> a -> t b) -> NEMap k a -> t (NEMap 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.

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)

traverseWithKey1 :: Apply t => (k -> a -> t b) -> NEMap k a -> t (NEMap k b)

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.

foldMapWithKey :: Semigroup m => (k -> a -> m) -> NEMap k a -> m

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.

Unsafe Map Functions

insertMinMap :: k -> a -> Map k a -> Map k a

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.

insertMaxMap :: k -> a -> Map k a -> Map k a

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.

Debug

valid :: Ord k => NEMap k a -> Bool

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