parameterized-utils-2.1.11.0: Classes and data structures for working with data-kind indexed types

Copyright | (c) Galois Inc 2014-2019
Safe Haskell | Trustworthy
Language | Haskell2010

Data.Parameterized.Map

Contents

- Construction
- Query
- Conversion
- Filter
- Folds
- Traversals
- Complex interface.
- Pair

Description

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 :: forall {v} (k :: v -> Type) (a :: v -> Type). MapF k a
- singleton :: forall {v} k (tp :: v) a. k tp -> a tp -> MapF k a
- insert :: forall {v} k (tp :: v) a. OrdF k => k tp -> a tp -> MapF k a -> MapF k a
- insertWith :: forall {v} k a (tp :: v). OrdF k => (a tp -> a tp -> a tp) -> k tp -> a tp -> MapF k a -> MapF k a
- delete :: forall {v} k (tp :: v) (a :: v -> Type). OrdF k => k tp -> MapF k a -> MapF k a
- union :: forall {v} (k :: v -> Type) (a :: v -> Type). OrdF k => MapF k a -> MapF k a -> MapF k a
- intersectWithKeyMaybe :: OrdF k => (forall (tp :: v). k tp -> a tp -> b tp -> Maybe (c tp)) -> MapF k a -> MapF k b -> MapF k c
- null :: forall {v} (k :: v -> Type) (a :: v -> Type). MapF k a -> Bool
- lookup :: forall {v} k (tp :: v) a. OrdF k => k tp -> MapF k a -> Maybe (a tp)
- findWithDefault :: forall {v} k a (tp :: v). OrdF k => a tp -> k tp -> MapF k a -> a tp
- member :: forall {v} k (tp :: v) (a :: v -> Type). OrdF k => k tp -> MapF k a -> Bool
- notMember :: forall {v} k (tp :: v) (a :: v -> Type). OrdF k => k tp -> MapF k a -> Bool
- size :: IsBinTree t e => t -> Int
- keys :: forall {k1} (k2 :: k1 -> Type) (a :: k1 -> Type). MapF k2 a -> [Some k2]
- elems :: forall {k1} (k2 :: k1 -> Type) (a :: k1 -> Type). MapF k2 a -> [Some a]
- fromList :: forall {v} (k :: v -> Type) (a :: v -> Type). OrdF k => [Pair k a] -> MapF k a
- toList :: forall {k1} (k2 :: k1 -> Type) (a :: k1 -> Type). MapF k2 a -> [Pair k2 a]
- toAscList :: forall {k1} (k2 :: k1 -> Type) (a :: k1 -> Type). MapF k2 a -> [Pair k2 a]
- toDescList :: forall {k1} (k2 :: k1 -> Type) (a :: k1 -> Type). MapF k2 a -> [Pair k2 a]
- fromKeys :: forall k m t a v. (Monad m, Foldable t, OrdF a) => (forall (tp :: k). a tp -> m (v tp)) -> t (Some a) -> m (MapF a v)
- fromKeysM :: forall k m t a v. (Monad m, Foldable t, OrdF a) => (forall (tp :: k). a tp -> m (v tp)) -> t (Some a) -> m (MapF a v)
- filter :: forall {v} f (k :: v -> Type). (forall (tp :: v). f tp -> Bool) -> MapF k f -> MapF k f
- filterWithKey :: (forall (tp :: v). k tp -> f tp -> Bool) -> MapF k f -> MapF k f
- filterGt :: forall {v1} k (tp :: v1) (v2 :: v1 -> Type). OrdF k => k tp -> MapF k v2 -> MapF k v2
- filterLt :: forall {v1} k (tp :: v1) (v2 :: v1 -> Type). OrdF k => k tp -> MapF k v2 -> MapF k v2
- foldlWithKey :: (forall (s :: v). b -> k s -> a s -> b) -> b -> MapF k a -> b
- foldlWithKey' :: (forall (s :: v). b -> k s -> a s -> b) -> b -> MapF k a -> b
- foldrWithKey :: (forall (s :: v). k s -> a s -> b -> b) -> b -> MapF k a -> b
- foldrWithKey' :: (forall (s :: v). k s -> a s -> b -> b) -> b -> MapF k a -> b
- foldMapWithKey :: forall {v} m k a. Monoid m => (forall (s :: v). k s -> a s -> m) -> MapF k a -> m
- foldlMWithKey :: forall {v} m b k a. Monad m => (forall (s :: v). b -> k s -> a s -> m b) -> b -> MapF k a -> m b
- foldrMWithKey :: forall {v} m k a b. Monad m => (forall (s :: v). k s -> a s -> b -> m b) -> b -> MapF k a -> m b
- map :: forall {v} f g (ktp :: v -> Type). (forall (tp :: v). f tp -> g tp) -> MapF ktp f -> MapF ktp g
- mapWithKey :: (forall (tp :: v). ktp tp -> f tp -> g tp) -> MapF ktp f -> MapF ktp g
- mapMaybe :: forall {v} f g (ktp :: v -> Type). (forall (tp :: v). f tp -> Maybe (g tp)) -> MapF ktp f -> MapF ktp g
- mapMaybeWithKey :: (forall (tp :: v). k tp -> f tp -> Maybe (g tp)) -> MapF k f -> MapF k g
- traverseWithKey :: forall {v} m ktp f g. Applicative m => (forall (tp :: v). ktp tp -> f tp -> m (g tp)) -> MapF ktp f -> m (MapF ktp g)
- traverseWithKey_ :: forall {v} m ktp f. Applicative m => (forall (tp :: v). ktp tp -> f tp -> m ()) -> MapF ktp f -> m ()
- traverseMaybeWithKey :: forall {v} f k a b. Applicative f => (forall (tp :: v). k tp -> a tp -> f (Maybe (b tp))) -> MapF k a -> f (MapF k b)
- data UpdateRequest v
  - = Keep
  - | Set !v
  - | Delete
