Safe Haskell | None |
---|---|

Language | Haskell2010 |

## Synopsis

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

# Documentation

A map from keys `k`

to values `v`

.

Map (Map Array UnliftedArray k v) |

## Instances

(Ord k, PrimUnlifted v) => IsList (Map k v) Source # | |

(Eq k, Eq v, PrimUnlifted v) => Eq (Map k v) Source # | |

(Ord k, Ord v, PrimUnlifted v) => Ord (Map k v) Source # | |

(Show k, Show v, PrimUnlifted v) => Show (Map k v) Source # | |

(Ord k, Semigroup v, PrimUnlifted v) => Semigroup (Map k v) Source # | |

(Ord k, Semigroup v, PrimUnlifted v) => Monoid (Map k v) Source # | |

type Item (Map k v) Source # | |

Defined in Data.Map.Lifted.Unlifted |

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

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

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

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

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

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

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

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

.

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

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

union :: (Ord k, PrimUnlifted v) => Map k v -> Map k v -> Map k v Source #

*O(n+m)* The expression (

) takes the left-biased union
of `union`

t1 t2`t1`

and `t2`

. It prefers `t1`

when duplicate keys are encountered.

# Folds

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

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

:: (Monoid b, 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.

# Monadic Folds

:: (Monad m, 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.

:: (Monad m, 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.

:: (Monad m, Monoid b, 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.

:: (Monad m, Monoid b, 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 f, PrimUnlifted v, PrimUnlifted b) => (v -> f b) -> Map k v -> f (Map k b) Source #

*O(n)* traversal over the values in the map.

traverseWithKey :: (Applicative f, 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.

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

*O(n)* like `traverseWithKey`

, but discards the results.

# List Conversion

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

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

fromList :: (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 :: (Ord k, Semigroup v, PrimUnlifted v) => [(k, v)] -> Map k v Source #

:: (Ord k, PrimUnlifted v) | |

=> Int | expected size of resulting |

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

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

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

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