Safe Haskell	None
Language	Haskell2010

Data.Map.Lifted.Lifted

Contents

Folds
Monadic Folds
List Conversion

Synopsis

newtype Map k v = Map (Map Array Array k v)
empty :: Map k v
singleton :: k -> v -> Map k v
lookup :: Ord k => k -> Map k v -> Maybe v
size :: Map k v -> Int
map :: (v -> w) -> Map k v -> Map k w
mapMaybe :: (v -> Maybe w) -> Map k v -> Map k w
mapMaybeWithKey :: (k -> v -> Maybe w) -> Map k v -> Map k w
appendWithKey :: Ord k => (k -> v -> v -> v) -> Map k v -> Map k v -> Map k v
union :: Ord k => Map k v -> Map k v -> Map k v
foldlWithKey' :: (b -> k -> v -> b) -> b -> Map k v -> b
foldrWithKey' :: (k -> v -> b -> b) -> b -> Map k v -> b
foldMapWithKey' :: Monoid b => (k -> v -> b) -> Map k v -> b
foldlWithKeyM' :: Monad m => (b -> k -> v -> m b) -> b -> Map k v -> m b
foldrWithKeyM' :: Monad m => (k -> v -> b -> m b) -> b -> Map k v -> m b
foldlMapWithKeyM' :: (Monad m, Monoid b) => (k -> v -> m b) -> Map k v -> m b
foldrMapWithKeyM' :: (Monad m, Monoid b) => (k -> v -> m b) -> Map k v -> m b
toList :: Ord k => Map k v -> [(k, v)]
fromList :: Ord k => [(k, v)] -> Map k v
fromListAppend :: (Ord k, Semigroup v) => [(k, v)] -> Map k v
fromListN :: Ord k => Int -> [(k, v)] -> Map k v
fromListAppendN :: (Ord k, Semigroup v) => Int -> [(k, v)] -> Map k v
fromSet :: (k -> v) -> Set k -> Map k v
keys :: Map k v -> Set k
elems :: Map k v -> Array v

Documentation

newtype Map k v Source #

A map from keys k to values v.

Constructors

Map (Map Array Array k v)

Instances

Functor (Map k) Source #
Instance details Defined in Data.Map.Lifted.Lifted Methods fmap :: (a -> b) -> Map k a -> Map k b # (<$) :: a -> Map k b -> Map k a #
Ord k => IsList (Map k v) Source #
Instance details Defined in Data.Map.Lifted.Lifted Associated Types type Item (Map k v) :: Type # Methods fromList :: [Item (Map k v)] -> Map k v # fromListN :: Int -> [Item (Map k v)] -> Map k v # toList :: Map k v -> [Item (Map k v)] #
(Eq k, Eq v) => Eq (Map k v) Source #
Instance details Defined in Data.Map.Lifted.Lifted Methods (==) :: Map k v -> Map k v -> Bool # (/=) :: Map k v -> Map k v -> Bool #
(Ord k, Ord v) => Ord (Map k v) Source #
Instance details Defined in Data.Map.Lifted.Lifted Methods compare :: Map k v -> Map k v -> Ordering # (<) :: Map k v -> Map k v -> Bool # (<=) :: Map k v -> Map k v -> Bool # (>) :: Map k v -> Map k v -> Bool # (>=) :: Map k v -> Map k v -> Bool # max :: Map k v -> Map k v -> Map k v # min :: Map k v -> Map k v -> Map k v #
(Show k, Show v) => Show (Map k v) Source #
Instance details Defined in Data.Map.Lifted.Lifted Methods showsPrec :: Int -> Map k v -> ShowS # show :: Map k v -> String # showList :: [Map k v] -> ShowS #
(Ord k, Semigroup v) => Semigroup (Map k v) Source #
Instance details Defined in Data.Map.Lifted.Lifted Methods (<>) :: Map k v -> Map k v -> Map k v # sconcat :: NonEmpty (Map k v) -> Map k v # stimes :: Integral b => b -> Map k v -> Map k v #
(Ord k, Semigroup v) => Monoid (Map k v) Source #
Instance details Defined in Data.Map.Lifted.Lifted Methods mempty :: Map k v # mappend :: Map k v -> Map k v -> Map k v # mconcat :: [Map k v] -> Map k v #
type Item (Map k v) Source #
Instance details Defined in Data.Map.Lifted.Lifted type Item (Map k v) = (k, v)

empty :: Map k v Source #

The empty diet map.

singleton :: k -> v -> Map k v Source #

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

