Data.Map.Internal

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 :: forall k v. Show k => Show v => Map k v -> String

Render a Map as a String

empty :: forall k v. Map k v

An empty map

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

Test if a map is empty

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

Create a map with one key/value pair

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 :: forall k v. Ord k => k -> v -> Map k v -> Map k v

Insert or replace a key/value pair in a map

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.

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

Look up a value for the specified key

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 :: 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 :: 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 :: 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 :: forall k v. Map k v -> Maybe { key :: k, value :: v }

Returns the pair with the least key

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

Returns the pair with the greatest key

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 that have keys within a lower and upper bound (including keys equal to those bounds). Nothing is treated as unbounded.

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 :: forall k v. Ord k => Maybe k -> Maybe k -> Map k v -> Map k v

Returns a new map containing all entries with keys that fall within a specified lower and upper bound (including keys equal to those bounds). Nothing is treated as unbounded.

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,
  do
    let
      m' = submap mmin mmax m
      inBounds =
        maybe true (\min -> min <= key) mmin &&
          maybe true (\max -> max >= key) mmax
    if inBounds then
      lookup key m == lookup key m'
    else
      not (member key m')

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 :: 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 :: forall f k v. Ord k => FoldableWithIndex k f => f v -> Map k v

Convert any indexed foldable collection into a map.

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 :: 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 :: forall k v. Ord k => k -> Map k v -> Map k v

Delete a key and its corresponding value from a map.

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 :: forall k v. Ord k => k -> Map k v -> Boolean

Test if a key is a member of a map

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

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

Get a list of the keys contained in a map

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

Get a list of the values contained in a map

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 :: 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 :: forall k v f. Ord k => Foldable f => f (Map k v) -> Map k v

Compute the union of a collection of maps

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 :: 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 :: 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 :: 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 :: forall k v. Map k v -> Int

Calculate the number of key/value pairs in a map

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

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)

data MapIterStep k v

Constructors

• IterDone
• IterNext k v (MapIter k v)

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

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

stepAsc :: forall k v. MapStepper k v

Steps a MapIter in ascending order.

stepAscCps :: forall k v. MapStepperCps k v

Steps a MapIter in ascending order with a CPS encoding.

stepDesc :: forall k v. MapStepper k v

Steps a MapIter in descending order.

stepDescCps :: forall k v. MapStepperCps k v

Steps a MapIter in descending order with a CPS encoding.

stepUnordered :: forall k v. MapStepper k v

Steps a MapIter in arbitrary order.

stepUnorderedCps :: forall k v. MapStepperCps k v

Steps a MapIter in arbitrary order with a CPS encoding.

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 :: 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 and balanced. Their heights may differ arbitrarily: join along the taller tree's inner spine before restoring balance on the way back up.

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

data Split k v

Constructors

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