TrieMap-0.0.1.2: An implementation of generalized tries with sophisticated map type inference.

TrieMap

Description

We will use the following terminology:

An algebraic type is a type isomorphic to an algebraic type, as defined in the package description. This isomorphism is declared via the type class `Algebraic`, where `AlgRep k` is algebraic. It is assumed for purposes of ordering that this isomorphism is order- and equality-preserving. We also require that if `k` is algebraic, `AlgRep k ~ k`.

These methods will automatically infer the correct type of a `TrieMap` on any given argument. For example,

``fromList` [(("alphabet", `Just` (0.2 :: `Double`), `True`), "wxyz")]`

returns a variable of type

``TrieMap` (`String`, `Double`, `Bool`) (`ProdMap` (`ConstMap` (`RadixTrie` `Int` `IntMap`)) (`ProdMap` (`ConstMap` (`UnionMap` (`ConstMap` `Maybe`) `IdMap` (`Ordered` `Double`) (`Map` `Double`))) `IdMap`) ((`Const` () :+: `Id`) '()') (`UnionMap` (`ConstMap` `Maybe`) `IdMap` () `Maybe`)) `String``

The inference was done entirely automatically. Note also:

• `AlgRep Char ~ Int`: the `Algebraic` instance for `Char` maps characters to their ASCII representations, so an `IntMap` can be used.
• `AlgRep (Maybe a) ~ Either () (AlgRep a)`; a `TrieMap` on a `Maybe` key type simply gets a space for one extra (possible) value.
• `AlgRep Double ~ Ordered Double`; the `Algebraic` instance for `Double` tells TrieMap to just use a regular `Map` and the default ordering for `Double`s.
• `AlgRep Bool ~ Either () ()`, so a `TrieMap` on a `Bool` takes the form of -- essentially -- a pair of `Maybe`s.
• `AlgRep (a, b, c) ~ (AlgRep a, (AlgRep b, AlgRep c))`, so tuple types get handled by a sequence of map products.

(If you plan to use these maps in type arguments, it is strongly suggested that you either reproduce the context `(Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a`, or you create a type alias!)

Synopsis

# Map type

data TrieMap k m a Source

A `TrieMap` is a size-tracking wrapper around a generalized trie map.

Instances

 TrieKey k' m => Functor (TrieMap k m) TrieKey k' m => Foldable (TrieMap k m) TrieKey k' m => Traversable (TrieMap k m) SAlgebraicT m => AlgebraicT (TrieMap k m) (Eq k, Eq a, Algebraic k, TrieKey (AlgRep k) m) => Eq (TrieMap k m a) (Ord k, Ord a, Algebraic k, TrieKey (AlgRep k) m) => Ord (TrieMap k m a) (Show k, Show a, Algebraic k, TrieKey (AlgRep k) m) => Show (TrieMap k m a) (Algebraic k, TrieKey (AlgRep k) m) => Monoid (TrieMap k m a) Algebraic (m (Elem a)) => Algebraic (TrieMap k m a)

class Algebraic k whereSource

`Algebraic` refers to a type with an algebraic representation, armed with methods to convert in each direction. `toAlg` and `fromAlg` should preserve equality and ordering.

Associated Types

type AlgRep k Source

`AlgRep k` is a fully decomposed representation of k into algebraic pieces.

Methods

toAlg :: k -> AlgRep kSource

fromAlg :: AlgRep k -> kSource

