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

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 :: 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
null :: MapF k a -> Bool
lookup :: OrdF k => k tp -> MapF k a -> Maybe (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]
fromKeys :: forall 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 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
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 ()
data UpdateRequest v
- = Keep
- | Set !v
- | Delete
data Updated a
- = Updated !a
- | Unchanged !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))
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
- Pair :: !(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

TraversableF (MapF ktp :: (k -> Type) -> Type) Source #
Instance details Defined in Data.Parameterized.Map Methods traverseF :: Applicative m => (forall (s :: k0). e s -> m (f s)) -> MapF ktp e -> m (MapF ktp f) Source #
FoldableF (MapF ktp :: (k -> Type) -> Type) Source #
Instance details Defined in Data.Parameterized.Map Methods 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 #
Instance details Defined in Data.Parameterized.Map Methods fmapF :: (forall (x :: k0). f x -> g x) -> MapF ktp f -> MapF ktp g 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 :: 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 :: IndexF (MapF k v) x -> Traversal' (MapF k v) (IxValueF (MapF k v) x) 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 # (/=) :: MapF k a -> MapF k a -> Bool #
(ShowF ktp, ShowF rtp) => Show (MapF ktp rtp) Source #
Instance details Defined in Data.Parameterized.Map Methods showsPrec :: Int -> MapF ktp rtp -> ShowS # show :: MapF ktp rtp -> String # showList :: [MapF ktp rtp] -> ShowS #
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 IxValueF (MapF k2 v) Source #
Instance details Defined in Data.Parameterized.Map type IxValueF (MapF k2 v) = v
type IndexF (MapF k2 v) Source #
Instance details Defined in Data.Parameterized.Map type IndexF (MapF k2 v) = k2

Construction

empty :: MapF k a Source #

Return empty map

singleton :: k tp -> a tp -> MapF k a Source #

Return map containing a single element

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.

insertWith :: 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 :: OrdF k => k tp -> MapF k a -> MapF k a Source #

Delete a value from the map if present.

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

Union two sets

Query

null :: MapF k a -> Bool Source #

Return true if map is empty

lookup :: OrdF k => k tp -> MapF k a -> Maybe (a tp) Source #

Lookup value in map.

member :: OrdF k => k tp -> MapF k a -> Bool Source #

Return true if key is bound in map.

notMember :: 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 :: MapF k a -> [Some k] Source #

Return all keys of the map in ascending order.

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

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

fromList :: OrdF k => [Pair k a] -> MapF k a Source #

Create a Map from a list of pairs.

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

fromKeys Source #

Arguments

:: forall (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.

fromKeysM Source #

Arguments

:: forall (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.

Traversals

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

Modify elements in a map

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.

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

:: (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.

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 to get a third.

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.

Constructors

Pair :: !(a tp) -> !(b tp) -> Pair a b

Instances

FoldableF (Pair a :: (k -> Type) -> Type) Source #
Instance details Defined in Data.Parameterized.Pair Methods 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 #
Instance details Defined in Data.Parameterized.Pair Methods fmapF :: (forall (x :: k0). 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 # (/=) :: Pair a b -> Pair a b -> Bool #
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 #