Module

# Data.Map

Package
purescript-maps
Repository
purescript/purescript-maps

This module defines a type of maps as balanced 2-3 trees, based on http://www.cs.princeton.edu/~dpw/courses/cos326-12/ass/2-3-trees.pdf

### #MapSource

``data Map k v``

`Map k v` represents maps from keys of type `k` to values of type `v`.

#### Instances

• `(Eq k) => Eq1 (Map k)`
• `(Eq k, Eq v) => Eq (Map k v)`
• `(Ord k) => Ord1 (Map k)`
• `(Ord k, Ord v) => Ord (Map k v)`
• `(Show k, Show v) => Show (Map k v)`
• `(Ord k) => Semigroup (Map k v)`
• `(Ord k) => Monoid (Map k v)`
• `Functor (Map k)`
• `Foldable (Map k)`
• `Traversable (Map k)`

### #showTreeSource

``showTree :: forall k v. Show k => Show v => Map k v -> String``

Render a `Map` as a `String`

### #emptySource

``empty :: forall k v. Map k v``

An empty map

### #isEmptySource

``isEmpty :: forall k v. Map k v -> Boolean``

Test if a map is empty

### #singletonSource

``singleton :: forall k v. k -> v -> Map k v``

Create a map with one key/value pair

### #checkValidSource

``checkValid :: forall k v. Map k v -> Boolean``

Check whether the underlying tree satisfies the 2-3 invariant

This function is provided for internal use.

### #lookupSource

``lookup :: forall k v. Ord k => k -> Map k v -> Maybe v``

Look up a value for the specified key

### #lookupLESource

``lookupLE :: forall k v. Ord k => k -> Map k v -> Maybe { key :: k, value :: v }``

Look up a value for the specified key, or the greatest one less than it

### #lookupLTSource

``lookupLT :: forall k v. Ord k => k -> Map k v -> Maybe { key :: k, value :: v }``

Look up a value for the greatest key less than the specified key

### #lookupGESource

``lookupGE :: forall k v. Ord k => k -> Map k v -> Maybe { key :: k, value :: v }``

Look up a value for the specified key, or the least one greater than it

### #lookupGTSource

``lookupGT :: forall k v. Ord k => k -> Map k v -> Maybe { key :: k, value :: v }``

Look up a value for the least key greater than the specified key

### #findMaxSource

``findMax :: forall k v. Map k v -> Maybe { key :: k, value :: v }``

Returns the pair with the greatest key

### #findMinSource

``findMin :: forall k v. Map k v -> Maybe { key :: k, value :: v }``

Returns the pair with the least key

### #foldSubmapSource

``foldSubmap :: forall k v m. Ord k => Monoid m => Maybe k -> Maybe k -> (k -> v -> m) -> Map k v -> m``

Fold over the entries of a given map where the key is between a lower and an upper bound. Passing `Nothing` as either the lower or upper bound argument means that the fold has no lower or upper bound, i.e. the fold starts from (or ends with) the smallest (or largest) key in the map.

``````foldSubmap (Just 1) (Just 2) (\_ v -> [v])
(fromFoldable [Tuple 0 "zero", Tuple 1 "one", Tuple 2 "two", Tuple 3 "three"])
== ["one", "two"]

foldSubmap Nothing (Just 2) (\_ v -> [v])
(fromFoldable [Tuple 0 "zero", Tuple 1 "one", Tuple 2 "two", Tuple 3 "three"])
== ["zero", "one", "two"]
``````

### #submapSource

``submap :: forall k v. Ord k => Maybe k -> Maybe k -> Map k v -> Map k v``

Returns a new map containing all entries of the given map which lie between a given lower and upper bound, treating `Nothing` as no bound i.e. including the smallest (or largest) key in the map, no matter how small (or large) it is. For example:

``````submap (Just 1) (Just 2)
(fromFoldable [Tuple 0 "zero", Tuple 1 "one", Tuple 2 "two", Tuple 3 "three"])
== fromFoldable [Tuple 1 "one", Tuple 2 "two"]

