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

Data.Dependent.Map

Synopsis

# Documentation

data DMap k Source

Dependent maps: f 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 `f`, as are `Tag`s from Data.Dependent.Tag.

Semantically, `DMap f` is equivalent to a set of `DSum 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

 EqTag k => Eq (DMap k) OrdTag k => Ord (DMap k) (GCompare * f, ReadTag f) => Read (DMap f) ShowTag k => Show (DMap k) GCompare * k => Monoid (DMap k) Typeable ((* -> *) -> *) DMap

data DSum tag :: (* -> *) -> * where

A basic dependent sum type; the first component is a tag that specifies the type of the second; for example, think of a GADT such as:

```data Tag a where
AString :: Tag String
AnInt   :: Tag Int```

Then, we have the following valid expressions of type `DSum Tag`:

```AString :=> "hello!"
AnInt   :=> 42```

And we can write functions that consume `DSum Tag` values by matching, such as:

```toString :: DSum Tag -> String
toString (AString :=> str) = str
toString (AnInt   :=> int) = show int```

By analogy to the (key => value) construction for dictionary entries in many dynamic languages, we use (key :=> value) as the constructor for dependent sums. The :=> operator has very low precedence and binds to the right, so if the `Tag` GADT is extended with an additional constructor `Rec :: Tag (DSum Tag)`, then `Rec :=> AnInt :=> 3 + 4` is parsed as would be expected (`Rec :=> (AnInt :=> (3 + 4))`) and has type `DSum Tag`. Its precedence is just above that of `\$`, so `foo bar \$ AString :=> "eep"` is equivalent to `foo bar (AString :=> "eep")`.

Constructors

 (:=>) :: !(tag a) -> a -> DSum tag infixr 1

Instances

 EqTag tag => Eq (DSum tag) OrdTag tag => Ord (DSum tag) ReadTag tag => Read (DSum tag) ShowTag tag => Show (DSum tag) Typeable ((* -> *) -> *) DSum

data Key f where Source

A `Key` is just a wrapper for the true key type `f` which hides the associated value type and presents the key's GADT-level `GCompare` instance as a vanilla `Ord` instance so it can be used in cases where we don't care about the associated value.

Constructors

 Key :: !(f a) -> Key f

Instances

 GEq * f => Eq (Key f) GCompare * f => Ord (Key f) GRead f => Read (Key f) GShow f => Show (Key f)

class GEq k f => GCompare f where

Type class for orderable GADT-like structures. When 2 things are equal, must return a witness that their parameter types are equal as well (GEQ). |Type class for comparable GADT-like structures. When 2 things are equal, must return a witness that their parameter types are equal as well (`GEQ`).

Methods

gcompare :: f a -> f b -> GOrdering k a b

Instances

 GCompare k ((:=) k a)

data GOrdering a b :: k -> k -> * where

A type for the result of comparing GADT constructors; the type parameters of the GADT values being compared are included so that in the case where they are equal their parameter types can be unified.

Constructors

 GLT :: GOrdering k a b GEQ :: GOrdering k t t GGT :: GOrdering k a b

Instances

 Show a => ShowTag (GOrdering * a) GShow (GOrdering * a) GRead (GOrdering * a) Typeable (k -> k -> *) (GOrdering k) Eq (GOrdering k a b) Ord (GOrdering k a b) Show (GOrdering k a b)

# Operators

(!) :: GCompare k => DMap k -> k v -> 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'```

(\\) :: GCompare k => DMap k -> DMap k -> DMap k infixl 9 Source

Same as `difference`.

# Query

null :: DMap k -> Bool Source

O(1). Is the map empty?

size :: DMap k -> Int Source

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

member :: GCompare k => k a -> DMap k -> Bool Source

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

notMember :: GCompare k => k v -> DMap k -> Bool Source

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

lookup :: forall k v. GCompare k => k v -> DMap k -> Maybe 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 :: GCompare k => v -> k v -> DMap k -> 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

O(1). The empty map.

```empty      == fromList []
size empty == 0```

singleton :: k v -> v -> DMap k Source

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

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

## Insertion

insert :: forall k v. GCompare k => k v -> v -> DMap k -> DMap k 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 :: GCompare k => (v -> v -> v) -> k v -> v -> DMap k -> DMap k 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' :: GCompare k => (v -> v -> v) -> k v -> v -> DMap k -> DMap k Source

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

insertWithKey :: forall k v. GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> DMap k 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 k v. GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> DMap k Source

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

insertLookupWithKey :: forall k v. GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> (Maybe v, DMap k) 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 k v. GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> (Maybe v, DMap k) Source

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

## Delete/Update

delete :: forall k v. GCompare k => k v -> DMap k -> DMap k 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 :: GCompare k => (v -> v) -> k v -> DMap k -> DMap k 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 :: GCompare k => (k v -> v -> v) -> k v -> DMap k -> DMap k 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.

update :: GCompare k => (v -> Maybe v) -> k v -> DMap k -> DMap k 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 k v. GCompare k => (k v -> v -> Maybe v) -> k v -> DMap k -> DMap k 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 k v. GCompare k => (k v -> v -> Maybe v) -> k v -> DMap k -> (Maybe v, DMap k) 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 k v. GCompare k => (Maybe v -> Maybe v) -> k v -> DMap k -> DMap k 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)`.

# Combine

## Union

union :: GCompare k => DMap k -> DMap k -> DMap k Source

O(n+m). 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`). The implementation uses the efficient hedge-union algorithm. Hedge-union is more efficient on (bigset ``union`` smallset).

unionWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> DMap k -> DMap k -> DMap k Source

O(n+m). Union with a combining function. The implementation uses the efficient hedge-union algorithm. Hedge-union is more efficient on (bigset ``union`` smallset).

unions :: GCompare k => [DMap k] -> DMap k Source

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

unionsWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> [DMap k] -> DMap k Source

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

## Difference

difference :: GCompare k => DMap k -> DMap k -> DMap k Source

O(n+m). Difference of two maps. Return elements of the first map not existing in the second map. The implementation uses an efficient hedge algorithm comparable with hedge-union.

differenceWithKey :: GCompare k => (forall v. k v -> v -> v -> Maybe v) -> DMap k -> DMap k -> DMap k 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`. The implementation uses an efficient hedge algorithm comparable with hedge-union.

## Intersection

intersection :: GCompare k => DMap k -> DMap k -> DMap k Source

O(n+m). 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 k => (forall v. k v -> v -> v -> v) -> DMap k -> DMap k -> DMap k Source

O(n+m). Intersection with a combining function. Intersection is more efficient on (bigset ``intersection`` smallset).

# Traversal

## Map

mapWithKey :: (forall v. k v -> v -> v) -> DMap k -> DMap k Source

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

mapAccumLWithKey :: (forall v. a -> k v -> v -> (a, v)) -> a -> DMap k -> (a, DMap k) Source

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

mapAccumRWithKey :: (forall v. a -> k v -> v -> (a, v)) -> a -> DMap k -> (a, DMap k) Source

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

mapKeysWith :: GCompare k2 => (forall v. k2 v -> v -> v -> v) -> (forall v. k1 v -> k2 v) -> DMap k1 -> DMap k2 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 v. k1 v -> k2 v) -> DMap k1 -> DMap k2 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. k v -> v -> b -> b) -> b -> DMap k -> b Source

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. k v -> v -> b -> b) -> b -> DMap k -> b Source

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

foldlWithKey :: (forall v. b -> k v -> v -> b) -> b -> DMap k -> b Source

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

# Conversion

keys :: DMap k -> [Key k] Source

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

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

assocs :: DMap k -> [DSum k] Source

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

## Lists

toList :: DMap k -> [DSum k] Source

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

fromList :: GCompare k => [DSum k] -> DMap k 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 k => (forall v. k v -> v -> v -> v) -> [DSum k] -> DMap k 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 :: DMap k -> [DSum k] Source

O(n). Convert to an ascending list.

toDescList :: DMap k -> [DSum k] Source

O(n). Convert to a descending list.

fromAscList :: GEq k => [DSum k] -> DMap k Source

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

fromAscListWithKey :: GEq k => (forall v. k v -> v -> v -> v) -> [DSum k] -> DMap k 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 :: [DSum k] -> DMap k 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]

`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]`

filterWithKey :: GCompare k => (forall v. k v -> v -> Bool) -> DMap k -> DMap k Source

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

partitionWithKey :: GCompare k => (forall v. k v -> v -> Bool) -> DMap k -> (DMap k, DMap k) 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`.

mapMaybeWithKey :: GCompare k => (forall v. k v -> v -> Maybe v) -> DMap k -> DMap k Source

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

mapEitherWithKey :: GCompare k => (forall v. k v -> v -> Either v v) -> DMap k -> (DMap k, DMap k) Source

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

split :: forall k v. GCompare k => k v -> DMap k -> (DMap k, DMap k) 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 k v. GCompare k => k v -> DMap k -> (DMap k, Maybe v, DMap k) Source

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

# Submap

isSubmapOf :: (GCompare k, EqTag k) => DMap k -> DMap k -> Bool Source

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

isSubmapOfBy :: GCompare k => (forall v. k v -> k v -> v -> v -> Bool) -> DMap k -> DMap k -> 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 :: (GCompare k, EqTag k) => DMap k -> DMap k -> Bool Source

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

isProperSubmapOfBy :: GCompare k => (forall v. k v -> k v -> v -> v -> Bool) -> DMap k -> DMap k -> 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 k v. GCompare k => k v -> DMap k -> 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 :: GCompare k => k v -> DMap k -> 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 :: Int -> DMap k -> DSum k Source

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

updateAt :: (forall v. k v -> v -> Maybe v) -> Int -> DMap k -> DMap k Source

O(log n). Update the element at index. Calls `error` when an invalid index is used.

deleteAt :: Int -> DMap k -> DMap k Source

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

# Min/Max

findMin :: DMap k -> DSum k Source

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

findMax :: DMap k -> DSum k Source

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

deleteMin :: DMap k -> DMap k Source

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

deleteMax :: DMap k -> DMap k Source

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

deleteFindMin :: DMap k -> (DSum k, DMap k) 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 :: DMap k -> (DSum k, DMap k) 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. k v -> v -> Maybe v) -> DMap k -> DMap k Source

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

updateMaxWithKey :: (forall v. k v -> v -> Maybe v) -> DMap k -> DMap k Source

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

minViewWithKey :: DMap k -> Maybe (DSum k, DMap k) 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 :: DMap k -> Maybe (DSum k, DMap k) 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 :: ShowTag k => DMap k -> 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. k v -> v -> String) -> Bool -> Bool -> DMap k -> 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 :: GCompare k => DMap k -> Bool Source

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