Data.IntMap.NonEmpty.Internal

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

Non-Empty IntMap type

data NEIntMap a

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

Constructors

NEIntMap

Fields

• neimK0 :: !Key

  invariant: must be smaller than smallest key in map

• neimV0 :: a
• neimIntMap :: !(IntMap a)

Instances

Functor NEIntMap

Defined in Data.IntMap.NonEmpty.Internal

Methods

fmap :: (a -> b) -> NEIntMap a -> NEIntMap b

(<$) :: a -> NEIntMap b -> NEIntMap a

Foldable NEIntMap

Traverses elements in order of ascending keys.

WARNING: fold and foldMap are different than for the IntMap instance. They traverse elements in order of ascending keys, while IntMap traverses positive keys first, then negative keys.

foldr1, foldl1, minimum, maximum are all total.

Defined in Data.IntMap.NonEmpty.Internal

Methods

fold :: Monoid m => NEIntMap m -> m

foldMap :: Monoid m => (a -> m) -> NEIntMap a -> m

foldr :: (a -> b -> b) -> b -> NEIntMap a -> b

foldr' :: (a -> b -> b) -> b -> NEIntMap a -> b

foldl :: (b -> a -> b) -> b -> NEIntMap a -> b

foldl' :: (b -> a -> b) -> b -> NEIntMap a -> b

foldr1 :: (a -> a -> a) -> NEIntMap a -> a

foldl1 :: (a -> a -> a) -> NEIntMap a -> a

toList :: NEIntMap a -> [a]

null :: NEIntMap a -> Bool

length :: NEIntMap a -> Int

elem :: Eq a => a -> NEIntMap a -> Bool

maximum :: Ord a => NEIntMap a -> a

minimum :: Ord a => NEIntMap a -> a

sum :: Num a => NEIntMap a -> a

product :: Num a => NEIntMap a -> a

Traversable NEIntMap

Traverses elements in order of ascending keys

WARNING: Different than for the IntMap instance. They traverse elements in order of ascending keys, while IntMap traverses positive keys first, then negative keys.

Defined in Data.IntMap.NonEmpty.Internal

Methods

traverse :: Applicative f => (a -> f b) -> NEIntMap a -> f (NEIntMap b)

sequenceA :: Applicative f => NEIntMap (f a) -> f (NEIntMap a)

mapM :: Monad m => (a -> m b) -> NEIntMap a -> m (NEIntMap b)

sequence :: Monad m => NEIntMap (m a) -> m (NEIntMap a)

Eq1 NEIntMap

Defined in Data.IntMap.NonEmpty.Internal

Methods

liftEq :: (a -> b -> Bool) -> NEIntMap a -> NEIntMap b -> Bool

Ord1 NEIntMap

Defined in Data.IntMap.NonEmpty.Internal

Methods

liftCompare :: (a -> b -> Ordering) -> NEIntMap a -> NEIntMap b -> Ordering

Read1 NEIntMap

Defined in Data.IntMap.NonEmpty.Internal

Methods

liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (NEIntMap a)

liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [NEIntMap a]

liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (NEIntMap a)

liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [NEIntMap a]

Show1 NEIntMap

Defined in Data.IntMap.NonEmpty.Internal

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> NEIntMap a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [NEIntMap a] -> ShowS

Comonad NEIntMap

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.IntMap.NonEmpty.Internal

Methods

extract :: NEIntMap a -> a

duplicate :: NEIntMap a -> NEIntMap (NEIntMap a)

extend :: (NEIntMap a -> b) -> NEIntMap a -> NEIntMap b

Traversable1 NEIntMap

Traverses elements in order of ascending keys

WARNING: traverse1 and sequence1 are different traverse and sequence for the IntMap instance of Traversable. They traverse elements in order of ascending keys, while IntMap traverses positive keys first, then negative keys.

Defined in Data.IntMap.NonEmpty.Internal

Methods

traverse1 :: Apply f => (a -> f b) -> NEIntMap a -> f (NEIntMap b)

sequence1 :: Apply f => NEIntMap (f b) -> f (NEIntMap b)

Foldable1 NEIntMap

Traverses elements in order of ascending keys

WARNING: fold1 and foldMap1 are different than fold and foldMap for the IntMap instance of Foldable. They traverse elements in order of ascending keys, while IntMap traverses positive keys first, then negative keys.

Defined in Data.IntMap.NonEmpty.Internal

Methods

fold1 :: Semigroup m => NEIntMap m -> m

foldMap1 :: Semigroup m => (a -> m) -> NEIntMap a -> m

