Copyright | (c) Galois Inc 2014-2019 |
---|---|

Safe Haskell | Trustworthy |

Language | Haskell2010 |

This module defines finite maps where the key and value types are parameterized by an arbitrary kind.

Some code was adapted from containers.

## Synopsis

- data MapF (k :: v -> Type) (a :: v -> Type)
- empty :: MapF k a
- singleton :: k tp -> a tp -> MapF k a
- insert :: OrdF k => k tp -> a tp -> MapF k a -> MapF k a
- insertWith :: OrdF k => (a tp -> a tp -> a tp) -> k tp -> a tp -> MapF k a -> MapF k a
- delete :: OrdF k => k tp -> MapF k a -> MapF k a
- union :: OrdF k => MapF k a -> MapF k a -> MapF k a
- intersectWithKeyMaybe :: OrdF k => (forall tp. k tp -> a tp -> b tp -> Maybe (c tp)) -> MapF k a -> MapF k b -> MapF k c
- null :: MapF k a -> Bool
- lookup :: OrdF k => k tp -> MapF k a -> Maybe (a tp)
- findWithDefault :: OrdF k => a tp -> k tp -> MapF k a -> a tp
- member :: OrdF k => k tp -> MapF k a -> Bool
- notMember :: OrdF k => k tp -> MapF k a -> Bool
- size :: IsBinTree t e => t -> Int
- keys :: MapF k a -> [Some k]
- elems :: MapF k a -> [Some a]
- fromList :: OrdF k => [Pair k a] -> MapF k a
- toList :: MapF k a -> [Pair k a]
- toAscList :: MapF k a -> [Pair k a]
- toDescList :: MapF k a -> [Pair k a]
- fromKeys :: forall k m (t :: Type -> Type) (a :: k -> Type) (v :: k -> Type). (Monad m, Foldable t, OrdF a) => (forall tp. a tp -> m (v tp)) -> t (Some a) -> m (MapF a v)
- fromKeysM :: forall k m (t :: Type -> Type) (a :: k -> Type) (v :: k -> Type). (Monad m, Foldable t, OrdF a) => (forall tp. a tp -> m (v tp)) -> t (Some a) -> m (MapF a v)
- filter :: (forall tp. f tp -> Bool) -> MapF k f -> MapF k f
- filterWithKey :: (forall tp. k tp -> f tp -> Bool) -> MapF k f -> MapF k f
- filterGt :: OrdF k => k tp -> MapF k v -> MapF k v
- filterLt :: OrdF k => k tp -> MapF k v -> MapF k v
- foldlWithKey :: (forall s. b -> k s -> a s -> b) -> b -> MapF k a -> b
- foldlWithKey' :: (forall s. b -> k s -> a s -> b) -> b -> MapF k a -> b
- foldrWithKey :: (forall s. k s -> a s -> b -> b) -> b -> MapF k a -> b
- foldrWithKey' :: (forall s. k s -> a s -> b -> b) -> b -> MapF k a -> b
- foldMapWithKey :: Monoid m => (forall s. k s -> a s -> m) -> MapF k a -> m
- foldlMWithKey :: Monad m => (forall s. b -> k s -> a s -> m b) -> b -> MapF k a -> m b
- foldrMWithKey :: Monad m => (forall s. k s -> a s -> b -> m b) -> b -> MapF k a -> m b
- map :: (forall tp. f tp -> g tp) -> MapF ktp f -> MapF ktp g
- mapWithKey :: (forall tp. ktp tp -> f tp -> g tp) -> MapF ktp f -> MapF ktp g
- mapMaybe :: (forall tp. f tp -> Maybe (g tp)) -> MapF ktp f -> MapF ktp g
- mapMaybeWithKey :: (forall tp. k tp -> f tp -> Maybe (g tp)) -> MapF k f -> MapF k g
- traverseWithKey :: Applicative m => (forall tp. ktp tp -> f tp -> m (g tp)) -> MapF ktp f -> m (MapF ktp g)
- traverseWithKey_ :: Applicative m => (forall tp. ktp tp -> f tp -> m ()) -> MapF ktp f -> m ()
- traverseMaybeWithKey :: Applicative f => (forall tp. k tp -> a tp -> f (Maybe (b tp))) -> MapF k a -> f (MapF k b)
- data UpdateRequest v
- data Updated a
- updatedValue :: Updated a -> a
- updateAtKey :: (OrdF k, Functor f) => k tp -> f (Maybe (a tp)) -> (a tp -> f (UpdateRequest (a tp))) -> MapF k a -> f (Updated (MapF k a))
- mergeWithKey :: forall k a b c. OrdF k => (forall tp. k tp -> a tp -> b tp -> Maybe (c tp)) -> (MapF k a -> MapF k c) -> (MapF k b -> MapF k c) -> MapF k a -> MapF k b -> MapF k c
- mergeWithKeyM :: forall k a b c m. (Applicative m, OrdF k) => (forall tp. k tp -> a tp -> b tp -> m (Maybe (c tp))) -> (MapF k a -> m (MapF k c)) -> (MapF k b -> m (MapF k c)) -> MapF k a -> MapF k b -> m (MapF k c)
- module Data.Parameterized.Classes
- data Pair (a :: k -> *) (b :: k -> *) where