Instances

 Algebraic Bool Algebraic Char Algebraic Double Algebraic Float Algebraic Int Algebraic Integer Algebraic Rational Algebraic Word8 Algebraic Word16 Algebraic Word32 Algebraic () Algebraic ByteString Algebraic IntSet Algebraic k => Algebraic [k] Algebraic a => Algebraic (Maybe a) Algebraic v => Algebraic (IntMap v) Algebraic a => Algebraic (Set a) Algebraic v => Algebraic (Elem v) AlgebraicT f => Algebraic (Fix f) Algebraic a => Algebraic (Ordered a) (Algebraic a, Algebraic b) => Algebraic (Either a b) (Algebraic a, Algebraic b) => Algebraic (a, b) (Algebraic k, Algebraic v) => Algebraic (Map k v) Algebraic (f a) => Algebraic (App f a) Algebraic a => Algebraic (Const a b) (AlgebraicT t, Algebraic a) => Algebraic (AlgWrap t a) (Algebraic a, Algebraic b, Algebraic c) => Algebraic (a, b, c) Algebraic (m a) => Algebraic (IdMap k m a) (AlgebraicT m, Algebraic k, Algebraic a) => Algebraic (RadixTrie k m a) (AlgebraicT m, Algebraic k, Algebraic a) => Algebraic (Edge k m a) (Algebraic (f (g a)), Functor f) => Algebraic (O f g a) (TrieKeyT f t, AlgebraicT f, Sized a, Algebraic a) => Algebraic (FixMap f t a) (AlgebraicT f, AlgebraicT g, Algebraic a) => Algebraic (:+: f g a) (AlgebraicT f, AlgebraicT g, Algebraic a) => Algebraic (:*: f g a) Algebraic (m (Elem a)) => Algebraic (TrieMap k m a) (Algebraic a, Algebraic b, Algebraic c, Algebraic d) => Algebraic (a, b, c, d) Algebraic (m a) => Algebraic (ConstMap m k m' a) (Algebraic (m1 a), Algebraic (m2 a)) => Algebraic (CUnionMap m1 k2 m2 a) Algebraic (m1 (m2 a)) => Algebraic (CProdMap m1 k2 m2 a) (Algebraic (t1 k m a), Algebraic (t2 k m a)) => Algebraic (UnionMap t1 t2 k m a) Algebraic (t1 k m (t2 k m a)) => Algebraic (ProdMap t1 t2 k m a) Algebraic (t1 (App f2 k) (App (t2 k m)) a) => Algebraic (CompMap t1 f2 t2 k m a)

class Functor (AlgRepT t) => AlgebraicT t whereSource

Associated Types

type AlgRepT t :: * -> *Source

Methods

toAlgT :: t a -> AlgRepT t aSource

fromAlgT :: AlgRepT t a -> t aSource

Instances

 AlgebraicT [] AlgebraicT Maybe AlgebraicT IntMap AlgebraicT Set AlgebraicT Id Algebraic a => AlgebraicT (Either a) Algebraic a => AlgebraicT ((,) a) Algebraic k => AlgebraicT (Map k) AlgebraicT f => AlgebraicT (App f) Algebraic a => AlgebraicT (Const a) (Algebraic a, Algebraic b) => AlgebraicT ((,,) a b) (AlgebraicT f, AlgebraicT g) => AlgebraicT (O f g) (AlgebraicT f, AlgebraicT g) => AlgebraicT (:+: f g) (AlgebraicT f, AlgebraicT g) => AlgebraicT (:*: f g) SAlgebraicT m => AlgebraicT (TrieMap k m) (Algebraic a, Algebraic b, Algebraic c) => AlgebraicT ((,,,) a b c)

class Eq k => TrieKey k m | k -> m, m -> kSource

TrieKey defines a bijection between map types and algebraic key types.

Instances

 TrieKey Int IntMap TrieKey () Maybe Ord k => TrieKey (Ordered k) (Map k) TrieKey k m => TrieKey [k] (RadixTrie k m) TrieKeyT f t => TrieKey (Fix f) (FixMap f t) TrieKey k m => TrieKey (Id k) (IdMap k m) (TrieKeyT f t, TrieKey k m) => TrieKey (App f k) (App (t k m)) (TrieKey k1 m1, TrieKey k2 m2) => TrieKey (Either k1 k2) (CUnionMap m1 k2 m2) (TrieKey k1 m1, TrieKey k2 m2) => TrieKey (k1, k2) (CProdMap m1 k2 m2) (TrieKey k m, TrieKey k' m') => TrieKey (Const k k') (ConstMap m k' m') (Eq (f1 k), Eq (f2 k), TrieKey k m, TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKey (:+: f1 f2 k) (UnionMap t1 t2 k m) (Eq (f1 k), Eq (f2 k), TrieKey k m, TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKey (:*: f1 f2 k) (ProdMap t1 t2 k m) (TrieKey k m, TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKey (O f1 f2 k) (CompMap t1 f2 t2 k m)

class EqT f => TrieKeyT f t | f -> t, t -> fSource

Instances

 TrieKeyT [] RadixTrie TrieKeyT Id IdMap TrieKey k m => TrieKeyT (Either k) (CUnionMap m) TrieKey k m => TrieKeyT ((,) k) (CProdMap m) TrieKey k m => TrieKeyT (Const k) (ConstMap m) (TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKeyT (:+: f1 f2) (UnionMap t1 t2) (TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKeyT (:*: f1 f2) (ProdMap t1 t2) (TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKeyT (O f1 f2) (CompMap t1 f2 t2)

class EqT f Source

Instances

 EqT [] EqT Maybe EqT Id Eq a => EqT (Either a) Eq a => EqT ((,) a) EqT f => EqT (App f) Eq a => EqT (Const a) (EqT f, EqT g) => EqT (O f g) (EqT f, EqT g) => EqT (:+: f g) (EqT f, EqT g) => EqT (:*: f g)

# Map instances

data ProdMap t1 t2 k m a Source

`ProdMap` is used to hold a map on the product of two key types.

Instances

 (TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKeyT (:*: f1 f2) (ProdMap t1 t2) (Eq (f1 k), Eq (f2 k), TrieKey k m, TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKey (:*: f1 f2 k) (ProdMap t1 t2 k m) (SAlgebraicT (t1 k m), SAlgebraicT (t2 k m), TrieKey k m, TrieKeyT f2 t2) => SAlgebraicT (ProdMap t1 t2 k m) Algebraic (t1 k m (t2 k m a)) => Algebraic (ProdMap t1 t2 k m a)

data (f :*: g) a Source

Constructors

 (f a) :*: (g a)

Instances

 (Functor f, Functor g) => Functor (:*: f g) (Foldable f, Foldable g) => Foldable (:*: f g) (Traversable f, Traversable g) => Traversable (:*: f g) (EqT f, EqT g) => EqT (:*: f g) (AlgebraicT f, AlgebraicT g) => AlgebraicT (:*: f g) (TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKeyT (:*: f1 f2) (ProdMap t1 t2) (Eq (f a), Eq (g a)) => Eq (:*: f g a) (Ord (f a), Ord (g a)) => Ord (:*: f g a) (Show (f a), Show (g a)) => Show (:*: f g a) (AlgebraicT f, AlgebraicT g, Algebraic a) => Algebraic (:*: f g a) (Eq (f1 k), Eq (f2 k), TrieKey k m, TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKey (:*: f1 f2 k) (ProdMap t1 t2 k m)

data CProdMap m1 k2 m2 a Source

Instances

 TrieKey k m => TrieKeyT ((,) k) (CProdMap m) (TrieKey k1 m1, TrieKey k2 m2) => TrieKey (k1, k2) (CProdMap m1 k2 m2) (SAlgebraicT m1, SAlgebraicT m2, TrieKey k2 m2) => SAlgebraicT (CProdMap m1 k2 m2) Algebraic (m1 (m2 a)) => Algebraic (CProdMap m1 k2 m2 a)

data UnionMap t1 t2 k m a Source

Instances

 (TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKeyT (:+: f1 f2) (UnionMap t1 t2) (Eq (f1 k), Eq (f2 k), TrieKey k m, TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKey (:+: f1 f2 k) (UnionMap t1 t2 k m) (SAlgebraicT (t1 k m), SAlgebraicT (t2 k m)) => SAlgebraicT (UnionMap t1 t2 k m) (Algebraic (t1 k m a), Algebraic (t2 k m a)) => Algebraic (UnionMap t1 t2 k m a)

data (f :+: g) a Source

Constructors

 A (f a) B (g a)

Instances

 (Functor f, Functor g) => Functor (:+: f g) (Foldable f, Foldable g) => Foldable (:+: f g) (Traversable f, Traversable g) => Traversable (:+: f g) (EqT f, EqT g) => EqT (:+: f g) (AlgebraicT f, AlgebraicT g) => AlgebraicT (:+: f g) (TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKeyT (:+: f1 f2) (UnionMap t1 t2) (Eq (f a), Eq (g a)) => Eq (:+: f g a) (Ord (f a), Ord (g a)) => Ord (:+: f g a) (Show (f a), Show (g a)) => Show (:+: f g a) (AlgebraicT f, AlgebraicT g, Algebraic a) => Algebraic (:+: f g a) (Eq (f1 k), Eq (f2 k), TrieKey k m, TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKey (:+: f1 f2 k) (UnionMap t1 t2 k m)

data CUnionMap m1 k2 m2 a Source

Instances

 TrieKey k m => TrieKeyT (Either k) (CUnionMap m) (TrieKey k1 m1, TrieKey k2 m2) => TrieKey (Either k1 k2) (CUnionMap m1 k2 m2) (SAlgebraicT m1, SAlgebraicT m2) => SAlgebraicT (CUnionMap m1 k2 m2) (Algebraic (m1 a), Algebraic (m2 a)) => Algebraic (CUnionMap m1 k2 m2 a)

data RadixTrie k m v Source

`RadixTrie` is used to hold a map on a list of keys.

Instances

 TrieKeyT [] RadixTrie TrieKey k m => TrieKey [k] (RadixTrie k m) (Algebraic k, TrieKey k m) => SAlgebraicT (RadixTrie k m) (AlgebraicT m, Algebraic k, Algebraic a) => Algebraic (RadixTrie k m a)

data ConstMap m k x a Source

Instances

 TrieKey k m => TrieKeyT (Const k) (ConstMap m) (TrieKey k m, TrieKey k' m') => TrieKey (Const k k') (ConstMap m k' m') SAlgebraicT m => SAlgebraicT (ConstMap m k m') Algebraic (m a) => Algebraic (ConstMap m k m' a)

newtype Const a b Source

Constructors

 Const FieldsunConst :: a

Instances

 Functor (Const a) Foldable (Const a) Traversable (Const a) Eq a => EqT (Const a) Algebraic a => AlgebraicT (Const a) TrieKey k m => TrieKeyT (Const k) (ConstMap m) Eq a => Eq (Const a b) Ord a => Ord (Const a b) Show a => Show (Const a b) Algebraic a => Algebraic (Const a b) (TrieKey k m, TrieKey k' m') => TrieKey (Const k k') (ConstMap m k' m')

data IdMap k m a Source

Instances

 TrieKeyT Id IdMap TrieKey k m => TrieKey (Id k) (IdMap k m) SAlgebraicT m => SAlgebraicT (IdMap k m) Algebraic (m a) => Algebraic (IdMap k m a)

newtype Id a Source

Constructors

 Id FieldsunId :: a

Instances

 Monad Id Functor Id Applicative Id Foldable Id Traversable Id EqT Id AlgebraicT Id TrieKeyT Id IdMap Eq a => Eq (Id a) Ord a => Ord (Id a) Show a => Show (Id a) TrieKey k m => TrieKey (Id k) (IdMap k m)

data CompMap t1 f2 t2 k m a Source

Instances

 (TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKeyT (O f1 f2) (CompMap t1 f2 t2) (TrieKey k m, TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKey (O f1 f2 k) (CompMap t1 f2 t2 k m) SAlgebraicT (t1 (App f2 k) (App (t2 k m))) => SAlgebraicT (CompMap t1 f2 t2 k m) Algebraic (t1 (App f2 k) (App (t2 k m)) a) => Algebraic (CompMap t1 f2 t2 k m a)

data O f g a Source

Instances

 (Functor f, Functor g) => Functor (O f g) (EqT f, EqT g) => EqT (O f g) (AlgebraicT f, AlgebraicT g) => AlgebraicT (O f g) (TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKeyT (O f1 f2) (CompMap t1 f2 t2) (EqT f, EqT g, Eq a) => Eq (O f g a) (Algebraic (f (g a)), Functor f) => Algebraic (O f g a) (TrieKey k m, TrieKeyT f1 t1, TrieKeyT f2 t2) => TrieKey (O f1 f2 k) (CompMap t1 f2 t2 k m)

o :: Functor f => f (g a) -> (f `O` g) aSource

unO :: Functor f => (f `O` g) a -> f (g a)Source

data FixMap f t a Source

Instances

 TrieKeyT f t => TrieKey (Fix f) (FixMap f t) TrieKeyT f t => SAlgebraicT (FixMap f t) (TrieKeyT f t, AlgebraicT f, Sized a, Algebraic a) => Algebraic (FixMap f t a)

newtype Fix f Source

Constructors

 Fix (f (Fix f))

Instances

 EqT f => Eq (Fix f) AlgebraicT f => Algebraic (Fix f) TrieKeyT f t => TrieKey (Fix f) (FixMap f t)

# Operators

(!) :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> k -> aSource

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

(\\) :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> TrieMap k m b -> TrieMap k m aSource

Same as `difference`.

# Query

null :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> BoolSource

Check if the specified map is empty.

size :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> IntSource

Returns the size of the specified map.

member :: (Algebraic k, TrieKey (AlgRep k) m) => k -> TrieMap k m a -> BoolSource

Is the key a member of the map? See also `notMember`.

``` member 5 (fromList [(5,'a'), (3,'b')]) == True
member 1 (fromList [(5,'a'), (3,'b')]) == False
```

notMember :: (Algebraic k, TrieKey (AlgRep k) m) => k -> TrieMap k m a -> BoolSource

Is the key not a member of the map? See also `member`.

``` notMember 5 (fromList [(5,'a'), (3,'b')]) == False
notMember 1 (fromList [(5,'a'), (3,'b')]) == True
```

lookup :: (Algebraic k, TrieKey (AlgRep k) m) => k -> TrieMap k m a -> Maybe aSource

Lookup the value of 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.

find :: (Algebraic k, TrieKey (AlgRep k) m) => k -> TrieMap k m a -> aSource

Find the value at a key. Calls `error` when the element can not be found.

findWithDefault :: (Algebraic k, TrieKey (AlgRep k) m) => a -> k -> TrieMap k m a -> aSource

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.

``` findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
```

# Construction

empty :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m aSource

singleton :: (Algebraic k, TrieKey (AlgRep k) m) => k -> a -> TrieMap k m aSource

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

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

# Insertion

insert :: (Algebraic k, TrieKey (AlgRep k) m) => k -> a -> TrieMap k m a -> TrieMap k m aSource

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

``` insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'x')]
insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'a'), (7, 'x')]
insert 5 'x' empty                         == singleton 5 'x'
```

insertWith :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> a -> a) -> k -> a -> TrieMap k m a -> TrieMap k m aSource

Insert with a function, combining new value and old value. `insertWith f key value mp` will insert the pair (key, value) into `mp` if key does not exist in the map. If the key does exist, the function will insert the pair `(key, f new_value old_value)`.

``` insertWith (++) 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "xxxa")]
insertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
insertWith (++) 5 "xxx" empty                         == singleton 5 "xxx"
```

insertWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> a -> a) -> k -> a -> TrieMap k m a -> TrieMap k m aSource

Insert with a function, combining key, new value and old value. `insertWithKey f key value mp` will insert the pair (key, value) into `mp` if key does not exist in the map. If the key does exist, the function will insert the pair `(key,f key new_value old_value)`. Note that the key passed to f is the same key passed to `insertWithKey`.

``` let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
insertWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:xxx|a")]
insertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
insertWithKey f 5 "xxx" empty                         == singleton 5 "xxx"
```

insertLookupWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> a -> a) -> k -> a -> TrieMap k m a -> (Maybe a, TrieMap k m a)Source

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

# Delete/Update

delete :: (Algebraic k, TrieKey (AlgRep k) m) => k -> TrieMap k m a -> TrieMap k m aSource

Delete a key and its value from the map. When the key is not a member of the map, the original map is returned.

``` delete 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
delete 5 empty                         == empty
```

`delete` is equivalent to `alter (const Nothing)`.

update :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> Maybe a) -> k -> TrieMap k m a -> TrieMap k m aSource

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

``` let f x = if x == "a" then Just "new a" else Nothing
update f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
update f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
```

updateWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> Maybe a) -> k -> TrieMap k m a -> TrieMap k m aSource

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

``` let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
updateWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
updateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
updateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
```

updateLookupWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> Maybe a) -> k -> TrieMap k m a -> (Maybe a, TrieMap k m a)Source

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.

``` let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "5:new a", fromList [(3, "b"), (5, "5:new a")])
updateLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a")])
updateLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")
```

alter :: (Algebraic k, TrieKey (AlgRep k) m) => (Maybe a -> Maybe a) -> k -> TrieMap k m a -> TrieMap k m aSource

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

``` let f _ = Nothing
alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
alter f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"

let f _ = Just "c"
alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "c")]
alter f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "c")]
```

alterLookup :: (Algebraic k, TrieKey (AlgRep k) m) => (Maybe a -> Maybe a) -> k -> TrieMap k m a -> (Maybe a, TrieMap k m a)Source

The expression (`alterLookup f k map`) alters the value `x` at `k`, or absence thereof, and returns the old value. `alterLookup` can be used to insert, delete, or update a value in a `Map`.

In short : `alterLookup f k m = (lookup k m, alter f k m)`.

# Combine

## Union/Symmetric Difference

union :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> TrieMap k m a -> TrieMap k m aSource

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

``` union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
```

unionWith :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> a -> a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m aSource

O(n+m). Union with a combining function.

``` unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
```

unionWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> a -> a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m aSource

O(n+m). Union with a combining function.

``` let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value
unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]
```

unions :: (Algebraic k, TrieKey (AlgRep k) m) => [TrieMap k m a] -> TrieMap k m aSource

unionsWith :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> a -> a) -> [TrieMap k m a] -> TrieMap k m aSource

unionsWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> a -> a) -> [TrieMap k m a] -> TrieMap k m aSource

unionMaybeWith :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> a -> Maybe a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m aSource

O(n+m). Union with a combining function that may discard some elements.

unionMaybeWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> a -> Maybe a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m aSource

O(n+m). Union with a combining function that may discard some elements.

symDifference :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> TrieMap k m a -> TrieMap k m aSource

O(n+m). Symmetric difference. Equivalent to `unionMaybeWith ( _ _ -> Nothing)`.

## Intersection

intersection :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> TrieMap k m b -> TrieMap k m aSource

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

``` intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a"
```

intersectionWith :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> b -> c) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m cSource

O(n+m). Intersection with a combining function.

``` intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA"
```

intersectionWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> b -> c) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m cSource

O(n+m). Intersection with a combining function.

``` let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar
intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "5:a|A"
```

intersectionMaybeWith :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> b -> Maybe c) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m cSource

O(n+m). Intersection of two maps with a combining function that may discard some elements.

intersectionMaybeWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> b -> Maybe c) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m cSource

O(n+m). Intersection of two maps with a combining function that may discard some elements.

## Difference

difference :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> TrieMap k m b -> TrieMap k m aSource

O(n+m). Difference of two maps. Return elements of the first map not existing in the second map.

``` difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"
```

differenceWith :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> b -> Maybe a) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m aSource

O(n+m). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the values of these keys. 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`.

``` let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])
== singleton 3 "b:B"
```

differenceWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> b -> Maybe a) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m aSource

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

``` let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
differenceWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (10, "C")])
== singleton 3 "3:b|B"
```

# Traversal

## Map

map :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> b) -> TrieMap k m a -> TrieMap k m bSource

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

``` map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
```

mapWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> b) -> TrieMap k m a -> TrieMap k m bSource

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

``` let f key x = (show key) ++ ":" ++ x
mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]
```

traverseWithKey :: (Algebraic k, TrieKey (AlgRep k) m, Applicative f) => (k -> a -> f b) -> TrieMap k m a -> f (TrieMap k m b)Source

Essentially equivalent to `traverse` with a function that takes both the key and the value as arguments.

mapMaybe :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> Maybe b) -> TrieMap k m a -> TrieMap k m bSource

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

``` let f x = if x == "a" then Just "new a" else Nothing
mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"
```

mapMaybeWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> Maybe b) -> TrieMap k m a -> TrieMap k m bSource

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

``` let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing
mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"
```

mapEither :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> Either b c) -> TrieMap k m a -> (TrieMap k m b, TrieMap k m c)Source

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

``` let f a = if a < "c" then Left a else Right a
mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
== (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")])

mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
== (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
```

mapEitherWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> Either b c) -> TrieMap k m a -> (TrieMap k m b, TrieMap k m c)Source

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

``` let f k a = if k < 5 then Left (k * 2) else Right (a ++ a)
mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
== (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")])

mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
== (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")])
```

mapKeys :: (Algebraic k1, Algebraic k2, TrieKey (AlgRep k1) m1, TrieKey (AlgRep k2) m2) => (k1 -> k2) -> TrieMap k1 m1 a -> TrieMap k2 m2 aSource

`mapKeys 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 value at the smallest of these keys is retained.

``` mapKeys (+ 1) (fromList [(5,"a"), (3,"b")])                        == fromList [(4, "b"), (6, "a")]
mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "c"
mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "c"
```

mapKeysWith :: (Algebraic k1, Algebraic k2, TrieKey (AlgRep k1) m1, TrieKey (AlgRep k2) m2) => (a -> a -> a) -> (k1 -> k2) -> TrieMap k1 m1 a -> TrieMap k2 m2 aSource

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

``` mapKeysWith (++) (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "cdab"
mapKeysWith (++) (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "cdab"
```

mapKeysMonotonic :: (Algebraic k1, Algebraic k2, TrieKey (AlgRep k1) m1, TrieKey (AlgRep k2) m2) => (k1 -> k2) -> TrieMap k1 m1 a -> TrieMap k2 m2 aSource

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

``` mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
valid (mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")])) == True
valid (mapKeysMonotonic (\ _ -> 1)     (fromList [(5,"a"), (3,"b")])) == False
```

## Fold

fold :: TrieKey k m => (a -> b -> b) -> b -> TrieMap k m a -> bSource

O(n). Fold the values in the map, such that `fold f z == foldr f z . elems`. For example,

``` elems map = fold (:) [] map
```
``` let f a len = len + (length a)
fold f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
```

foldWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> b -> b) -> b -> TrieMap k m a -> bSource

O(n). Fold the keys and values in the map, such that `foldWithKey f z == foldr (uncurry f) z . assocs`. For example,

``` keys map = foldWithKey (\k x ks -> k:ks) [] map
```
``` let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
foldWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
```

# Conversion

elems :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> [a]Source

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

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

keys :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> [k]Source

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

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

assocs :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> [(k, a)]Source

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

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

## Lists

fromList :: (Algebraic k, TrieKey (AlgRep k) m) => [(k, a)] -> TrieMap k m aSource

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.

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

fromListWith :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> a -> a) -> [(k, a)] -> TrieMap k m aSource

Build a map from a list of key/value pairs with a combining function. See also `fromAscListWith`.

``` fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
fromListWith (++) [] == empty
```

fromListWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> a -> a) -> [(k, a)] -> TrieMap k m aSource

Build a map from a list of key/value pairs with a combining function. See also `fromAscListWithKey`.

``` let f k a1 a2 = (show k) ++ a1 ++ a2
fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "3ab"), (5, "5a5ba")]
fromListWithKey f [] == empty
```

## Ordered lists

fromAscList :: (Algebraic k, TrieKey (AlgRep k) m) => [(k, a)] -> TrieMap k m aSource

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

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

fromAscListWith :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> a -> a) -> [(k, a)] -> TrieMap k m aSource

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.

``` fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
```

fromAscListWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> a -> a) -> [(k, a)] -> TrieMap k m aSource

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.

``` let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2
fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")] == fromList [(3, "b"), (5, "5:b5:ba")]
```

fromDistinctAscList :: (Algebraic k, TrieKey (AlgRep k) m) => [(k, a)] -> TrieMap k m aSource

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

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

# Filter

filter :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> Bool) -> TrieMap k m a -> TrieMap k m aSource

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

``` filter (> "a") (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
filter (> "x") (fromList [(5,"a"), (3,"b")]) == empty
filter (< "a") (fromList [(5,"a"), (3,"b")]) == empty
```

filterWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> Bool) -> TrieMap k m a -> TrieMap k m aSource

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

``` filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
```

partition :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> Bool) -> TrieMap k m a -> (TrieMap k m a, TrieMap k m a)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.

``` partition (> "a") (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a")
partition (< "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
partition (> "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
```

partitionWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> Bool) -> TrieMap k m a -> (TrieMap k m a, TrieMap k m a)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.

``` partitionWithKey (\ k _ -> k > 3) (fromList [(5,"a"), (3,"b")]) == (singleton 5 "a", singleton 3 "b")
partitionWithKey (\ k _ -> k < 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
partitionWithKey (\ k _ -> k > 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
```

