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

Safe Haskell | Safe
Language | Haskell2010

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

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 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 #

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 #