dependent-map-0.4.0.1: Dependent finite maps (partial dependent products)

Safe Haskell | Trustworthy
Language | Haskell2010

Data.Dependent.Map

Contents

- Operators
- Query
- Construction
  - Insertion
  - Delete/Update
- Combine
  - Union
  - Difference
  - Intersection
- Traversal
  - Map
  - Fold
- Conversion
  - Lists
  - Ordered lists
- Filter
- Submap
- Indexed
- Min/Max
- Debugging
- Orphan instances

Synopsis

- data DMap (k1 :: k -> Type) (f :: k -> Type)
- (!) :: forall {k1} k2 f (v :: k1). GCompare k2 => DMap k2 f -> k2 v -> f v
- (\\) :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => DMap k2 f -> DMap k2 f -> DMap k2 f
- null :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Bool
- size :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Int
- member :: forall {k1} k2 (a :: k1) (f :: k1 -> Type). GCompare k2 => k2 a -> DMap k2 f -> Bool
- notMember :: forall {k1} k2 (v :: k1) (f :: k1 -> Type). GCompare k2 => k2 v -> DMap k2 f -> Bool
- lookup :: forall {k1} k2 f (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> Maybe (f v)
- findWithDefault :: forall {k1} k2 f (v :: k1). GCompare k2 => f v -> k2 v -> DMap k2 f -> f v
- empty :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f
- singleton :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f
- insert :: forall {k1} k2 f (v :: k1). GCompare k2 => k2 v -> f v -> DMap k2 f -> DMap k2 f
- insertWith :: forall {k1} k2 f (v :: k1). GCompare k2 => (f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> DMap k2 f
- insertWith' :: forall {k1} k2 f (v :: k1). GCompare k2 => (f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> DMap k2 f
- insertWithKey :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> DMap k2 f
- insertWithKey' :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> DMap k2 f
- insertLookupWithKey :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> (Maybe (f v), DMap k2 f)
- insertLookupWithKey' :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> (Maybe (f v), DMap k2 f)
- delete :: forall {k1} k2 (f :: k1 -> Type) (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> DMap k2 f
- adjust :: forall {k1} k2 f (v :: k1). GCompare k2 => (f v -> f v) -> k2 v -> DMap k2 f -> DMap k2 f
- adjustWithKey :: forall {k1} k2 (v :: k1) f. GCompare k2 => (k2 v -> f v -> f v) -> k2 v -> DMap k2 f -> DMap k2 f
- adjustWithKey' :: forall {k1} k2 (v :: k1) f. GCompare k2 => (k2 v -> f v -> f v) -> k2 v -> DMap k2 f -> DMap k2 f
- update :: forall {k1} k2 f (v :: k1). GCompare k2 => (f v -> Maybe (f v)) -> k2 v -> DMap k2 f -> DMap k2 f
- updateWithKey :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> Maybe (f v)) -> k2 v -> DMap k2 f -> DMap k2 f
- updateLookupWithKey :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> Maybe (f v)) -> k2 v -> DMap k2 f -> (Maybe (f v), DMap k2 f)
- alter :: forall {k1} k2 f (v :: k1). GCompare k2 => (Maybe (f v) -> Maybe (f v)) -> k2 v -> DMap k2 f -> DMap k2 f
- alterF :: forall {k1} k2 f (v :: k1) g. (GCompare k2, Functor f) => k2 v -> (Maybe (g v) -> f (Maybe (g v))) -> DMap k2 g -> f (DMap k2 g)
- union :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => DMap k2 f -> DMap k2 f -> DMap k2 f
- unionWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> f v -> f v) -> DMap k2 f -> DMap k2 f -> DMap k2 f
- unions :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => [DMap k2 f] -> DMap k2 f
- unionsWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> f v -> f v) -> [DMap k2 f] -> DMap k2 f
- difference :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type) (g :: k1 -> Type). GCompare k2 => DMap k2 f -> DMap k2 g -> DMap k2 f
- differenceWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> g v -> Maybe (f v)) -> DMap k2 f -> DMap k2 g -> DMap k2 f
- intersection :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => DMap k2 f -> DMap k2 f -> DMap k2 f
- intersectionWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> g v -> h v) -> DMap k2 f -> DMap k2 g -> DMap k2 h
- map :: forall {k1} f g (k2 :: k1 -> Type). (forall (v :: k1). f v -> g v) -> DMap k2 f -> DMap k2 g
- ffor :: forall {k1} (k2 :: k1 -> Type) f g. DMap k2 f -> (forall (v :: k1). f v -> g v) -> DMap k2 g
- mapWithKey :: (forall (v :: k1). k2 v -> f v -> g v) -> DMap k2 f -> DMap k2 g
- fforWithKey :: DMap k2 f -> (forall (v :: k1). k2 v -> f v -> g v) -> DMap k2 g
- traverseWithKey_ :: forall {k1} t k2 f. Applicative t => (forall (v :: k1). k2 v -> f v -> t ()) -> DMap k2 f -> t ()
- forWithKey_ :: forall {k1} t k2 f. Applicative t => DMap k2 f -> (forall (v :: k1). k2 v -> f v -> t ()) -> t ()
- traverseWithKey :: forall {k1} t k2 f g. Applicative t => (forall (v :: k1). k2 v -> f v -> t (g v)) -> DMap k2 f -> t (DMap k2 g)
- forWithKey :: forall {k1} t k2 f g. Applicative t => DMap k2 f -> (forall (v :: k1). k2 v -> f v -> t (g v)) -> t (DMap k2 g)
- mapAccumLWithKey :: (forall (v :: k1). a -> k2 v -> f v -> (a, g v)) -> a -> DMap k2 f -> (a, DMap k2 g)
- mapAccumRWithKey :: (forall (v :: k1). a -> k2 v -> f v -> (a, g v)) -> a -> DMap k2 f -> (a, DMap k2 g)
- mapKeysWith :: GCompare k2 => (forall (v :: k). k2 v -> f v -> f v -> f v) -> (forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
- mapKeysMonotonic :: forall {k} k1 k2 (f :: k -> Type). (forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
- foldWithKey :: (forall (v :: k1). k2 v -> f v -> b -> b) -> b -> DMap k2 f -> b
- foldrWithKey :: (forall (v :: k1). k2 v -> f v -> b -> b) -> b -> DMap k2 f -> b
- foldlWithKey :: (forall (v :: k1). b -> k2 v -> f v -> b) -> b -> DMap k2 f -> b
- keys :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> [Some k2]
- assocs :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> [DSum k2 f]
- toList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> [DSum k2 f]
- fromList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => [DSum k2 f] -> DMap k2 f
- fromListWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> f v -> f v) -> [DSum k2 f] -> DMap k2 f
- toAscList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> [DSum k2 f]
- toDescList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> [DSum k2 f]
- fromAscList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GEq k2 => [DSum k2 f] -> DMap k2 f
- fromAscListWithKey :: GEq k2 => (forall (v :: k1). k2 v -> f v -> f v -> f v) -> [DSum k2 f] -> DMap k2 f
- fromDistinctAscList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). [DSum k2 f] -> DMap k2 f
- filter :: (a -> Bool) -> [a] -> [a]
- filterWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> Bool) -> DMap k2 f -> DMap k2 f
- partitionWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> Bool) -> DMap k2 f -> (DMap k2 f, DMap k2 f)
- mapMaybe :: forall {k1} (k2 :: k1 -> Type) f g. GCompare k2 => (forall (v :: k1). f v -> Maybe (g v)) -> DMap k2 f -> DMap k2 g
- mapMaybeWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> Maybe (g v)) -> DMap k2 f -> DMap k2 g
- mapEitherWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> Either (g v) (h v)) -> DMap k2 f -> (DMap k2 g, DMap k2 h)
- split :: forall {k1} k2 (f :: k1 -> Type) (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> (DMap k2 f, DMap k2 f)
- splitLookup :: forall {k1} k2 f (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> (DMap k2 f, Maybe (f v), DMap k2 f)
- isSubmapOf :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). (GCompare k2, Has' Eq k2 f) => DMap k2 f -> DMap k2 f -> Bool
- isSubmapOfBy :: GCompare k2 => (forall (v :: k1). k2 v -> k2 v -> f v -> g v -> Bool) -> DMap k2 f -> DMap k2 g -> Bool
- isProperSubmapOf :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). (GCompare k2, Has' Eq k2 f) => DMap k2 f -> DMap k2 f -> Bool
- isProperSubmapOfBy :: GCompare k2 => (forall (v :: k1). k2 v -> k2 v -> f v -> g v -> Bool) -> DMap k2 f -> DMap k2 g -> Bool
- lookupIndex :: forall {k1} k2 (f :: k1 -> Type) (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> Maybe Int
- findIndex :: forall {k1} k2 (v :: k1) (f :: k1 -> Type). GCompare k2 => k2 v -> DMap k2 f -> Int
- elemAt :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). Int -> DMap k2 f -> DSum k2 f
- updateAt :: (forall (v :: k1). k2 v -> f v -> Maybe (f v)) -> Int -> DMap k2 f -> DMap k2 f
- deleteAt :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). Int -> DMap k2 f -> DMap k2 f
- findMin :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> DSum k2 f
- findMax :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> DSum k2 f
- lookupMin :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Maybe (DSum k2 f)
- lookupMax :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Maybe (DSum k2 f)
- deleteMin :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> DMap k2 f
- deleteMax :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> DMap k2 f
- deleteFindMin :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> (DSum k2 f, DMap k2 f)
- deleteFindMax :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> (DSum k2 f, DMap k2 f)
- updateMinWithKey :: (forall (v :: k1). k2 v -> f v -> Maybe (f v)) -> DMap k2 f -> DMap k2 f
- updateMaxWithKey :: (forall (v :: k1). k2 v -> f v -> Maybe (f v)) -> DMap k2 f -> DMap k2 f
- minViewWithKey :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Maybe (DSum k2 f, DMap k2 f)
- maxViewWithKey :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Maybe (DSum k2 f, DMap k2 f)
- showTree :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). (GShow k2, Has' Show k2 f) => DMap k2 f -> String
- showTreeWith :: (forall (v :: k1). k2 v -> f v -> String) -> Bool -> Bool -> DMap k2 f -> String
- valid :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => DMap k2 f -> Bool

# Documentation

data DMap (k1 :: k -> Type) (f :: k -> Type) Source #

Dependent maps: `k` is a GADT-like thing with a facility for rediscovering its type parameter, elements of which function as identifiers tagged with the type of the thing they identify. Real GADTs are one useful instantiation of `k`, as are `Tag`s from Data.Unique.Tag in the 'prim-uniq' package.

Semantically, ``DMap` k f` is equivalent to a set of ``DSum` k f` where no two elements have the same tag.

More informally, `DMap` is to dependent products as `Map` is to `(->)`. Thus it could also be thought of as a partial (in the sense of "partial function") dependent product.

#### Instances

Instances details

GCompare k2 => Monoid (DMap k2 f) Source # |
Instance details Defined in Data.Dependent.Map Methods mempty :: DMap k2 f Source # mappend :: DMap k2 f -> DMap k2 f -> DMap k2 f Source # mconcat :: [DMap k2 f] -> DMap k2 f Source #
GCompare k2 => Semigroup (DMap k2 f) Source # |
Instance details Defined in Data.Dependent.Map Methods (<>) :: DMap k2 f -> DMap k2 f -> DMap k2 f Source # sconcat :: NonEmpty (DMap k2 f) -> DMap k2 f Source # stimes :: Integral b => b -> DMap k2 f -> DMap k2 f Source #
(GCompare k2, GRead k2, Has' Read k2 f) => Read (DMap k2 f) Source # |
Instance details Defined in Data.Dependent.Map Methods readsPrec :: Int -> ReadS (DMap k2 f) Source # readList :: ReadS [DMap k2 f] Source # readPrec :: ReadPrec (DMap k2 f) Source # readListPrec :: ReadPrec [DMap k2 f] Source #
(GShow k2, Has' Show k2 f) => Show (DMap k2 f) Source # |
Instance details Defined in Data.Dependent.Map Methods showsPrec :: Int -> DMap k2 f -> ShowS Source # show :: DMap k2 f -> String Source # showList :: [DMap k2 f] -> ShowS Source #
(GEq k2, Has' Eq k2 f) => Eq (DMap k2 f) Source # |
Instance details Defined in Data.Dependent.Map Methods (==) :: DMap k2 f -> DMap k2 f -> Bool Source # (/=) :: DMap k2 f -> DMap k2 f -> Bool Source #
(GCompare k2, Has' Eq k2 f, Has' Ord k2 f) => Ord (DMap k2 f) Source # |

Instance details

Defined in Data.Dependent.Map

Methods

compare :: DMap k2 f -> DMap k2 f -> Ordering Source #

(<) :: DMap k2 f -> DMap k2 f -> Bool Source #

(<=) :: DMap k2 f -> DMap k2 f -> Bool Source #

(>) :: DMap k2 f -> DMap k2 f -> Bool Source #

(>=) :: DMap k2 f -> DMap k2 f -> Bool Source #

max :: DMap k2 f -> DMap k2 f -> DMap k2 f Source #

min :: DMap k2 f -> DMap k2 f -> DMap k2 f Source #

# Operators

(!) :: forall {k1} k2 f (v :: k1). GCompare k2 => DMap k2 f -> k2 v -> f v infixl 9 Source #

O(log n). Find the value at a key. Calls `error` when the element can not be found.

    fromList [(5,'a'), (3,'b')] ! 1    Error: element not in the map
    fromList [(5,'a'), (3,'b')] ! 5 == 'a'

(\\) :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => DMap k2 f -> DMap k2 f -> DMap k2 f infixl 9 Source #

Same as `difference`.

# Query

null :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Bool Source #

O(1). Is the map empty?

size :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Int Source #

O(1). The number of elements in the map.

member :: forall {k1} k2 (a :: k1) (f :: k1 -> Type). GCompare k2 => k2 a -> DMap k2 f -> Bool Source #

O(log n). Is the key a member of the map? See also `notMember`.

notMember :: forall {k1} k2 (v :: k1) (f :: k1 -> Type). GCompare k2 => k2 v -> DMap k2 f -> Bool Source #

O(log n). Is the key not a member of the map? See also `member`.

lookup :: forall {k1} k2 f (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> Maybe (f v) Source #

O(log n). Lookup the value at a key in the map.

The function will return the corresponding value as `(`Just` value)`, or `Nothing` if the key isn't in the map.

findWithDefault :: forall {k1} k2 f (v :: k1). GCompare k2 => f v -> k2 v -> DMap k2 f -> f v Source #

O(log n). The expression `(`findWithDefault` def k map)` returns the value at key `k` or returns default value `def` when the key is not in the map.

# Construction

empty :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f Source #

O(1). The empty map.

    empty      == fromList []
    size empty == 0

singleton :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f Source #

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

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

## Insertion

insert :: forall {k1} k2 f (v :: k1). GCompare k2 => k2 v -> f v -> DMap k2 f -> DMap k2 f Source #

O(log n). Insert a new key and value in the map. If the key is already present in the map, the associated value is replaced with the supplied value. `insert` is equivalent to ``insertWith` `const``.

insertWith :: forall {k1} k2 f (v :: k1). GCompare k2 => (f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> DMap k2 f Source #

O(log n). Insert with a function, combining new value and old value. ``insertWith` f key value mp` will insert the entry `key :=> value` into `mp` if key does not exist in the map. If the key does exist, the function will insert the entry `key :=> f new_value old_value`.

insertWith' :: forall {k1} k2 f (v :: k1). GCompare k2 => (f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> DMap k2 f Source #

Same as `insertWith`, but the combining function is applied strictly. This is often the most desirable behavior.

insertWithKey :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> DMap k2 f Source #

O(log n). Insert with a function, combining key, new value and old value. ``insertWithKey` f key value mp` will insert the entry `key :=> value` into `mp` if key does not exist in the map. If the key does exist, the function will insert the entry `key :=> f key new_value old_value`. Note that the key passed to f is the same key passed to `insertWithKey`.

insertWithKey' :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> DMap k2 f Source #

Same as `insertWithKey`, but the combining function is applied strictly.

insertLookupWithKey :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> (Maybe (f v), DMap k2 f) Source #

O(log n). Combines insert operation with old value retrieval. The expression (``insertLookupWithKey` f k x map`) is a pair where the first element is equal to (``lookup` k map`) and the second element equal to (``insertWithKey` f k x map`).

insertLookupWithKey' :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> (Maybe (f v), DMap k2 f) Source #

O(log n). A strict version of `insertLookupWithKey`.

## Delete/Update

delete :: forall {k1} k2 (f :: k1 -> Type) (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> DMap k2 f Source #

O(log n). Delete a key and its value from the map. When the key is not a member of the map, the original map is returned.

adjust :: forall {k1} k2 f (v :: k1). GCompare k2 => (f v -> f v) -> k2 v -> DMap k2 f -> DMap k2 f Source #

O(log n). Update a value at a specific key with the result of the provided function. When the key is not a member of the map, the original map is returned.

adjustWithKey :: forall {k1} k2 (v :: k1) f. GCompare k2 => (k2 v -> f v -> f v) -> k2 v -> DMap k2 f -> DMap k2 f Source #

O(log n). Adjust a value at a specific key. When the key is not a member of the map, the original map is returned.

adjustWithKey' :: forall {k1} k2 (v :: k1) f. GCompare k2 => (k2 v -> f v -> f v) -> k2 v -> DMap k2 f -> DMap k2 f Source #

O(log n). A strict version of `adjustWithKey`.

update :: forall {k1} k2 f (v :: k1). GCompare k2 => (f v -> Maybe (f v)) -> k2 v -> DMap k2 f -> DMap k2 f Source #

O(log n). The expression (``update` f k map`) updates the value `x` at `k` (if it is in the map). If (`f x`) is `Nothing`, the element is deleted. If it is (``Just` y`), the key `k` is bound to the new value `y`.

updateWithKey :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> Maybe (f v)) -> k2 v -> DMap k2 f -> DMap k2 f Source #

O(log n). The expression (``updateWithKey` f k map`) updates the value `x` at `k` (if it is in the map). If (`f k x`) is `Nothing`, the element is deleted. If it is (``Just` y`), the key `k` is bound to the new value `y`.

updateLookupWithKey :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> Maybe (f v)) -> k2 v -> DMap k2 f -> (Maybe (f v), DMap k2 f) Source #

O(log n). Lookup and update. See also `updateWithKey`. The function returns changed value, if it is updated. Returns the original key value if the map entry is deleted.

alter :: forall {k1} k2 f (v :: k1). GCompare k2 => (Maybe (f v) -> Maybe (f v)) -> k2 v -> DMap k2 f -> DMap k2 f Source #

O(log n). The expression (``alter` f k map`) alters the value `x` at `k`, or absence thereof. `alter` can be used to insert, delete, or update a value in a `Map`. In short : ``lookup` k (`alter` f k m) = f (`lookup` k m)`.

alterF :: forall {k1} k2 f (v :: k1) g. (GCompare k2, Functor f) => k2 v -> (Maybe (g v) -> f (Maybe (g v))) -> DMap k2 g -> f (DMap k2 g) Source #

Works the same as `alter` except the new value is returned in some `Functor` `f`. In short : `(v' -> alter (const v') k dm) $ f (lookup k dm)`

# Combine

## Union

union :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => DMap k2 f -> DMap k2 f -> DMap k2 f 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``).

unionWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> f v -> f v) -> DMap k2 f -> DMap k2 f -> DMap k2 f Source #

O(n+m). Union with a combining function.

unions :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => [DMap k2 f] -> DMap k2 f Source #

The union of a list of maps: (``unions` == `foldl` `union` `empty``).

unionsWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> f v -> f v) -> [DMap k2 f] -> DMap k2 f Source #

The union of a list of maps, with a combining operation: (``unionsWithKey` f == `foldl` (`unionWithKey` f) `empty``).

## Difference

difference :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type) (g :: k1 -> Type). GCompare k2 => DMap k2 f -> DMap k2 g -> DMap k2 f Source #

O(m * log (n/m + 1)), m <= n. Difference of two maps. Return elements of the first map not existing in the second map.

differenceWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> g v -> Maybe (f v)) -> DMap k2 f -> DMap k2 g -> DMap k2 f Source #