split :: (Algebraic k, TrieKey (AlgRep k) m) => k -> TrieMap k m a -> (TrieMap k m a, TrieMap k m a)Source

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

``` split 2 (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3,"b"), (5,"a")])
split 3 (fromList [(5,"a"), (3,"b")]) == (empty, singleton 5 "a")
split 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a")
split 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", empty)
split 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], empty)
```

splitLookup :: (Algebraic k, TrieKey (AlgRep k) m) => k -> TrieMap k m a -> (TrieMap k m a, Maybe a, TrieMap k m a)Source

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

``` splitLookup 2 (fromList [(5,"a"), (3,"b")]) == (empty, Nothing, fromList [(3,"b"), (5,"a")])
splitLookup 3 (fromList [(5,"a"), (3,"b")]) == (empty, Just "b", singleton 5 "a")
splitLookup 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Nothing, singleton 5 "a")
splitLookup 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Just "a", empty)
splitLookup 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], Nothing, empty)
```

# Submap

isSubmapOf :: (Algebraic k, TrieKey (AlgRep k) m, Eq a) => TrieMap k m a -> TrieMap k m a -> BoolSource

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

isSubmapOfBy :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> b -> Bool) -> TrieMap k m a -> TrieMap k m b -> BoolSource

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 values. For example, the following expressions are all `True`:

