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

Data.Dependent.Map.Internal

Synopsis

# Documentation

data DMap k f where 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 Tags 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.

Constructors

 Tip :: DMap k f Bin :: !Int -> !(k v) -> f v -> !(DMap k f) -> !(DMap k f) -> DMap k f
Instances

empty :: DMap k f Source #

O(1). The empty map.

empty      == fromList []
size empty == 0

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

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

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

null :: DMap k f -> Bool Source #

O(1). Is the map empty?

size :: DMap k f -> Int Source #

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

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

lookupAssoc :: forall k f v. GCompare k => Some k -> DMap k f -> Maybe (DSum k f) Source #

combine :: GCompare k => k v -> f v -> DMap k f -> DMap k f -> DMap k f Source #

insertMax :: k v -> f v -> DMap k f -> DMap k f Source #

insertMin :: k v -> f v -> DMap k f -> DMap k f Source #

merge :: DMap k f -> DMap k f -> DMap k f Source #

glue :: DMap k f -> DMap k f -> DMap k f Source #

deleteFindMin :: DMap k f -> (DSum k f, DMap k 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

data a :*: b infixr 1 Source #

A strict pair.

Constructors

 !a :*: !b infixr 1

toPair :: (a :*: b) -> (a, b) Source #

Convert a strict pair to a pair.

data Triple' a b c Source #

Constructors

 Triple' !a !b !c

toTriple :: Triple' a b c -> (a, b, c) Source #

Convert a strict triple to a triple.

minViewWithKey :: forall k f. DMap k f -> Maybe (DSum k f, DMap k 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 k f. DMap k f -> Maybe (DSum k f, DMap k 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.

deleteFindMax :: DMap k f -> (DSum k f, DMap k 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

balance :: k v -> f v -> DMap k f -> DMap k f -> DMap k f Source #

rotateL :: k v -> f v -> DMap k f -> DMap k f -> DMap k f Source #

rotateR :: k v -> f v -> DMap k f -> DMap k f -> DMap k f Source #

singleL :: k v -> f v -> DMap k f -> DMap k f -> DMap k f Source #

singleR :: k v -> f v -> DMap k f -> DMap k f -> DMap k f Source #

doubleL :: k v -> f v -> DMap k f -> DMap k f -> DMap k f Source #

doubleR :: k v -> f v -> DMap k f -> DMap k f -> DMap k f Source #

bin :: k v -> f v -> DMap k f -> DMap k f -> DMap k f Source #

trim :: (Some k -> Ordering) -> (Some k -> Ordering) -> DMap k f -> DMap k f Source #

trimLookupLo :: GCompare k => Some k -> (Some k -> Ordering) -> DMap k f -> (Maybe (DSum k f), DMap k f) Source #

filterGt :: GCompare k => (Some k -> Ordering) -> DMap k f -> DMap k f Source #

filterLt :: GCompare k => (Some k -> Ordering) -> DMap k f -> DMap k f Source #