O(n+m). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the key and both values. If it returns `Nothing`, the element is discarded (proper set difference). If it returns (``Just` y`), the element is updated with a new value `y`.

## Intersection

intersection :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => DMap k2 f -> DMap k2 f -> DMap k2 f Source #

O(m * log (n/m + 1), m <= n. Intersection of two maps. Return data in the first map for the keys existing in both maps. (``intersection` m1 m2 == `intersectionWith` `const` m1 m2`).

intersectionWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> g v -> h v) -> DMap k2 f -> DMap k2 g -> DMap k2 h Source #

O(m * log (n/m + 1), m <= n. Intersection with a combining function.

# Traversal

## Map

map :: forall {k1} f g (k2 :: k1 -> Type). (forall (v :: k1). f v -> g v) -> DMap k2 f -> DMap k2 g Source #

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

ffor :: forall {k1} (k2 :: k1 -> Type) f g. DMap k2 f -> (forall (v :: k1). f v -> g v) -> DMap k2 g Source #

O(n). ``ffor` == `flip` `map`` except we cannot actually use `flip` because of the lack of impredicative types.

mapWithKey :: (forall (v :: k1). k2 v -> f v -> g v) -> DMap k2 f -> DMap k2 g Source #

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

fforWithKey :: DMap k2 f -> (forall (v :: k1). k2 v -> f v -> g v) -> DMap k2 g Source #

O(n). ``fforWithKey` == `flip` `mapWithKey`` except we cannot actually use `flip` because of the lack of impredicative types.

traverseWithKey_ :: forall {k1} t k2 f. Applicative t => (forall (v :: k1). k2 v -> f v -> t ()) -> DMap k2 f -> t () 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.

forWithKey_ :: forall {k1} t k2 f. Applicative t => DMap k2 f -> (forall (v :: k1). k2 v -> f v -> t ()) -> t () Source #

O(n). ``forWithKey` == `flip` `traverseWithKey`` except we cannot actually use `flip` because of the lack of impredicative types.

traverseWithKey :: forall {k1} t k2 f g. Applicative t => (forall (v :: k1). k2 v -> f v -> t (g v)) -> DMap k2 f -> t (DMap k2 g) 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.

forWithKey :: forall {k1} t k2 f g. Applicative t => DMap k2 f -> (forall (v :: k1). k2 v -> f v -> t (g v)) -> t (DMap k2 g) Source #

O(n). ``forWithKey` == `flip` `traverseWithKey`` except we cannot actually use `flip` because of the lack of impredicative types.

mapAccumLWithKey :: (forall (v :: k1). a -> k2 v -> f v -> (a, g v)) -> a -> DMap k2 f -> (a, DMap k2 g) Source #

O(n). The function `mapAccumLWithKey` threads an accumulating argument through the map in ascending order of keys.

mapAccumRWithKey :: (forall (v :: k1). a -> k2 v -> f v -> (a, g v)) -> a -> DMap k2 f -> (a, DMap k2 g) Source #

O(n). The function `mapAccumRWithKey` threads an accumulating argument through the map in descending order of keys.

mapKeysWith :: GCompare k2 => (forall (v :: k). k2 v -> f v -> f v -> f v) -> (forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f Source #

O(n*log n). ``mapKeysWith` c f s` is the map obtained by applying `f` to each key of `s`.

The size of the result may be smaller if `f` maps two or more distinct keys to the same new key. In this case the associated values will be combined using `c`.

mapKeysMonotonic :: forall {k} k1 k2 (f :: k -> Type). (forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f Source #

O(n). ``mapKeysMonotonic` f s == `mapKeys` f s`, but works only when `f` is strictly monotonic. That is, for any values `x` and `y`, if `x` < `y` then `f x` < `f y`. The precondition is not checked. Semi-formally, we have:

    and [x < y ==> f x < f y | x <- ls, y <- ls]
                        ==> mapKeysMonotonic f s == mapKeys f s
        where ls = keys s

This means that `f` maps distinct original keys to distinct resulting keys. This function has better performance than `mapKeys`.

## Fold

foldWithKey :: (forall (v :: k1). k2 v -> f v -> b -> b) -> b -> DMap k2 f -> b Source #

Deprecated: Use foldrWithKey instead

O(n). Fold the keys and values in the map, such that ``foldWithKey` f z == `foldr` (`uncurry` f) z . `toAscList``.

This is identical to `foldrWithKey`, and you should use that one instead of this one. This name is kept for backward compatibility.

foldrWithKey :: (forall (v :: k1). k2 v -> f v -> b -> b) -> b -> DMap k2 f -> b Source #

O(n). Post-order fold. The function will be applied from the lowest value to the highest.

foldlWithKey :: (forall (v :: k1). b -> k2 v -> f v -> b) -> b -> DMap k2 f -> b Source #

O(n). Pre-order fold. The function will be applied from the highest value to the lowest.

# Conversion

keys :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> [Some k2] Source #

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

    keys (fromList [(5,"a"), (3,"b")]) == [3,5]
    keys empty == []

assocs :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> [DSum k2 f] Source #

O(n). Return all key/value pairs in the map in ascending key order.

## Lists

toList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> [DSum k2 f] Source #

O(n). Convert to a list of key/value pairs.

fromList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => [DSum k2 f] -> DMap k2 f Source #

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

fromListWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> f v -> f v) -> [DSum k2 f] -> DMap k2 f Source #

O(n*log n). Build a map from a list of key/value pairs with a combining function. See also `fromAscListWithKey`.

## Ordered lists

toAscList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> [DSum k2 f] Source #

O(n). Convert to an ascending list.

toDescList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> [DSum k2 f] Source #

O(n). Convert to a descending list.

fromAscList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GEq k2 => [DSum k2 f] -> DMap k2 f Source #

O(n). Build a map from an ascending list in linear time. The precondition (input list is ascending) is not checked.

fromAscListWithKey :: GEq k2 => (forall (v :: k1). k2 v -> f v -> f v -> f v) -> [DSum k2 f] -> DMap k2 f Source #

O(n). Build a map from an ascending list in linear time with a combining function for equal keys. The precondition (input list is ascending) is not checked.

fromDistinctAscList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). [DSum k2 f] -> DMap k2 f Source #

O(n). Build a map from an ascending list of distinct elements in linear time. The precondition is not checked.

# Filter

filter :: (a -> Bool) -> [a] -> [a] Source #

\(\mathcal{O}(n)\). `filter`, applied to a predicate and a list, returns the list of those elements that satisfy the predicate; i.e.,

    filter p xs = [ x | x <- xs, p x]

#### Examples

Expand

    >>> filter odd [1, 2, 3]
    [1,3]

    >>> filter (\l -> length l > 3) ["Hello", ", ", "World", "!"]
    ["Hello","World"]

    >>> filter (/= 3) [1, 2, 3, 4, 3, 2, 1]
    [1,2,4,2,1]

filterWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> Bool) -> DMap k2 f -> DMap k2 f Source #