lookup :: Ord k => k -> Map k v -> Maybe v Source #

O(log n) Lookup the value at a key in the map.

size :: Map k v -> Int Source #

O(1) The number of elements in the map.

map :: (v -> w) -> Map k v -> Map k w Source #

O(n) Map over the values in the map.

mapMaybe :: (v -> Maybe w) -> Map k v -> Map k w Source #

O(n) Drop elements for which the predicate returns Nothing.

mapMaybeWithKey :: (k -> v -> Maybe w) -> Map k v -> Map k w Source #

O(n) Drop elements for which the predicate returns Nothing. The predicate is given access to the key.

appendWithKey :: Ord k => (k -> v -> v -> v) -> Map k v -> Map k v -> Map k v Source #

union :: Ord k => Map k v -> Map k v -> Map k v Source #

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.

Folds

foldlWithKey' Source #

Arguments

:: (b -> k -> v -> b)	reduction
-> b	initial accumulator
-> Map k v	map
-> b

O(n) Left fold over the keys and values with a strict accumulator.

foldrWithKey' Source #

Arguments

:: (k -> v -> b -> b)	reduction
-> b	initial accumulator
-> Map k v	map
-> b

O(n) Right fold over the keys and values with a strict accumulator.

foldMapWithKey' Source #

Arguments

:: Monoid b
=> (k -> v -> b)	reduction
-> Map k v	map
-> b

O(n) Fold over the keys and values of the map with a strict monoidal accumulator. This function does not have left and right variants since the associativity required by a monoid instance means that both variants would always produce the same result.

Monadic Folds

foldlWithKeyM' Source #

Arguments

:: Monad m
=> (b -> k -> v -> m b)	reduction
-> b	initial accumulator
-> Map k v	map
-> m b

O(n) Left monadic fold over the keys and values of the map. This fold is strict in the accumulator.

foldrWithKeyM' Source #

Arguments

:: Monad m
=> (k -> v -> b -> m b)	reduction
-> b	initial accumulator
-> Map k v	map
-> m b

O(n) Right monadic fold over the keys and values of the map. This fold is strict in the accumulator.

foldlMapWithKeyM' Source #

Arguments

:: (Monad m, Monoid b)
=> (k -> v -> m b)	reduction
-> Map k v	map
-> m b

O(n) Monadic left fold over the keys and values of the map with a strict monoidal accumulator. The monoidal accumulator is appended to the left after each reduction.

foldrMapWithKeyM' Source #

Arguments

:: (Monad m, Monoid b)
=> (k -> v -> m b)	reduction
-> Map k v	map
-> m b

O(n) Monadic right fold over the keys and values of the map with a strict monoidal accumulator. The monoidal accumulator is appended to the right after each reduction.

List Conversion

toList :: Ord k => Map k v -> [(k, v)] Source #

O(n) A list of key-value pairs in ascending order.

fromList :: Ord k => [(k, v)] -> Map k v Source #

O(n*log n) Create a map from a list of key-value pairs. If the list contains more than one value for the same key, the last value is retained. If the keys in the argument are in nondescending order, this algorithm runs in O(n) time instead.

fromListAppend :: (Ord k, Semigroup v) => [(k, v)] -> Map k v Source #

O(n*log n) This function has the same behavior as fromList, but it combines values with the Semigroup instances instead of choosing the last occurrence.

fromListN Source #

Arguments

:: Ord k
=> Int	expected size of resulting `Map`
-> [(k, v)]	key-value pairs
-> Map k v

O(n*log n) This function has the same behavior as fromList regardless of whether or not the expected size is accurate. Additionally, negative sizes are handled correctly. The expected size is used as the size of the initially allocated buffer when building the Map. If the keys in the argument are in nondescending order, this algorithm runs in O(n) time.

fromListAppendN Source #

Arguments

:: (Ord k, Semigroup v)
=> Int	expected size of resulting `Map`
-> [(k, v)]	key-value pairs
-> Map k v

O(n*log n) This function has the same behavior as fromListN, but it combines values with the Semigroup instances instead of choosing the last occurrence.

fromSet :: (k -> v) -> Set k -> Map k v Source #

O(n) Build a map from a set. This function is uses the underlying array that backs the set as the array for the keys. It constructs the values by apply the given function to each key.

keys :: Map k v -> Set k Source #

O(1) The values in a map. This is a zero-cost operation.

elems :: Map k v -> Array v Source #

O(1) The values in a map. This is a zero-cost operation.