Data.Parameterized.Map

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

Some code was adapted from containers.

Documentation

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

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

Instances

FoldableF (MapF ktp :: (k -> Type) -> Type)

Defined in Data.Parameterized.Map

Methods

foldMapF :: Monoid m => (forall (s :: k0). e s -> m) -> MapF ktp e -> m

foldrF :: (forall (s :: k0). e s -> b -> b) -> b -> MapF ktp e -> b

foldlF :: (forall (s :: k0). b -> e s -> b) -> b -> MapF ktp e -> b

foldrF' :: (forall (s :: k0). e s -> b -> b) -> b -> MapF ktp e -> b

foldlF' :: (forall (s :: k0). b -> e s -> b) -> b -> MapF ktp e -> b

toListF :: (forall (tp :: k0). f tp -> a) -> MapF ktp f -> [a]

FunctorF (MapF ktp :: (k -> Type) -> Type)

Defined in Data.Parameterized.Map

Methods

fmapF :: (forall (x :: k0). f x -> g x) -> MapF ktp f -> MapF ktp g

TraversableF (MapF ktp :: (k -> Type) -> Type)

Defined in Data.Parameterized.Map

Methods

traverseF :: Applicative m => (forall (s :: k0). e s -> m (f s)) -> MapF ktp e -> m (MapF ktp f)

OrdF k => AtF a (MapF k v)

Turn a map key into a lens that points into the indicated position in the map.

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

OrdF k => IxedF a (MapF k v)

Turn a map key into a traversal that visits the indicated element in the map, if it exists.

Defined in Data.Parameterized.Map

Methods

ixF :: forall (x :: a). IndexF (MapF k v) x -> Traversal' (MapF k v) (IxValueF (MapF k v) x)

(ShowF ktp, ShowF rtp) => Show (MapF ktp rtp)

Defined in Data.Parameterized.Map

Methods

showsPrec :: Int -> MapF ktp rtp -> ShowS

show :: MapF ktp rtp -> String

showList :: [MapF ktp rtp] -> ShowS

(TestEquality k, EqF a) => Eq (MapF k a)

Defined in Data.Parameterized.Map

Methods

(==) :: MapF k a -> MapF k a -> Bool

(/=) :: MapF k a -> MapF k a -> Bool

IsBinTree (MapF k2 a) (Pair k2 a)

Defined in Data.Parameterized.Map

Methods

asBin :: MapF k2 a -> TreeApp (Pair k2 a) (MapF k2 a)

tip :: MapF k2 a

bin :: Pair k2 a -> MapF k2 a -> MapF k2 a -> MapF k2 a

size :: MapF k2 a -> Int

type IndexF (MapF k2 v)

Defined in Data.Parameterized.Map

type IndexF (MapF k2 v) = k2

type IxValueF (MapF k2 v)

Defined in Data.Parameterized.Map

type IxValueF (MapF k2 v) = v

Construction

empty :: MapF k a

Return empty map

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

Return map containing a single element

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

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

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

Delete a value from the map if present.

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

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

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 :: MapF k a -> Bool

Return true if map is empty

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

Lookup value in map.

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

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 :: OrdF k => k tp -> MapF k a -> Bool

Return true if key is bound in map.

notMember :: OrdF k => k tp -> MapF k a -> Bool

Return true if key is not bound in map.

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

Conversion

keys :: MapF k a -> [Some k]

Return all keys of the map in ascending order.

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

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

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

Create a Map from a list of pairs.

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

Return list of key-values pairs in map.

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

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

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

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

fromKeys

Arguments

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

fromKeysM

Arguments

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

Return entries with values that satisfy a predicate.

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

Return key-value pairs that satisfy a predicate.

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

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

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

Perform a left fold with the key also provided.

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

Perform a strict left fold with the key also provided.

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

Perform a right fold with the key also provided.

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

Perform a strict right fold with the key also provided.

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

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

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

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

Traversals

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

Modify elements in a map

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

Apply function to all elements in map.

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

Map elements and collect Just results.

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

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)

Traverse elements in a map

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

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)

Traverse keys/values and collect the Just results.

Complex interface.

data UpdateRequest v

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

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

updateAtKey

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.

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

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)

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

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)

Defined in Data.Parameterized.Pair

Methods

foldMapF :: Monoid m => (forall (s :: k0). e s -> m) -> Pair a e -> m

foldrF :: (forall (s :: k0). e s -> b -> b) -> b -> Pair a e -> b

foldlF :: (forall (s :: k0). b -> e s -> b) -> b -> Pair a e -> b

foldrF' :: (forall (s :: k0). e s -> b -> b) -> b -> Pair a e -> b

foldlF' :: (forall (s :: k0). b -> e s -> b) -> b -> Pair a e -> b

toListF :: (forall (tp :: k0). f tp -> a0) -> Pair a f -> [a0]

FunctorF (Pair a :: (k -> Type) -> Type)

Defined in Data.Parameterized.Pair

Methods

fmapF :: (forall (x :: k0). f x -> g x) -> Pair a f -> Pair a g

(TestEquality a, EqF b) => Eq (Pair a b)

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)

Defined in Data.Parameterized.Map

Methods

asBin :: MapF k2 a -> TreeApp (Pair k2 a) (MapF k2 a)

tip :: MapF k2 a

bin :: Pair k2 a -> MapF k2 a -> MapF k2 a -> MapF k2 a

size :: MapF k2 a -> Int