nonempty-containers-0.3.5.0: Non-empty variants of containers data types, with full API

Copyright | (c) Justin Le 2018
License | BSD3
Maintainer | justin@jle.im
Stability | experimental
Portability | non-portable
Safe Haskell | None
Language | Haskell2010

Data.Map.NonEmpty.Internal

Contents

- Non-Empty Map type
- Folds
- Traversals
- Unsafe Map Functions
- Debug

Description

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!

Synopsis

- data NEMap k a = NEMap {
  - nemK0 :: !k
  - nemV0 :: a
  - nemMap :: !(Map k a)
  }
- singleton :: k -> a -> NEMap k a
- nonEmptyMap :: Map k a -> Maybe (NEMap k a)
- withNonEmpty :: r -> (NEMap k a -> r) -> Map k a -> r
- fromList :: Ord k => NonEmpty (k, a) -> NEMap k a
- toList :: NEMap k a -> NonEmpty (k, a)
- map :: (a -> b) -> NEMap k a -> NEMap k b
- insertWith :: Ord k => (a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
- union :: Ord k => NEMap k a -> NEMap k a -> NEMap k a
- unions :: (Foldable1 f, Ord k) => f (NEMap k a) -> NEMap k a
- elems :: NEMap k a -> NonEmpty a
- size :: NEMap k a -> Int
- toMap :: NEMap k a -> Map k a
- foldr :: (a -> b -> b) -> b -> NEMap k a -> b
- foldr' :: (a -> b -> b) -> b -> NEMap k a -> b
- foldr1 :: (a -> a -> a) -> NEMap k a -> a
- foldl :: (a -> b -> a) -> a -> NEMap k b -> a
- foldl' :: (a -> b -> a) -> a -> NEMap k b -> a
- foldl1 :: (a -> a -> a) -> NEMap k a -> a
- traverseWithKey :: Applicative t => (k -> a -> t b) -> NEMap k a -> t (NEMap k b)
- traverseWithKey1 :: Apply t => (k -> a -> t b) -> NEMap k a -> t (NEMap k b)
- foldMapWithKey :: Semigroup m => (k -> a -> m) -> NEMap k a -> m
- insertMinMap :: k -> a -> Map k a -> Map k a
- insertMaxMap :: k -> a -> Map k a -> Map k a
- valid :: Ord k => NEMap k a -> Bool

# Non-Empty Map type

data NEMap k a Source #

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

Instances details

Eq2 NEMap Source # |
Instance details Defined in Data.Map.NonEmpty.Internal Methods liftEq2 :: (a -> b -> Bool) -> (c -> d -> Bool) -> NEMap a c -> NEMap b d -> Bool Source #
Ord2 NEMap Source # |
Instance details Defined in Data.Map.NonEmpty.Internal Methods liftCompare2 :: (a -> b -> Ordering) -> (c -> d -> Ordering) -> NEMap a c -> NEMap b d -> Ordering Source #
Show2 NEMap Source # |
Instance details Defined in Data.Map.NonEmpty.Internal Methods liftShowsPrec2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> Int -> NEMap a b -> ShowS Source # liftShowList2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> [NEMap a b] -> ShowS Source #
Foldable1 (NEMap k) Source # | Traverses elements in order of ascending keys

Instance details

Defined in Data.Map.NonEmpty.Internal

Methods

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

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

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

toNonEmpty :: NEMap k a -> NonEmpty a Source #

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

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

head :: NEMap k a -> a Source #

last :: NEMap k a -> a Source #

foldrMap1 :: (a -> b) -> (a -> b -> b) -> NEMap k a -> b Source #

foldlMap1' :: (a -> b) -> (b -> a -> b) -> NEMap k a -> b Source #

foldlMap1 :: (a -> b) -> (b -> a -> b) -> NEMap k a -> b Source #

foldrMap1' :: (a -> b) -> (a -> b -> b) -> NEMap k a -> b Source #

Eq k => Eq1 (NEMap k) Source # |
Instance details Defined in Data.Map.NonEmpty.Internal Methods liftEq :: (a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool Source #
Ord k => Ord1 (NEMap k) Source # |
Instance details Defined in Data.Map.NonEmpty.Internal Methods liftCompare :: (a -> b -> Ordering) -> NEMap k a -> NEMap k b -> Ordering Source #
(Ord k, Read k) => Read1 (NEMap k) Source # |
Instance details Defined in Data.Map.NonEmpty.Internal Methods liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (NEMap k a) Source # liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [NEMap k a] Source # liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (NEMap k a) Source # liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [NEMap k a] Source #
Show k => Show1 (NEMap k) Source # |
Instance details Defined in Data.Map.NonEmpty.Internal Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> NEMap k a -> ShowS Source # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [NEMap k a] -> ShowS Source #
Comonad (NEMap k) Source # | `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
Instance details Defined in Data.Map.NonEmpty.Internal Methods extract :: NEMap k a -> a Source # duplicate :: NEMap k a -> NEMap k (NEMap k a) Source # extend :: (NEMap k a -> b) -> NEMap k a -> NEMap k b Source #
Functor (NEMap k) Source # |
Instance details Defined in Data.Map.NonEmpty.Internal Methods fmap :: (a -> b) -> NEMap k a -> NEMap k b Source # (<$) :: a -> NEMap k b -> NEMap k a Source #
Foldable (NEMap k) Source # | Traverses elements in order of ascending keys `foldr1`, `foldl1`, `minimum`, `maximum` are all total.

Instance details

Defined in Data.Map.NonEmpty.Internal

Methods

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

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

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

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

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

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

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

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

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

toList :: NEMap k a -> [a] Source #

null :: NEMap k a -> Bool Source #

length :: NEMap k a -> Int Source #

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

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

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

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

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

Traversable (NEMap k) Source # | Traverses elements in order of ascending keys
Instance details Defined in Data.Map.NonEmpty.Internal Methods traverse :: Applicative f => (a -> f b) -> NEMap k a -> f (NEMap k b) Source # sequenceA :: Applicative f => NEMap k (f a) -> f (NEMap k a) Source # mapM :: Monad m => (a -> m b) -> NEMap k a -> m (NEMap k b) Source # sequence :: Monad m => NEMap k (m a) -> m (NEMap k a) Source #
Invariant (NEMap k) Source # | Since: 0.3.4.4
Instance details Defined in Data.Map.NonEmpty.Internal Methods invmap :: (a -> b) -> (b -> a) -> NEMap k a -> NEMap k b Source #
Ord k => Alt (NEMap k) Source # | Since: 0.3.4.4
Instance details Defined in Data.Map.NonEmpty.Internal Methods (<!>) :: NEMap k a -> NEMap k a -> NEMap k a Source # some :: Applicative (NEMap k) => NEMap k a -> NEMap k [a] Source # many :: Applicative (NEMap k) => NEMap k a -> NEMap k [a] Source #
Traversable1 (NEMap k) Source # | Traverses elements in order of ascending keys
Instance details Defined in Data.Map.NonEmpty.Internal Methods traverse1 :: Apply f => (a -> f b) -> NEMap k a -> f (NEMap k b) Source # sequence1 :: Apply f => NEMap k (f b) -> f (NEMap k b) Source #
(FromJSONKey k, Ord k, FromJSON a) => FromJSON (NEMap k a) Source # |
Instance details Defined in Data.Map.NonEmpty.Internal Methods parseJSON :: Value -> Parser (NEMap k a) Source # parseJSONList :: Value -> Parser [NEMap k a] Source # omittedField :: Maybe (NEMap k a) Source #
(ToJSONKey k, ToJSON a) => ToJSON (NEMap k a) Source # |
Instance details Defined in Data.Map.NonEmpty.Internal Methods toJSON :: NEMap k a -> Value Source # toEncoding :: NEMap k a -> Encoding Source # toJSONList :: [NEMap k a] -> Value Source # toEncodingList :: [NEMap k a] -> Encoding Source # omitField :: NEMap k a -> Bool Source #
(NFData k, NFData a) => NFData (NEMap k a) Source # |
Instance details Defined in Data.Map.NonEmpty.Internal Methods rnf :: NEMap k a -> () Source #
Ord k => Semigroup (NEMap k a) Source # | Left-biased union
Instance details Defined in Data.Map.NonEmpty.Internal Methods (<>) :: NEMap k a -> NEMap k a -> NEMap k a Source # sconcat :: NonEmpty (NEMap k a) -> NEMap k a Source # stimes :: Integral b => b -> NEMap k a -> NEMap k a Source #
(Data k, Data a, Ord k) => Data (NEMap k a) Source # |

Instance details

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) Source #

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

toConstr :: NEMap k a -> Constr Source #

dataTypeOf :: NEMap k a -> DataType Source #

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

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

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

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

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

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

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

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

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

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

(Ord k, Read k, Read e) => Read (NEMap k e) Source # |
Instance details Defined in Data.Map.NonEmpty.Internal Methods readsPrec :: Int -> ReadS (NEMap k e) Source # readList :: ReadS [NEMap k e] Source # readPrec :: ReadPrec (NEMap k e) Source # readListPrec :: ReadPrec [NEMap k e] Source #
(Show k, Show a) => Show (NEMap k a) Source # |
Instance details Defined in Data.Map.NonEmpty.Internal Methods showsPrec :: Int -> NEMap k a -> ShowS Source # show :: NEMap k a -> String Source # showList :: [NEMap k a] -> ShowS Source #
(Eq k, Eq a) => Eq (NEMap k a) Source # |
Instance details Defined in Data.Map.NonEmpty.Internal Methods (==) :: NEMap k a -> NEMap k a -> Bool Source # (/=) :: NEMap k a -> NEMap k a -> Bool Source #
(Ord k, Ord a) => Ord (NEMap k a) Source # |

Instance details

Defined in Data.Map.NonEmpty.Internal

Methods

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

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

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

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

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

max :: NEMap k a -> NEMap k a -> NEMap k a Source #

min :: NEMap k a -> NEMap k a -> NEMap k a Source #

singleton :: k -> a -> NEMap k a Source #

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) Source #

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 Source #

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 Source #

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) Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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) Source #

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) Source #

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 Source #

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 Source #

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 Source #

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 Source #

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