- data Updated a
  - = Updated !a
  - | Unchanged !a
- updatedValue :: Updated a -> a
- updateAtKey :: forall {v} k f (tp :: v) a. (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 :: OrdF k => (forall (tp :: v). 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 {v} k a b c m. (Applicative m, OrdF k) => (forall (tp :: v). 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 -> Type) (b :: k -> Type) where
  - Pair :: forall {k} (a :: k -> Type) (tp :: k) (b :: k -> Type). !(a tp) -> !(b tp) -> Pair a b

# Documentation

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

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

#### Instances

Instances details

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

Instance details

Defined in Data.Parameterized.Map

Methods

foldMapF :: Monoid m => (forall (s :: k). e s -> m) -> MapF ktp e -> m Source #

foldrF :: (forall (s :: k). e s -> b -> b) -> b -> MapF ktp e -> b Source #

foldlF :: (forall (s :: k). b -> e s -> b) -> b -> MapF ktp e -> b Source #

foldrF' :: (forall (s :: k). e s -> b -> b) -> b -> MapF ktp e -> b Source #

foldlF' :: (forall (s :: k). b -> e s -> b) -> b -> MapF ktp e -> b Source #

toListF :: (forall (tp :: k). f tp -> a) -> MapF ktp f -> [a] Source #

FunctorF (MapF ktp :: (k -> Type) -> Type) Source # |
Instance details Defined in Data.Parameterized.Map Methods fmapF :: (forall (x :: k). f x -> g x) -> MapF ktp f -> MapF ktp g Source #
TraversableF (MapF ktp :: (k -> Type) -> Type) Source # |
Instance details Defined in Data.Parameterized.Map Methods traverseF :: Applicative m => (forall (s :: k). e s -> m (f s)) -> MapF ktp e -> m (MapF ktp f) 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.
Instance details Defined in Data.Parameterized.Map Methods atF :: forall (x :: a). IndexF (MapF k v) x -> Lens' (MapF k v) (Maybe (IxValueF (MapF k v) x)) Source #
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.
Instance details Defined in Data.Parameterized.Map Methods ixF :: forall (x :: a). IndexF (MapF k v) x -> Traversal' (MapF k v) (IxValueF (MapF k v) x) Source #
(ShowF ktp, ShowF rtp) => Show (MapF ktp rtp) Source # |
Instance details Defined in Data.Parameterized.Map Methods showsPrec :: Int -> MapF ktp rtp -> ShowS Source # show :: MapF ktp rtp -> String Source # showList :: [MapF ktp rtp] -> ShowS Source #
(TestEquality k, EqF a) => Eq (MapF k a) Source # |
Instance details Defined in Data.Parameterized.Map Methods (==) :: MapF k a -> MapF k a -> Bool Source # (/=) :: MapF k a -> MapF k a -> Bool Source #
IsBinTree (MapF k2 a) (Pair k2 a) Source # |
Instance details Defined in Data.Parameterized.Map Methods asBin :: MapF k2 a -> TreeApp (Pair k2 a) (MapF k2 a) Source # tip :: MapF k2 a Source # bin :: Pair k2 a -> MapF k2 a -> MapF k2 a -> MapF k2 a Source # size :: MapF k2 a -> Int Source #
type IndexF (MapF k2 v) Source # |
Instance details Defined in Data.Parameterized.Map type IndexF (MapF k2 v) = k2
type IxValueF (MapF k2 v) Source # |
Instance details Defined in Data.Parameterized.Map type IxValueF (MapF k2 v) = v

# Construction

empty :: forall {v} (k :: v -> Type) (a :: v -> Type). MapF k a Source #

Return empty map

singleton :: forall {v} k (tp :: v) a. k tp -> a tp -> MapF k a Source #

Return map containing a single element

insert :: forall {v} k (tp :: v) a. 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.

insertWith :: forall {v} k a (tp :: v). OrdF k => (a tp -> a tp -> a tp) -> k tp -> a tp -> MapF k a -> MapF k a Source #

`insertWith f new m` inserts the binding into `m`.

It inserts `f new old` if `m` already contains an equivalent value `old`, and `new` otherwise. It returns an `Unchanged` value if the map stays the same size and an `Updated` value if a new entry was inserted.

delete :: forall {v} k (tp :: v) (a :: v -> Type). OrdF k => k tp -> MapF k a -> MapF k a Source #

Delete a value from the map if present.

union :: forall {v} (k :: v -> Type) (a :: v -> Type). 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 :: v). 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

null :: forall {v} (k :: v -> Type) (a :: v -> Type). MapF k a -> Bool Source #

Return true if map is empty

lookup :: forall {v} k (tp :: v) a. OrdF k => k tp -> MapF k a -> Maybe (a tp) Source #

Lookup value in map.

findWithDefault :: forall {v} k a (tp :: v). 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.

member :: forall {v} k (tp :: v) (a :: v -> Type). OrdF k => k tp -> MapF k a -> Bool Source #

Return true if key is bound in map.

notMember :: forall {v} k (tp :: v) (a :: v -> Type). OrdF k => k tp -> MapF k a -> Bool Source #

Return true if key is not bound in map.

size :: IsBinTree t e => t -> Int Source #

# Conversion

keys :: forall {k1} (k2 :: k1 -> Type) (a :: k1 -> Type). MapF k2 a -> [Some k2] Source #

Return all keys of the map in ascending order.

elems :: forall {k1} (k2 :: k1 -> Type) (a :: k1 -> Type). MapF k2 a -> [Some a] Source #

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

fromList :: forall {v} (k :: v -> Type) (a :: v -> Type). OrdF k => [Pair k a] -> MapF k a Source #

Create a Map from a list of pairs.

toList :: forall {k1} (k2 :: k1 -> Type) (a :: k1 -> Type). MapF k2 a -> [Pair k2 a] Source #

Return list of key-values pairs in map.

toAscList :: forall {k1} (k2 :: k1 -> Type) (a :: k1 -> Type). MapF k2 a -> [Pair k2 a] Source #

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

toDescList :: forall {k1} (k2 :: k1 -> Type) (a :: k1 -> Type). MapF k2 a -> [Pair k2 a] Source #

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

fromKeys Source #

Arguments

:: forall k m t a v. (Monad m, Foldable t, OrdF a) |
=> (forall (tp :: k). 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.

fromKeysM Source #

Arguments

:: forall k m t a v. (Monad m, Foldable t, OrdF a) |
=> (forall (tp :: k). 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 {v} f (k :: v -> Type). (forall (tp :: v). f tp -> Bool) -> MapF k f -> MapF k f Source #

Return entries with values that satisfy a predicate.

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

Return key-value pairs that satisfy a predicate.

filterGt :: forall {v1} k (tp :: v1) (v2 :: v1 -> Type). OrdF k => k tp -> MapF k v2 -> MapF k v2 Source #

`filterGt k m` returns submap of `m` that only contains entries that are larger than `k`.

filterLt :: forall {v1} k (tp :: v1) (v2 :: v1 -> Type). OrdF k => k tp -> MapF k v2 -> MapF k v2 Source #

`filterLt k m` returns submap of `m` that only contains entries that are smaller than `k`.

# Folds

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

Perform a left fold with the key also provided.

foldlWithKey' :: (forall (s :: v). 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 :: v). k s -> a s -> b -> b) -> b -> MapF k a -> b Source #

Perform a right fold with the key also provided.

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

Perform a strict right fold with the key also provided.

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

Fold the keys and values using the given monoid.

foldlMWithKey :: forall {v} m b k a. Monad m => (forall (s :: v). 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 :: forall {v} m k a b. Monad m => (forall (s :: v). 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

map :: forall {v} f g (ktp :: v -> Type). (forall (tp :: v). f tp -> g tp) -> MapF ktp f -> MapF ktp g Source #

Modify elements in a map

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

Apply function to all elements in map.

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

Map elements and collect `Just` results.

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

Map keys and elements and collect `Just` results.

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

Traverse elements in a map

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

Traverse elements in a map without returning result.

traverseMaybeWithKey :: forall {v} f k a b. Applicative f => (forall (tp :: v). 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

Constructors

Keep | Keep the current value.
Set !v | Set the value to a new value.
Delete | Delete a value.

data Updated a Source #

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

Constructors

Updated !a |
Unchanged !a |

updatedValue :: Updated a -> a Source #

updateAtKey Source #

Arguments

:: forall {v} k f (tp :: v) a. (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 :: OrdF k => (forall (tp :: v). 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 {v} k a b c m. (Applicative m, OrdF k) => (forall (tp :: v). 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 -> Type) (b :: k -> Type) where Source #

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

Constructors

Pair :: forall {k} (a :: k -> Type) (tp :: k) (b :: k -> Type). !(a tp) -> !(b tp) -> Pair a b |

#### Instances

Instances details

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

Instance details

Defined in Data.Parameterized.Pair

Methods

foldMapF :: Monoid m => (forall (s :: k). e s -> m) -> Pair a e -> m Source #

foldrF :: (forall (s :: k). e s -> b -> b) -> b -> Pair a e -> b Source #

foldlF :: (forall (s :: k). b -> e s -> b) -> b -> Pair a e -> b Source #

foldrF' :: (forall (s :: k). e s -> b -> b) -> b -> Pair a e -> b Source #

foldlF' :: (forall (s :: k). b -> e s -> b) -> b -> Pair a e -> b Source #

toListF :: (forall (tp :: k). f tp -> a0) -> Pair a f -> [a0] Source #

FunctorF (Pair a :: (k -> Type) -> Type) Source # |
Instance details Defined in Data.Parameterized.Pair Methods fmapF :: (forall (x :: k). f x -> g x) -> Pair a f -> Pair a g Source #
(TestEquality a, EqF b) => Eq (Pair a b) Source # |
Instance details Defined in Data.Parameterized.Pair Methods (==) :: Pair a b -> Pair a b -> Bool Source # (/=) :: Pair a b -> Pair a b -> Bool Source #
IsBinTree (MapF k2 a) (Pair k2 a) Source # |
Instance details Defined in Data.Parameterized.Map Methods asBin :: MapF k2 a -> TreeApp (Pair k2 a) (MapF k2 a) Source # tip :: MapF k2 a Source # bin :: Pair k2 a -> MapF k2 a -> MapF k2 a -> MapF k2 a Source # size :: MapF k2 a -> Int Source #