# Documentation

data MapF (k :: v -> Type) (a :: v -> Type) Source #

A map from parameterized keys to values with the same parameter type.

#### Instances

TraversableF (MapF ktp :: (k -> Type) -> Type) Source # | |

Defined in Data.Parameterized.Map | |

FoldableF (MapF ktp :: (k -> Type) -> Type) Source # | |

Defined in Data.Parameterized.Map foldMapF :: Monoid m => (forall (s :: k0). e s -> m) -> MapF ktp e -> m Source # foldrF :: (forall (s :: k0). e s -> b -> b) -> b -> MapF ktp e -> b Source # foldlF :: (forall (s :: k0). b -> e s -> b) -> b -> MapF ktp e -> b Source # foldrF' :: (forall (s :: k0). e s -> b -> b) -> b -> MapF ktp e -> b Source # foldlF' :: (forall (s :: k0). b -> e s -> b) -> b -> MapF ktp e -> b Source # toListF :: (forall (tp :: k0). f tp -> a) -> MapF ktp f -> [a] Source # | |

FunctorF (MapF ktp :: (k -> Type) -> Type) Source # | |

OrdF k => AtF a (MapF k v) Source # | Turn a map key into a lens that points into the indicated position in the map. |

OrdF k => IxedF a (MapF k v) Source # | Turn a map key into a traversal that visits the indicated element in the map, if it exists. |

(TestEquality k, EqF a) => Eq (MapF k a) Source # | |

(ShowF ktp, ShowF rtp) => Show (MapF ktp rtp) Source # | |

IsBinTree (MapF k2 a) (Pair k2 a) Source # | |

type IxValueF (MapF k2 v) Source # | |

Defined in Data.Parameterized.Map | |

type IndexF (MapF k2 v) Source # | |

Defined in Data.Parameterized.Map |

# Construction

insert :: OrdF k => k tp -> a tp -> MapF k a -> MapF k a Source #

Insert a binding into the map, replacing the existing binding if needed.

union :: OrdF k => MapF k a -> MapF k a -> MapF k a Source #

Left-biased union of two maps. The resulting map will contain the union of the keys of the two arguments. When a key is contained in both maps the value from the first map will be preserved.

intersectWithKeyMaybe :: OrdF k => (forall tp. k tp -> a tp -> b tp -> Maybe (c tp)) -> MapF k a -> MapF k b -> MapF k c Source #

Applies a function to the pairwise common elements of two maps.

Formally, we have that `intersectWithKeyMaybe f x y`

contains a
binding from a key `k`

to a value `v`

if and only if `x`

and `y`

bind `k`

to `x_k`

and `y_k`

and `f x_k y_k = Just v`

.

# Query