submap Nothing (Just 2)
(fromFoldable [Tuple 0 "zero", Tuple 1 "one", Tuple 2 "two", Tuple 3 "three"])
== fromFoldable [Tuple 0 "zero", Tuple 1 "one", Tuple 2 "two"]
``````

The function is entirely specified by the following property:

``````Given any m :: Map k v, mmin :: Maybe k, mmax :: Maybe k, key :: k,
let m' = submap mmin mmax m in
if (maybe true (\min -> min <= key) mmin &&
maybe true (\max -> max >= key) mmax)
then lookup key m == lookup key m'
else not (member key m')
``````

### #memberSource

``member :: forall k v. Ord k => k -> Map k v -> Boolean``

Test if a key is a member of a map

### #insertSource

``insert :: forall k v. Ord k => k -> v -> Map k v -> Map k v``

Insert or replace a key/value pair in a map

### #deleteSource

``delete :: forall k v. Ord k => k -> Map k v -> Map k v``

Delete a key and its corresponding value from a map.

### #popSource

``pop :: forall k v. Ord k => k -> Map k v -> Maybe (Tuple v (Map k v))``

Delete a key and its corresponding value from a map, returning the value as well as the subsequent map.

### #alterSource

``alter :: forall k v. Ord k => (Maybe v -> Maybe v) -> k -> Map k v -> Map k v``

Insert the value, delete a value, or update a value for a key in a map

``update :: forall k v. Ord k => (v -> Maybe v) -> k -> Map k v -> Map k v``

Update or delete the value for a key in a map

### #fromFoldableSource

``fromFoldable :: forall f k v. Ord k => Foldable f => f (Tuple k v) -> Map k v``

Convert any foldable collection of key/value pairs to a map. On key collision, later values take precedence over earlier ones.

### #fromFoldableWithSource

``fromFoldableWith :: forall f k v. Ord k => Foldable f => (v -> v -> v) -> f (Tuple k v) -> Map k v``

Convert any foldable collection of key/value pairs to a map. On key collision, the values are configurably combined.

### #toUnfoldableSource

``toUnfoldable :: forall f k v. Unfoldable f => Map k v -> f (Tuple k v)``

Convert a map to an unfoldable structure of key/value pairs

### #toAscUnfoldableSource

``toAscUnfoldable :: forall f k v. Unfoldable f => Map k v -> f (Tuple k v)``

Convert a map to an unfoldable structure of key/value pairs where the keys are in ascending order

### #keysSource

``keys :: forall k v. Map k v -> List k``

Get a list of the keys contained in a map

### #valuesSource

``values :: forall k v. Map k v -> List v``

Get a list of the values contained in a map

### #unionWithSource

``unionWith :: forall k v. Ord k => (v -> v -> v) -> Map k v -> Map k v -> Map k v``

Compute the union of two maps, using the specified function to combine values for duplicate keys.

### #unionSource

``union :: forall k v. Ord k => Map k v -> Map k v -> Map k v``

Compute the union of two maps, preferring values from the first map in the case of duplicate keys

### #unionsSource

``unions :: forall k v f. Ord k => Foldable f => f (Map k v) -> Map k v``

Compute the union of a collection of maps

### #isSubmapSource

``isSubmap :: forall k v. Ord k => Eq v => Map k v -> Map k v -> Boolean``

Test whether one map contains all of the keys and values contained in another map

### #sizeSource

``size :: forall k v. Map k v -> Int``

Calculate the number of key/value pairs in a map

### #mapWithKeySource

``mapWithKey :: forall k v v'. (k -> v -> v') -> Map k v -> Map k v'``

Apply a function of two arguments to each key/value pair, producing a new map

### #filterWithKeySource

``filterWithKey :: forall k v. Ord k => (k -> v -> Boolean) -> Map k v -> Map k v``

Filter out those key/value pairs of a map for which a predicate fails to hold.

### #filterKeysSource

``filterKeys :: forall k. Ord k => (k -> Boolean) -> (Map k) ~> (Map k)``

Filter out those key/value pairs of a map for which a predicate on the key fails to hold.

### #filterSource

``filter :: forall k v. Ord k => (v -> Boolean) -> Map k v -> Map k v``

Filter out those key/value pairs of a map for which a predicate on the value fails to hold.