toNonEmpty :: NEIntMap a -> NonEmpty a

Eq a => Eq (NEIntMap a)

Defined in Data.IntMap.NonEmpty.Internal

Methods

(==) :: NEIntMap a -> NEIntMap a -> Bool

(/=) :: NEIntMap a -> NEIntMap a -> Bool

Data a => Data (NEIntMap a)

Defined in Data.IntMap.NonEmpty.Internal

Methods

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

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

toConstr :: NEIntMap a -> Constr

dataTypeOf :: NEIntMap a -> DataType

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

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

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

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

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

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

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

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

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

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

Ord a => Ord (NEIntMap a)

Defined in Data.IntMap.NonEmpty.Internal

Methods

compare :: NEIntMap a -> NEIntMap a -> Ordering

(<) :: NEIntMap a -> NEIntMap a -> Bool

(<=) :: NEIntMap a -> NEIntMap a -> Bool

(>) :: NEIntMap a -> NEIntMap a -> Bool

(>=) :: NEIntMap a -> NEIntMap a -> Bool

max :: NEIntMap a -> NEIntMap a -> NEIntMap a

min :: NEIntMap a -> NEIntMap a -> NEIntMap a

Read e => Read (NEIntMap e)

Defined in Data.IntMap.NonEmpty.Internal

Methods

readsPrec :: Int -> ReadS (NEIntMap e)

readList :: ReadS [NEIntMap e]

readPrec :: ReadPrec (NEIntMap e)

readListPrec :: ReadPrec [NEIntMap e]

Show a => Show (NEIntMap a)

Defined in Data.IntMap.NonEmpty.Internal

Methods

showsPrec :: Int -> NEIntMap a -> ShowS

show :: NEIntMap a -> String

showList :: [NEIntMap a] -> ShowS

Semigroup (NEIntMap a)

Left-biased union

Defined in Data.IntMap.NonEmpty.Internal

Methods

(<>) :: NEIntMap a -> NEIntMap a -> NEIntMap a

sconcat :: NonEmpty (NEIntMap a) -> NEIntMap a

stimes :: Integral b => b -> NEIntMap a -> NEIntMap a

NFData a => NFData (NEIntMap a)

Defined in Data.IntMap.NonEmpty.Internal

Methods

rnf :: NEIntMap a -> ()

type Key = Int

singleton :: Key -> a -> NEIntMap a

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

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

nonEmptyMap :: IntMap a -> Maybe (NEIntMap a)

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

withNonEmpty

Arguments

:: r

value to return if map is empty

-> (NEIntMap a -> r)

function to apply if map is not empty

-> IntMap a

-> r

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

fromList :: NonEmpty (Key, a) -> NEIntMap 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 :: NEIntMap a -> NonEmpty (Key, 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) -> NEIntMap a -> NEIntMap b

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

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

insertWith :: (a -> a -> a) -> Key -> a -> NEIntMap a -> NEIntMap 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 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")])

union :: NEIntMap a -> NEIntMap a -> NEIntMap 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 => f (NEIntMap a) -> NEIntMap 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 :: NEIntMap 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 :: NEIntMap 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 :: NEIntMap a -> IntMap a

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 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.IntMap.fromList [(3,"a"), (5,"b")]

Folds

foldr :: (a -> b -> b) -> b -> NEIntMap 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 -> NEIntMap 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) -> NEIntMap 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 IntMap, this function is total if the input function is total.

foldl :: (a -> b -> a) -> a -> NEIntMap 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 -> NEIntMap 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) -> NEIntMap 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 IntMap, this function is total if the input function is total.

Traversals

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

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

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

traverseWithKey1 :: Apply t => (Key -> a -> t b) -> NEIntMap a -> t (NEIntMap 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.

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.

foldMapWithKey :: Semigroup m => (Key -> a -> m) -> NEIntMap a -> m

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.

traverseMapWithKey :: Applicative t => (Key -> a -> t b) -> IntMap a -> t (IntMap b)

O(n). A fixed version of traverseWithKey that traverses items in ascending order of keys.

Unsafe IntMap Functions

insertMinMap :: Key -> a -> IntMap a -> IntMap 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 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.

insertMaxMap :: Key -> a -> IntMap a -> IntMap 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 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.

Debug

valid :: NEIntMap a -> Bool

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

CPP compatibility

lookupMinMap :: IntMap a -> Maybe (Key, a)

CPP for new functions not in old containers ---------------------------------------------

Compatibility layer for lookupMinMap.

lookupMaxMap :: IntMap a -> Maybe (Key, a)

Compatibility layer for lookupMaxMap.