Safe Haskell	Safe
Language	Haskell98

Data.Dependent.Map.Internal

Synopsis

data DMap (k1 :: k -> Type) (f :: k -> Type) where
- Tip :: forall {k} (k1 :: k -> Type) (f :: k -> Type). DMap k1 f
- Bin :: forall {k} (k1 :: k -> Type) (v :: k) (f :: k -> Type). !Int -> !(k1 v) -> f v -> !(DMap k1 f) -> !(DMap k1 f) -> DMap k1 f
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
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
lookup :: forall {k1} k2 f (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> Maybe (f v)
lookupAssoc :: forall {k1} {k2} (k3 :: k1 -> Type) (f :: k1 -> Type) (v :: k2). GCompare k3 => Some k3 -> DMap k3 f -> Maybe (DSum k3 f)
combine :: forall {k1} k2 (v :: k1) f. GCompare k2 => k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
insertMax :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f
insertMin :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f
merge :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> DMap k2 f -> DMap k2 f
glue :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> DMap k2 f -> DMap k2 f
deleteFindMin :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> (DSum k2 f, DMap k2 f)
data a :*: b = !a :*: !b
toPair :: (a :*: b) -> (a, b)
data Triple' a b c = Triple' !a !b !c
toTriple :: Triple' a b c -> (a, b, c)
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)
deleteFindMax :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> (DSum k2 f, DMap k2 f)
delta :: Int
ratio :: Int
balance :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
rotateL :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
rotateR :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
singleL :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
singleR :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
doubleL :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
doubleR :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
bin :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
trim :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). (Some k2 -> Ordering) -> (Some k2 -> Ordering) -> DMap k2 f -> DMap k2 f
trimLookupLo :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => Some k2 -> (Some k2 -> Ordering) -> DMap k2 f -> (Maybe (DSum k2 f), DMap k2 f)
filterGt :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => (Some k2 -> Ordering) -> DMap k2 f -> DMap k2 f
filterLt :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => (Some k2 -> Ordering) -> DMap k2 f -> DMap k2 f

Documentation

data DMap (k1 :: k -> Type) (f :: k -> Type) 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 :: forall {k} (k1 :: k -> Type) (f :: k -> Type). DMap k1 f
Bin :: forall {k} (k1 :: k -> Type) (v :: k) (f :: k -> Type). !Int -> !(k1 v) -> f v -> !(DMap k1 f) -> !(DMap k1 f) -> DMap k1 f

Instances

Instances details

GCompare k2 => Monoid (DMap k2 f) Source #
Instance details Defined in Data.Dependent.Map Methods mempty :: DMap k2 f # mappend :: DMap k2 f -> DMap k2 f -> DMap k2 f # mconcat :: [DMap k2 f] -> DMap k2 f #
GCompare k2 => Semigroup (DMap k2 f) Source #
Instance details Defined in Data.Dependent.Map Methods (<>) :: DMap k2 f -> DMap k2 f -> DMap k2 f # sconcat :: NonEmpty (DMap k2 f) -> DMap k2 f # stimes :: Integral b => b -> DMap k2 f -> DMap k2 f #
(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) # readList :: ReadS [DMap k2 f] # readPrec :: ReadPrec (DMap k2 f) # readListPrec :: ReadPrec [DMap k2 f] #
(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 # show :: DMap k2 f -> String # showList :: [DMap k2 f] -> ShowS #
(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 # (/=) :: DMap k2 f -> DMap k2 f -> Bool #
(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 # (<) :: DMap k2 f -> DMap k2 f -> Bool # (<=) :: DMap k2 f -> DMap k2 f -> Bool # (>) :: DMap k2 f -> DMap k2 f -> Bool # (>=) :: DMap k2 f -> DMap k2 f -> Bool # max :: DMap k2 f -> DMap k2 f -> DMap k2 f # min :: DMap k2 f -> DMap k2 f -> DMap k2 f #

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

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.

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.

lookupAssoc :: forall {k1} {k2} (k3 :: k1 -> Type) (f :: k1 -> Type) (v :: k2). GCompare k3 => Some k3 -> DMap k3 f -> Maybe (DSum k3 f) Source #

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

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

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

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

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

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

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 {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.

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

delta :: Int Source #

ratio :: Int Source #

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

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

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

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

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

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

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

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

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

trimLookupLo :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => Some k2 -> (Some k2 -> Ordering) -> DMap k2 f -> (Maybe (DSum k2 f), DMap k2 f) Source #

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

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