# Data.Map.Internal

- Package
- purescript-ordered-collections
- Repository
- purescript/purescript-ordered-collections

This module defines a type of maps as height-balanced (AVL) binary trees. Efficient set operations are implemented in terms of https://www.cs.cmu.edu/~guyb/papers/BFS16.pdf

### #Map Source

`data Map k`_{} v

`Map k v`

represents maps from keys of type `k`

to values of type `v`

.

#### Constructors

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

`(Warn (Text "Data.Map\'s `Semigroup` instance is now unbiased and differs from the left-biased instance defined in PureScript releases <= 0.13.x."), Ord k, Semigroup v) => Semigroup (Map k v)`

`(Warn (Text "Data.Map\'s `Semigroup` instance is now unbiased and differs from the left-biased instance defined in PureScript releases <= 0.13.x."), Ord k, Semigroup v) => Monoid (Map k v)`

`(Ord k) => Alt (Map k)`

`(Ord k) => Plus (Map k)`

`Functor (Map k)`

`FunctorWithIndex k (Map k)`

`(Ord k) => Apply (Map k)`

`(Ord k) => Bind (Map k)`

`Foldable (Map k)`

`FoldableWithIndex k (Map k)`

`Traversable (Map k)`

`TraversableWithIndex k (Map k)`

### #checkValid Source

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

Check whether the underlying tree satisfies the height, size, and ordering invariants.

This function is provided for internal use.

### #insertWith Source

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

Inserts or updates a value with the given function.

The combining function is called with the existing value as the first argument and the new value as the second argument.

### #foldSubmap Source

`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"]
```

### #submap Source

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

### #fromFoldable Source

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

### #fromFoldableWith Source

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

### #fromFoldableWithIndex Source

`fromFoldableWithIndex :: forall f k v. Ord k => FoldableWithIndex k f => f v -> Map k v`

Convert any indexed foldable collection into a map.

### #toUnfoldable Source

`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 where the keys are in ascending order

### #toUnfoldableUnordered Source

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

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

While this traversal is up to 10% faster in benchmarks than `toUnfoldable`

,
it leaks the underlying map stucture, making it only suitable for applications
where order is irrelevant.

If you are unsure, use `toUnfoldable`

### #intersection Source

`intersection :: forall k a b. Ord k => Map k a -> Map k b -> Map k a`

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

### #intersectionWith Source

`intersectionWith :: forall k a b c. Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k c`

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

### #difference Source

`difference :: forall k v w. Ord k => Map k v -> Map k w -> Map k v`

Difference of two maps. Return elements of the first map where the keys do not exist in the second map.

### #filterWithKey Source

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

### #mapMaybeWithKey Source

`mapMaybeWithKey :: forall k a b. Ord k => (k -> a -> Maybe b) -> Map k a -> Map k b`

Applies a function to each key/value pair in a map, discarding entries
where the function returns `Nothing`

.

### #stepAsc Source

`stepAsc :: forall k v. MapStepper k v`

Steps a `MapIter`

in ascending order.

### #stepAscCps Source

`stepAscCps :: forall k v. MapStepperCps k v`

Steps a `MapIter`

in ascending order with a CPS encoding.

### #stepDesc Source

`stepDesc :: forall k v. MapStepper k v`

Steps a `MapIter`

in descending order.

### #stepDescCps Source

`stepDescCps :: forall k v. MapStepperCps k v`

Steps a `MapIter`

in descending order with a CPS encoding.

### #stepUnordered Source

`stepUnordered :: forall k v. MapStepper k v`

Steps a `MapIter`

in arbitrary order.

### #stepUnorderedCps Source

`stepUnorderedCps :: forall k v. MapStepperCps k v`

Steps a `MapIter`

in arbitrary order with a CPS encoding.

### #unsafeNode Source

`unsafeNode :: forall k v. Fn4 k v (Map k v) (Map k v) (Map k v)`

Low-level Node constructor which maintains the height and size invariants This is unsafe because it assumes the child Maps are ordered and balanced.

### #unsafeBalancedNode Source

`unsafeBalancedNode :: forall k v. Fn4 k v (Map k v) (Map k v) (Map k v)`

Low-level Node constructor which maintains the balance invariants. This is unsafe because it assumes the child Maps are ordered.

### #unsafeJoinNodes Source

`unsafeJoinNodes :: forall k v. Fn2 (Map k v) (Map k v) (Map k v)`

Low-level Node constructor from two Maps. This is unsafe because it assumes the child Maps are ordered.