O(n). Filter all keys/values that satisfy the predicate.

partitionWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> Bool) -> DMap k2 f -> (DMap k2 f, DMap k2 f) Source #

O(n). Partition the map according to a predicate. The first map contains all elements that satisfy the predicate, the second all elements that fail the predicate. See also `split`.

mapMaybe :: forall {k1} (k2 :: k1 -> Type) f g. GCompare k2 => (forall (v :: k1). f v -> Maybe (g v)) -> DMap k2 f -> DMap k2 g Source #

O(n). Map values and collect the `Just` results.

mapMaybeWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> Maybe (g v)) -> DMap k2 f -> DMap k2 g Source #

O(n). Map keys/values and collect the `Just` results.

mapEitherWithKey :: GCompare k2 => (forall (v :: k1). k2 v -> f v -> Either (g v) (h v)) -> DMap k2 f -> (DMap k2 g, DMap k2 h) Source #

O(n). Map keys/values and separate the `Left` and `Right` results.

split :: forall {k1} k2 (f :: k1 -> Type) (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> (DMap k2 f, DMap k2 f) Source #

O(log n). The expression (``split` k map`) is a pair `(map1,map2)` where the keys in `map1` are smaller than `k` and the keys in `map2` larger than `k`. Any key equal to `k` is found in neither `map1` nor `map2`.

splitLookup :: forall {k1} k2 f (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> (DMap k2 f, Maybe (f v), DMap k2 f) Source #

O(log n). The expression (``splitLookup` k map`) splits a map just like `split` but also returns ``lookup` k map`.

# Submap

isSubmapOf :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). (GCompare k2, Has' Eq k2 f) => DMap k2 f -> DMap k2 f -> Bool Source #

O(n+m). This function is defined as (``isSubmapOf` = `isSubmapOfBy` `eqTagged`)`).

isSubmapOfBy :: GCompare k2 => (forall (v :: k1). k2 v -> k2 v -> f v -> g v -> Bool) -> DMap k2 f -> DMap k2 g -> Bool Source #

O(n+m). The expression (``isSubmapOfBy` f t1 t2`) returns `True` if all keys in `t1` are in tree `t2`, and when `f` returns `True` when applied to their respective keys and values.

isProperSubmapOf :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). (GCompare k2, Has' Eq k2 f) => DMap k2 f -> DMap k2 f -> Bool Source #

O(n+m). Is this a proper submap? (ie. a submap but not equal). Defined as (``isProperSubmapOf` = `isProperSubmapOfBy` `eqTagged``).

isProperSubmapOfBy :: GCompare k2 => (forall (v :: k1). k2 v -> k2 v -> f v -> g v -> Bool) -> DMap k2 f -> DMap k2 g -> Bool Source #

O(n+m). Is this a proper submap? (ie. a submap but not equal). The expression (``isProperSubmapOfBy` f m1 m2`) returns `True` when `m1` and `m2` are not equal, all keys in `m1` are in `m2`, and when `f` returns `True` when applied to their respective keys and values.

# Indexed

lookupIndex :: forall {k1} k2 (f :: k1 -> Type) (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> Maybe Int Source #

O(log n). Lookup the index of a key. The index is a number from 0 up to, but not including, the `size` of the map.

findIndex :: forall {k1} k2 (v :: k1) (f :: k1 -> Type). GCompare k2 => k2 v -> DMap k2 f -> Int Source #

O(log n). Return the index of a key. The index is a number from 0 up to, but not including, the `size` of the map. Calls `error` when the key is not a `member` of the map.

elemAt :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). Int -> DMap k2 f -> DSum k2 f Source #

O(log n). Retrieve an element by index. Calls `error` when an invalid index is used.

updateAt :: (forall (v :: k1). k2 v -> f v -> Maybe (f v)) -> Int -> DMap k2 f -> DMap k2 f Source #

O(log n). Update the element at index. Does nothing when an invalid index is used.

deleteAt :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). Int -> DMap k2 f -> DMap k2 f Source #

O(log n). Delete the element at index. Defined as (``deleteAt` i map = `updateAt` (k x -> `Nothing`) i map`).

# Min/Max

findMin :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> DSum k2 f Source #

O(log n). The minimal key of the map. Calls `error` is the map is empty.

findMax :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> DSum k2 f Source #

O(log n). The maximal key of the map. Calls `error` is the map is empty.

lookupMin :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Maybe (DSum k2 f) Source #

lookupMax :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Maybe (DSum k2 f) Source #

deleteMin :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> DMap k2 f Source #

O(log n). Delete the minimal key. Returns an empty map if the map is empty.

deleteMax :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> DMap k2 f Source #

O(log n). Delete the maximal key. Returns an empty map if the map is empty.

deleteFindMin :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> (DSum k2 f, DMap k2 f) Source #

O(log n). Delete and find the minimal element.

    deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")])
    deleteFindMin                                            Error: can not return the minimal element of an empty map

deleteFindMax :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> (DSum k2 f, DMap k2 f) Source #

O(log n). Delete and find the maximal element.

    deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")])
    deleteFindMax empty                                      Error: can not return the maximal element of an empty map

updateMinWithKey :: (forall (v :: k1). k2 v -> f v -> Maybe (f v)) -> DMap k2 f -> DMap k2 f Source #

O(log n). Update the value at the minimal key.

updateMaxWithKey :: (forall (v :: k1). k2 v -> f v -> Maybe (f v)) -> DMap k2 f -> DMap k2 f Source #

O(log n). Update the value at the maximal key.

minViewWithKey :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Maybe (DSum k2 f, DMap k2 f) Source #

O(log n). Retrieves the minimal (key :=> value) entry of the map, and the map stripped of that element, or `Nothing` if passed an empty map.

maxViewWithKey :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Maybe (DSum k2 f, DMap k2 f) Source #

O(log n). Retrieves the maximal (key :=> value) entry of the map, and the map stripped of that element, or `Nothing` if passed an empty map.

# Debugging

showTree :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). (GShow k2, Has' Show k2 f) => DMap k2 f -> String Source #

O(n). Show the tree that implements the map. The tree is shown in a compressed, hanging format. See `showTreeWith`.

showTreeWith :: (forall (v :: k1). k2 v -> f v -> String) -> Bool -> Bool -> DMap k2 f -> String Source #

O(n). The expression (``showTreeWith` showelem hang wide map`) shows the tree that implements the map. Elements are shown using the `showElem` function. If `hang` is `True`, a hanging tree is shown otherwise a rotated tree is shown. If `wide` is `True`, an extra wide version is shown.

valid :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => DMap k2 f -> Bool Source #

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

# Orphan instances

GCompare k2 => Monoid (DMap k2 f) Source # |
Instance details Methods mempty :: DMap k2 f Source # mappend :: DMap k2 f -> DMap k2 f -> DMap k2 f Source # mconcat :: [DMap k2 f] -> DMap k2 f Source #
GCompare k2 => Semigroup (DMap k2 f) Source # |
Instance details Methods (<>) :: DMap k2 f -> DMap k2 f -> DMap k2 f Source # sconcat :: NonEmpty (DMap k2 f) -> DMap k2 f Source # stimes :: Integral b => b -> DMap k2 f -> DMap k2 f Source #
(GCompare k2, GRead k2, Has' Read k2 f) => Read (DMap k2 f) Source # |
Instance details Methods readsPrec :: Int -> ReadS (DMap k2 f) Source # readList :: ReadS [DMap k2 f] Source # readPrec :: ReadPrec (DMap k2 f) Source # readListPrec :: ReadPrec [DMap k2 f] Source #
(GShow k2, Has' Show k2 f) => Show (DMap k2 f) Source # |
Instance details Methods showsPrec :: Int -> DMap k2 f -> ShowS Source # show :: DMap k2 f -> String Source # showList :: [DMap k2 f] -> ShowS Source #
(GEq k2, Has' Eq k2 f) => Eq (DMap k2 f) Source # |
Instance details Methods (==) :: DMap k2 f -> DMap k2 f -> Bool Source # (/=) :: DMap k2 f -> DMap k2 f -> Bool Source #
(GCompare k2, Has' Eq k2 f, Has' Ord k2 f) => Ord (DMap k2 f) Source # |
Instance details Methods compare :: DMap k2 f -> DMap k2 f -> Ordering Source # (<) :: DMap k2 f -> DMap k2 f -> Bool Source # (<=) :: DMap k2 f -> DMap k2 f -> Bool Source # (>) :: DMap k2 f -> DMap k2 f -> Bool Source # (>=) :: DMap k2 f -> DMap k2 f -> Bool Source # max :: DMap k2 f -> DMap k2 f -> DMap k2 f Source # min :: DMap k2 f -> DMap k2 f -> DMap k2 f Source #