Module

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

Leaf
Node Int Int k v (Map k v) (Map k 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)
(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)

#showTree Source

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

Render a Map as a String

#isEmpty Source

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

Test if a map is empty

#singleton Source

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

Create a map with one key/value pair

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

#insert Source

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

Insert or replace a key/value pair in a map

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

#lookupLE Source

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

#lookupLT Source

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

#lookupGE Source

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

#lookupGT Source

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

#findMin Source

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

Returns the pair with the least key

#findMax Source

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

Returns the pair with the greatest key

#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

#delete Source

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

Delete a key and its corresponding value from a map.

#pop Source

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.

#member Source

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

Test if a key is a member of a map

#alter Source

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 Source

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

#keys Source

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

Get a list of the keys contained in a map

#values Source

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

Get a list of the values contained in a map

#union Source

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

#unionWith Source

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.

#unions Source

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

Compute the union of a collection of maps

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

#isSubmap Source

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

#size Source

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

Calculate the number of key/value pairs in a 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.

#filterKeys Source

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.

#filter Source

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.

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

#mapMaybe Source

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

Applies a function to each value in a map, discarding entries where the function returns Nothing.

#catMaybes Source

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

Filter a map of optional values, keeping only the key/value pairs which contain a value, creating a new map.

#any Source

any :: forall k v. (v -> Boolean) -> Map k v -> Boolean

Returns true if at least one map element satisfies the given predicateon the value, iterating the map only as necessary and stopping as soon as the predicate yields true.

#anyWithKey Source

anyWithKey :: forall k v. (k -> v -> Boolean) -> Map k v -> Boolean

Returns true if at least one map element satisfies the given predicate, iterating the map only as necessary and stopping as soon as the predicate yields true.

#MapIter Source

data MapIter k v

Low-level iteration state for a Map. Must be consumed using an appropriate stepper.

Instances

(Eq k, Eq v) => Eq (MapIter k v)
(Ord k, Ord v) => Ord (MapIter k v)

#MapIterStep Source

data MapIterStep k v

Constructors

IterDone
IterNext k v (MapIter k v)

#toMapIter Source

toMapIter :: forall k v. Map k v -> MapIter k v

Converts a Map to a MapIter for iteration using a MapStepper.

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

#unsafeSplit Source

unsafeSplit :: forall k v. Fn3 (k -> k -> Ordering) k (Map k v) (Split k v)

Reassocates a Map so the given key is at the top. This is unsafe because it assumes the ordering function is appropriate.

#Split Source

data Split k v

Constructors

Split (Maybe v) (Map k v) (Map k v)

Modules: Data.Map; Data.Map.Gen; Data.Map.Internal; Data.Set; Data.Set.NonEmpty

Data.Map.Internal

#Map Source

Constructors

Instances

#showTree Source

#empty Source

#isEmpty Source

#singleton Source

#checkValid Source

#insert Source

#insertWith Source

#lookup Source

#lookupLE Source

#lookupLT Source

#lookupGE Source

#lookupGT Source

#findMin Source

#findMax Source

#foldSubmap Source

#submap Source

#fromFoldable Source

#fromFoldableWith Source

#fromFoldableWithIndex Source

#toUnfoldable Source

#toUnfoldableUnordered Source

#delete Source

#pop Source

#member Source

#alter Source

#update Source

#keys Source

#values Source

#union Source

#unionWith Source

#unions Source

#intersection Source

#intersectionWith Source

#difference Source

#isSubmap Source

#size Source

#filterWithKey Source

#filterKeys Source

#filter Source

#mapMaybeWithKey Source

#mapMaybe Source

#catMaybes Source

#any Source

#anyWithKey Source

#MapIter Source

Instances

#MapIterStep Source

Constructors

#toMapIter Source

#stepAsc Source

#stepAscCps Source

#stepDesc Source

#stepDescCps Source

#stepUnordered Source

#stepUnorderedCps Source

#unsafeNode Source

#unsafeBalancedNode Source

#unsafeJoinNodes Source

#unsafeSplit Source

#Split Source

Constructors