findWithDefault :: OrdF k => a tp -> k tp -> MapF k a -> a tp Source #

`findWithDefault d k m`

returns the value bound to `k`

in the map `m`

, or `d`

if `k`

is not bound in the map.

# Conversion

elems :: MapF k a -> [Some a] Source #

Return all elements of the map in the ascending order of their keys.

toAscList :: MapF k a -> [Pair k a] Source #

Return list of key-values pairs in map in ascending order.

toDescList :: MapF k a -> [Pair k a] Source #

Return list of key-values pairs in map in descending order.

:: forall k m (t :: Type -> Type) (a :: k -> Type) (v :: k -> Type). (Monad m, Foldable t, OrdF a) | |

=> (forall tp. a tp -> m (v tp)) | Function for evaluating a register value. |

-> t (Some a) | Set of X86 registers |

-> m (MapF a v) |

Generate a map from a foldable collection of keys and a function from keys to values.

:: forall k m (t :: Type -> Type) (a :: k -> Type) (v :: k -> Type). (Monad m, Foldable t, OrdF a) | |

=> (forall tp. a tp -> m (v tp)) | Function for evaluating an input value to store the result in the map. |

-> t (Some a) | Set of input values (traversed via folding) |

-> m (MapF a v) |

Generate a map from a foldable collection of keys and a monadic function from keys to values.

# Filter

filter :: (forall tp. f tp -> Bool) -> MapF k f -> MapF k f Source #

Return entries with values that satisfy a predicate.

filterWithKey :: (forall tp. k tp -> f tp -> Bool) -> MapF k f -> MapF k f Source #

Return key-value pairs that satisfy a predicate.

filterGt :: OrdF k => k tp -> MapF k v -> MapF k v Source #

`filterGt k m`

returns submap of `m`

that only contains entries
that are larger than `k`

.

filterLt :: OrdF k => k tp -> MapF k v -> MapF k v Source #

`filterLt k m`

returns submap of `m`

that only contains entries
that are smaller than `k`

.

# Folds

foldlWithKey :: (forall s. b -> k s -> a s -> b) -> b -> MapF k a -> b Source #

Perform a left fold with the key also provided.

foldlWithKey' :: (forall s. b -> k s -> a s -> b) -> b -> MapF k a -> b Source #

Perform a strict left fold with the key also provided.

foldrWithKey :: (forall s. k s -> a s -> b -> b) -> b -> MapF k a -> b Source #

Perform a right fold with the key also provided.

foldrWithKey' :: (forall s. k s -> a s -> b -> b) -> b -> MapF k a -> b Source #

Perform a strict right fold with the key also provided.

foldMapWithKey :: Monoid m => (forall s. k s -> a s -> m) -> MapF k a -> m Source #

Fold the keys and values using the given monoid.

foldlMWithKey :: Monad m => (forall s. b -> k s -> a s -> m b) -> b -> MapF k a -> m b Source #

A monadic left-to-right fold over keys and values in the map.

foldrMWithKey :: Monad m => (forall s. k s -> a s -> b -> m b) -> b -> MapF k a -> m b Source #

A monadic right-to-left fold over keys and values in the map.

# Traversals

mapWithKey :: (forall tp. ktp tp -> f tp -> g tp) -> MapF ktp f -> MapF ktp g Source #

Apply function to all elements in map.

mapMaybe :: (forall tp. f tp -> Maybe (g tp)) -> MapF ktp f -> MapF ktp g Source #

Map elements and collect `Just`

results.

mapMaybeWithKey :: (forall tp. k tp -> f tp -> Maybe (g tp)) -> MapF k f -> MapF k g Source #

Map keys and elements and collect `Just`

results.

traverseWithKey :: Applicative m => (forall tp. ktp tp -> f tp -> m (g tp)) -> MapF ktp f -> m (MapF ktp g) Source #

Traverse elements in a map

traverseWithKey_ :: Applicative m => (forall tp. ktp tp -> f tp -> m ()) -> MapF ktp f -> m () Source #

Traverse elements in a map without returning result.