``` isSubmapOfBy (==) (fromList [('a',1)]) (fromList [('a',1),('b',2)])
isSubmapOfBy (<=) (fromList [('a',1)]) (fromList [('a',1),('b',2)])
isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1),('b',2)])
```

But the following are all `False`:

``` isSubmapOfBy (==) (fromList [('a',2)]) (fromList [('a',1),('b',2)])
isSubmapOfBy (<)  (fromList [('a',1)]) (fromList [('a',1),('b',2)])
isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1)])
```

# Min/Max

findMin :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> (k, a)Source

The minimal key of the map. Calls `error` if the map is empty.

``` findMin (fromList [(5,"a"), (3,"b")]) == (3,"b")
findMin empty                            Error: empty map has no minimal element
```

getMin :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> Maybe (k, a)Source

The minimal key of the map, if any. Returns `Nothing` if the map is empty.

``` getMin (fromList [(5,"a"), (3,"b")]) == Just (3,"b")
getMin empty                         == Nothing
```

findMax :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> (k, a)Source

The maximal key of the map. Calls `error` is the map is empty.

``` findMax (fromList [(5,"a"), (3,"b")]) == (5,"a")
findMax empty                            Error: empty map has no maximal element
```

getMax :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> Maybe (k, a)Source

The maximal key of the map, if any. Returns `Nothing` if the map is empty.

