- data DMap k
- data DSum tag where
- data Key f where
- class GEq f => GCompare f where
- data GOrdering a b where
- (!) :: GCompare k => DMap k -> k v -> v
- (\\) :: GCompare k => DMap k -> DMap k -> DMap k
- null :: DMap k -> Bool
- size :: DMap k -> Int
- member :: GCompare k => k a -> DMap k -> Bool
- notMember :: GCompare k => k v -> DMap k -> Bool
- lookup :: forall k v. GCompare k => k v -> DMap k -> Maybe v
- findWithDefault :: GCompare k => v -> k v -> DMap k -> v
- empty :: DMap k
- singleton :: k v -> v -> DMap k
- insert :: forall k v. GCompare k => k v -> v -> DMap k -> DMap k
- insertWith :: GCompare k => (v -> v -> v) -> k v -> v -> DMap k -> DMap k
- insertWith' :: GCompare k => (v -> v -> v) -> k v -> v -> DMap k -> DMap k
- insertWithKey :: forall k v. GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> DMap k
- insertWithKey' :: forall k v. GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> DMap k
- insertLookupWithKey :: forall k v. GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> (Maybe v, DMap k)
- insertLookupWithKey' :: forall k v. GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> (Maybe v, DMap k)
- delete :: forall k v. GCompare k => k v -> DMap k -> DMap k
- adjust :: GCompare k => (v -> v) -> k v -> DMap k -> DMap k
- adjustWithKey :: GCompare k => (k v -> v -> v) -> k v -> DMap k -> DMap k
- update :: GCompare k => (v -> Maybe v) -> k v -> DMap k -> DMap k
- updateWithKey :: forall k v. GCompare k => (k v -> v -> Maybe v) -> k v -> DMap k -> DMap k
- updateLookupWithKey :: forall k v. GCompare k => (k v -> v -> Maybe v) -> k v -> DMap k -> (Maybe v, DMap k)
- alter :: forall k v. GCompare k => (Maybe v -> Maybe v) -> k v -> DMap k -> DMap k
- union :: GCompare k => DMap k -> DMap k -> DMap k
- unionWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> DMap k -> DMap k -> DMap k
- unions :: GCompare k => [DMap k] -> DMap k
- unionsWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> [DMap k] -> DMap k
- difference :: GCompare k => DMap k -> DMap k -> DMap k
- differenceWithKey :: GCompare k => (forall v. k v -> v -> v -> Maybe v) -> DMap k -> DMap k -> DMap k
- intersection :: GCompare k => DMap k -> DMap k -> DMap k
- intersectionWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> DMap k -> DMap k -> DMap k
- mapWithKey :: (forall v. k v -> v -> v) -> DMap k -> DMap k
- mapAccumLWithKey :: (forall v. a -> k v -> v -> (a, v)) -> a -> DMap k -> (a, DMap k)
- mapAccumRWithKey :: (forall v. a -> k v -> v -> (a, v)) -> a -> DMap k -> (a, DMap k)
- mapKeysWith :: GCompare k2 => (forall v. k2 v -> v -> v -> v) -> (forall v. k1 v -> k2 v) -> DMap k1 -> DMap k2
- mapKeysMonotonic :: (forall v. k1 v -> k2 v) -> DMap k1 -> DMap k2
- foldWithKey :: (forall v. k v -> v -> b -> b) -> b -> DMap k -> b
- foldrWithKey :: (forall v. k v -> v -> b -> b) -> b -> DMap k -> b
- foldlWithKey :: (forall v. b -> k v -> v -> b) -> b -> DMap k -> b
- keys :: DMap k -> [Key k]
- assocs :: DMap k -> [DSum k]
- toList :: DMap k -> [DSum k]
- fromList :: GCompare k => [DSum k] -> DMap k
- fromListWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> [DSum k] -> DMap k
- toAscList :: DMap k -> [DSum k]
- toDescList :: DMap k -> [DSum k]
- fromAscList :: GEq k => [DSum k] -> DMap k
- fromAscListWithKey :: GEq k => (forall v. k v -> v -> v -> v) -> [DSum k] -> DMap k
- fromDistinctAscList :: [DSum k] -> DMap k
- filter :: (a -> Bool) -> [a] -> [a]
- filterWithKey :: GCompare k => (forall v. k v -> v -> Bool) -> DMap k -> DMap k
- partitionWithKey :: GCompare k => (forall v. k v -> v -> Bool) -> DMap k -> (DMap k, DMap k)
- mapMaybeWithKey :: GCompare k => (forall v. k v -> v -> Maybe v) -> DMap k -> DMap k
- mapEitherWithKey :: GCompare k => (forall v. k v -> v -> Either v v) -> DMap k -> (DMap k, DMap k)
- split :: forall k v. GCompare k => k v -> DMap k -> (DMap k, DMap k)
- splitLookup :: forall k v. GCompare k => k v -> DMap k -> (DMap k, Maybe v, DMap k)
- isSubmapOf :: (GCompare k, EqTag k) => DMap k -> DMap k -> Bool
- isSubmapOfBy :: GCompare k => (forall v. k v -> k v -> v -> v -> Bool) -> DMap k -> DMap k -> Bool
- isProperSubmapOf :: (GCompare k, EqTag k) => DMap k -> DMap k -> Bool
- isProperSubmapOfBy :: GCompare k => (forall v. k v -> k v -> v -> v -> Bool) -> DMap k -> DMap k -> Bool
- lookupIndex :: forall k v. GCompare k => k v -> DMap k -> Maybe Int
- findIndex :: GCompare k => k v -> DMap k -> Int
- elemAt :: Int -> DMap k -> DSum k
- updateAt :: (forall v. k v -> v -> Maybe v) -> Int -> DMap k -> DMap k
- deleteAt :: Int -> DMap k -> DMap k
- findMin :: DMap k -> DSum k
- findMax :: DMap k -> DSum k
- deleteMin :: DMap k -> DMap k
- deleteMax :: DMap k -> DMap k
- deleteFindMin :: DMap k -> (DSum k, DMap k)
- deleteFindMax :: DMap k -> (DSum k, DMap k)
- updateMinWithKey :: (forall v. k v -> v -> Maybe v) -> DMap k -> DMap k
- updateMaxWithKey :: (forall v. k v -> v -> Maybe v) -> DMap k -> DMap k
- minViewWithKey :: DMap k -> Maybe (DSum k, DMap k)
- maxViewWithKey :: DMap k -> Maybe (DSum k, DMap k)
- showTree :: ShowTag k => DMap k -> String
- showTreeWith :: (forall v. k v -> v -> String) -> Bool -> Bool -> DMap k -> String
- valid :: GCompare k => DMap k -> Bool
Documentation
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,
is equivalent to a set of DMap
f
where no two
elements have the same tag.
DSum
f
More informally, DMap
is to dependent products as M.Map
is to (->)
.
Thus it could also be thought of as a partial (in the sense of "partial
function") dependent product.
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)
.
class GEq 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
).
data GOrdering a b 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.
Operators
(!) :: GCompare k => DMap k -> k v -> vSource
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'
Query
member :: GCompare k => k a -> DMap k -> BoolSource
O(log n). Is the key a member of the map? See also notMember
.
notMember :: GCompare k => k v -> DMap k -> BoolSource
O(log n). Is the key not a member of the map? See also member
.
findWithDefault :: GCompare k => v -> k v -> DMap k -> vSource
O(log n). The expression (
returns
the value at key findWithDefault
def k map)k
or returns default value def
when the key is not in the map.
Construction
singleton :: k v -> v -> DMap kSource
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 kSource
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 kSource
O(log n). Insert with a function, combining new value and old value.
will insert the entry insertWith
f key value mpkey :=> 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 kSource
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 kSource
O(log n). Insert with a function, combining key, new value and old value.
will insert the entry insertWithKey
f key value mpkey :=> 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 kSource
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 (
)
is a pair where the first element is equal to (insertLookupWithKey
f k x map
)
and the second element equal to (lookup
k map
).
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 kSource
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 kSource
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 kSource
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.
updateWithKey :: forall k v. GCompare k => (k v -> v -> Maybe v) -> k v -> DMap k -> DMap kSource
O(log n). The expression (
) updates the
value updateWithKey
f k mapx
at k
(if it is in the map). If (f k x
) is Nothing
,
the element is deleted. If it is (
), the key Just
yk
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.
Combine
Union
unionWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> DMap k -> DMap k -> DMap kSource
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).
unionsWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> [DMap k] -> DMap kSource
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 kSource
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 kSource
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 (
), the element is updated with a new value Just
yy
.
The implementation uses an efficient hedge algorithm comparable with hedge-union.
Intersection
intersection :: GCompare k => DMap k -> DMap k -> DMap kSource
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 kSource
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 kSource
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 k2Source
O(n*log n).
is the map obtained by applying mapKeysWith
c f sf
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 k2Source
O(n).
, but works only when mapKeysMonotonic
f s == mapKeys
f sf
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 -> bSource
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 -> bSource
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 -> bSource
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
fromList :: GCompare k => [DSum k] -> DMap kSource
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 kSource
O(n*log n). Build a map from a list of key/value pairs with a combining function. See also fromAscListWithKey
.
Ordered lists
toDescList :: DMap k -> [DSum k]Source
O(n). Convert to a descending list.
fromAscList :: GEq k => [DSum k] -> DMap kSource
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 kSource
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 kSource
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 kSource
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 kSource
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
split :: forall k v. GCompare k => k v -> DMap k -> (DMap k, DMap k)Source
O(log n). The expression (
) is a pair split
k map(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 (
) splits a map just
like splitLookup
k mapsplit
but also returns
.
lookup
k map
Submap
isSubmapOf :: (GCompare k, EqTag k) => DMap k -> DMap k -> BoolSource
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 -> BoolSource
O(n+m).
The expression (
) returns isSubmapOfBy
f t1 t2True
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 -> BoolSource
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 -> BoolSource
O(n+m). Is this a proper submap? (ie. a submap but not equal).
The expression (
) returns isProperSubmapOfBy
f m1 m2True
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 IntSource
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.
elemAt :: Int -> DMap k -> DSum kSource
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 kSource
O(log n). Update the element at index. Calls error
when an
invalid index is used.
Min/Max
findMin :: DMap k -> DSum kSource
O(log n). The minimal key of the map. Calls error
is the map is empty.
findMax :: DMap k -> DSum kSource
O(log n). The maximal key of the map. Calls error
is the map is empty.
deleteMin :: DMap k -> DMap kSource
O(log n). Delete the minimal key. Returns an empty map if the map is empty.
deleteMax :: DMap k -> DMap kSource
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 kSource
O(log n). Update the value at the minimal key.
updateMaxWithKey :: (forall v. k v -> v -> Maybe v) -> DMap k -> DMap kSource
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 -> StringSource
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 -> StringSource
O(n). The expression (
) shows
the tree that implements the map. Elements are shown using the showTreeWith
showelem hang wide mapshowElem
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.