traverseMaybeWithKey :: Applicative f => (forall tp. k tp -> a tp -> f (Maybe (b tp))) -> MapF k a -> f (MapF k b) Source #

Traverse keys/values and collect the `Just`

results.

# Complex interface.

data UpdateRequest v Source #

`UpdateRequest`

tells what to do with a found value

`Updated a`

contains a value that has been flagged on whether it was
modified by an operation.

updatedValue :: Updated a -> a Source #

:: (OrdF k, Functor f) | |

=> k tp | Key to update |

-> f (Maybe (a tp)) | Action to call if nothing is found |

-> (a tp -> f (UpdateRequest (a tp))) | Action to call if value is found. |

-> MapF k a | Map to update |

-> f (Updated (MapF k a)) |

Log-time algorithm that allows a value at a specific key to be added, replaced, or deleted.

mergeWithKey :: forall k a b c. OrdF k => (forall tp. k tp -> a tp -> b tp -> Maybe (c tp)) -> (MapF k a -> MapF k c) -> (MapF k b -> MapF k c) -> MapF k a -> MapF k b -> MapF k c Source #

Merge bindings in two maps to get a third.

The first function is used to merge elements that occur under the same key in both maps. Return Just to add an entry into the resulting map under this key or Nothing to remove this key from the resulting map.

The second function will be applied to submaps of the first map
argument where no keys overlap with the second map argument. The
result of this function must be a map with a subset of the keys of
its argument. This means the function can alter the values of its
argument and it can remove key-value pairs from it, but it can
break `MapF`

ordering invariants if it introduces new keys.

Third function is analogous to the second function except that it applies
to the second map argument of `mergeWithKeyM`

instead of the first.

Common examples of the two functions include `id`

when constructing a union
or `const`

`empty`

when constructing an intersection.

mergeWithKeyM :: forall k a b c m. (Applicative m, OrdF k) => (forall tp. k tp -> a tp -> b tp -> m (Maybe (c tp))) -> (MapF k a -> m (MapF k c)) -> (MapF k b -> m (MapF k c)) -> MapF k a -> MapF k b -> m (MapF k c) Source #

Merge bindings in two maps using monadic actions to get a third.

The first function is used to merge elements that occur under the same key in both maps. Return Just to add an entry into the resulting map under this key or Nothing to remove this key from the resulting map.

The second function will be applied to submaps of the first map
argument where no keys overlap with the second map argument. The
result of this function must be a map with a subset of the keys of
its argument. This means the function can alter the values of its
argument and it can remove key-value pairs from it, but it can
break `MapF`

ordering invariants if it introduces new keys.

Third function is analogous to the second function except that it applies
to the second map argument of `mergeWithKeyM`

instead of the first.

Common examples of the two functions include `id`

when constructing a union
or `const`

`empty`

when constructing an intersection.

module Data.Parameterized.Classes

# Pair

data Pair (a :: k -> *) (b :: k -> *) where Source #

Like a 2-tuple, but with an existentially quantified parameter that both of the elements share.

#### Instances

FoldableF (Pair a :: (k -> Type) -> Type) Source # | |

Defined in Data.Parameterized.Pair foldMapF :: Monoid m => (forall (s :: k0). e s -> m) -> Pair a e -> m Source # foldrF :: (forall (s :: k0). e s -> b -> b) -> b -> Pair a e -> b Source # foldlF :: (forall (s :: k0). b -> e s -> b) -> b -> Pair a e -> b Source # foldrF' :: (forall (s :: k0). e s -> b -> b) -> b -> Pair a e -> b Source # foldlF' :: (forall (s :: k0). b -> e s -> b) -> b -> Pair a e -> b Source # toListF :: (forall (tp :: k0). f tp -> a0) -> Pair a f -> [a0] Source # | |

FunctorF (Pair a :: (k -> Type) -> Type) Source # | |

(TestEquality a, EqF b) => Eq (Pair a b) Source # | |

IsBinTree (MapF k2 a) (Pair k2 a) Source # | |