``` getMax (fromList [(5,"a"), (3,"b")]) == Just (5,"a")
getMax empty                         == Nothing
```

deleteMin :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> TrieMap k m aSource

Delete the minimal key. Returns an empty map if the map is empty.

``` deleteMin (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(5,"a"), (7,"c")]
deleteMin empty == empty
```

deleteMax :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> TrieMap k m aSource

Delete the maximal key. Returns an empty map if the map is empty.

``` deleteMax (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(3,"b"), (5,"a")]
deleteMax empty == empty
```

deleteFindMin :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> ((k, a), TrieMap k m a)Source

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 :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> ((k, a), TrieMap k m a)Source

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

updateMin :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> Maybe a) -> TrieMap k m a -> TrieMap k m aSource

Update the value at the minimal key.

``` updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")]
updateMin (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
```

updateMax :: (Algebraic k, TrieKey (AlgRep k) m) => (a -> Maybe a) -> TrieMap k m a -> TrieMap k m aSource

Update the value at the maximal key.

``` updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")]
updateMax (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
```

updateMinWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> Maybe a) -> TrieMap k m a -> TrieMap k m aSource

Update the value at the minimal key.

``` updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")]
updateMinWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
```

updateMaxWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => (k -> a -> Maybe a) -> TrieMap k m a -> TrieMap k m aSource

Update the value at the maximal key.

``` updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")]
updateMaxWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
```

minView :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> Maybe (a, TrieMap k m a)Source

Retrieves the value associated with the minimal key of the map, and the map stripped of that element, or `Nothing` if passed an empty map.

``` minView (fromList [(5,"a"), (3,"b")]) == Just ("b", singleton 5 "a")
minView empty == Nothing
```

maxView :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> Maybe (a, TrieMap k m a)Source

Retrieves the value associated with the maximal key of the map, and the map stripped of that element, or `Nothing` if passed an

``` maxView (fromList [(5,"a"), (3,"b")]) == Just ("a", singleton 3 "b")
maxView empty == Nothing
```

minViewWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> Maybe ((k, a), TrieMap k m a)Source

Retrieves the minimal (key,value) pair of the map, and the map stripped of that element, or `Nothing` if passed an empty map.

``` minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
minViewWithKey empty == Nothing
```

maxViewWithKey :: (Algebraic k, TrieKey (AlgRep k) m) => TrieMap k m a -> Maybe ((k, a), TrieMap k m a)Source

Retrieves the maximal (key,value) pair of the map, and the map stripped of that element, or `Nothing` if passed an empty map.

``` maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b")
maxViewWithKey empty == Nothing
```