primitive-containers-0.4.1: containers backed by arrays

Data.Map.Unboxed.Unlifted

Synopsis

# Documentation

data Map k v Source #

A map from keys k to values v. The key type and the value type must both have Prim instances.

Instances
 (Prim k, Ord k, PrimUnlifted v) => IsList (Map k v) Source # Instance detailsDefined in Data.Map.Unboxed.Unlifted Associated Typestype Item (Map k v) :: Type # MethodsfromList :: [Item (Map k v)] -> Map k v #fromListN :: Int -> [Item (Map k v)] -> Map k v #toList :: Map k v -> [Item (Map k v)] # (Prim k, Eq k, PrimUnlifted v, Eq v) => Eq (Map k v) Source # Instance detailsDefined in Data.Map.Unboxed.Unlifted Methods(==) :: Map k v -> Map k v -> Bool #(/=) :: Map k v -> Map k v -> Bool # (Prim k, Ord k, PrimUnlifted v, Ord v) => Ord (Map k v) Source # Instance detailsDefined in Data.Map.Unboxed.Unlifted Methodscompare :: 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 # (Prim k, Show k, PrimUnlifted v, Show v) => Show (Map k v) Source # Instance detailsDefined in Data.Map.Unboxed.Unlifted MethodsshowsPrec :: Int -> Map k v -> ShowS #show :: Map k v -> String #showList :: [Map k v] -> ShowS # (Prim k, Ord k, PrimUnlifted v, Semigroup v) => Semigroup (Map k v) Source # Instance detailsDefined in Data.Map.Unboxed.Unlifted 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 # (Prim k, Ord k, PrimUnlifted v, Semigroup v) => Monoid (Map k v) Source # Instance detailsDefined in Data.Map.Unboxed.Unlifted Methodsmempty :: 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 detailsDefined in Data.Map.Unboxed.Unlifted type Item (Map k v) = (k, v)

empty :: Map k v Source #

The empty diet map.

singleton :: (Prim k, PrimUnlifted v) => k -> v -> Map k v Source #

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

lookup :: (Prim k, Ord k, PrimUnlifted v) => k -> Map k v -> Maybe v Source #

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

size :: PrimUnlifted v => Map k v -> Int Source #

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

# Transform

map :: (Prim k, PrimUnlifted v, PrimUnlifted w) => (v -> w) -> Map k v -> Map k w Source #

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

mapLifted :: (Prim k, PrimUnlifted v) => (v -> w) -> Map k v -> Map k w Source #

O(n) Map over the values in the map. The resulting map contains lifted values.

mapMaybe :: (Prim k, PrimUnlifted v, PrimUnlifted w) => (v -> Maybe w) -> Map k v -> Map k w Source #

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

mapMaybeP :: (PrimMonad m, Prim k, PrimUnlifted v, PrimUnlifted w) => (v -> m (Maybe w)) -> Map k v -> m (Map k w) Source #

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

mapMaybeWithKey :: (Prim k, PrimUnlifted v, PrimUnlifted w) => (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.

Arguments

 :: (Prim k, PrimUnlifted v, PrimMonad m, Ord k) => ((k -> (v -> m v) -> m ()) -> m a) Modification-applying function -> Map k v Map -> m (Map k v, a)

Update the values at any number of keys. This is done on in a buffer without building intermediate maps. Example use:

adjustMany
adjust 2 (\x -> pure (x + 1))
adjust 3 (\_ -> pure 42)
) myMap

This increments by 1 the value associated with key 2. Then, it replaces with 42 the value associated with key 3.

# Folds

Arguments

 :: (Prim k, PrimUnlifted v) => (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.

Arguments

 :: (Prim k, PrimUnlifted v) => (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.

Arguments

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

O(n) Fold over the keys and values of the map with a 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.

Arguments

 :: (Monoid b, Prim k, PrimUnlifted v) => (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.

Arguments

 :: (Monad m, Prim k, PrimUnlifted v) => (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.

Arguments

 :: (Monad m, Prim k, PrimUnlifted v) => (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.

Arguments

 :: (Monad m, Monoid b, Prim k, PrimUnlifted v) => (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.

Arguments

 :: (Monad m, Monoid b, Prim k, PrimUnlifted v) => (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.

# Traversals

traverse :: (Applicative m, Prim k, PrimUnlifted v, PrimUnlifted b) => (v -> m b) -> Map k v -> m (Map k b) Source #

O(n) Traverse the values of the map.

traverseWithKey :: (Applicative f, Prim k, PrimUnlifted v, PrimUnlifted b) => (k -> v -> f b) -> Map k v -> f (Map k b) Source #

O(n) traversal over the values in the map, using the keys.

Arguments

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

O(n) Traverse the keys and values of the map from left to right.

# List Conversion

fromList :: (Prim k, Ord k, PrimUnlifted v) => [(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 :: (Prim k, Ord k, PrimUnlifted v, 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.

Arguments

 :: (Prim k, Ord k, PrimUnlifted 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 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.

Arguments

 :: (Prim k, Ord k, PrimUnlifted v, 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 :: (Prim k, PrimUnlifted v) => (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.

fromSetP :: (PrimMonad m, Prim k, PrimUnlifted v) => (k -> m v) -> Set k -> m (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. The function can perform primitive monadic effects.

# Array Conversion

unsafeFreezeZip :: (Ord k, Prim k, PrimUnlifted v) => MutablePrimArray s k -> MutableUnliftedArray s v -> ST s (Map k v) Source #

O(n*log n) Zip an array of keys with an array of values. If they are not the same length, the longer one will be truncated to match the shorter one. This function sorts and deduplicates the array of keys, preserving the last value associated with each key. The argument arrays may not be reused after being passed to this function.

This is by far the fastest way to create a map, since the functions backing it are aggressively specialized. It internally uses a hybrid of mergesort and insertion sort provided by the primitive-sort package. It generates much less garbage than any of the fromList variants.