• Effekt Logo Effekt Library
    • map
      • Map
      • empty
      • emptyGeneric
      • isEmpty
      • nonEmpty
      • singleton
      • singletonGeneric
      • size
      • put
      • putWithKey
      • get
      • getOrElse
      • contains
      • getMin
      • getMax
      • map
      • map
      • mapMaybe
      • filter
      • filter
      • foreach
      • foreachReversed
      • toList
      • keys
      • values
      • fromList
      • fromListGeneric
      • delete
      • alter
      • update
      • update
      • getIndex
      • difference
      • difference
      • union
      • union
      • union
      • intersection
      • intersection
      • intersection
      • each
      • eachKey
      • eachValue
      • collect
      • returning
        • collect
      • internal
        • Tree
          • Bin
          • Tip
        • empty
        • isEmpty
        • nonEmpty
        • singleton
        • size
        • getWith
        • contains
        • getOrElse
        • put
        • putWithKey
        • get
        • getMin
        • getMax
        • forget
        • map
        • mapMaybe
        • filter
        • foreach
        • foreachReversed
        • Waiting
        • collect
        • fromList
        • delete
        • alter
        • update
        • getIndex
        • difference
        • union
        • intersection
        • ratio
        • delta
        • bin
        • balance
        • MaxView
        • MinView
        • maxViewSure
        • minViewSure
        • glue
        • splitLookup
        • link
        • link2
        • putMin
        • putMax
        • isBalanced
        • prettyTree
        • prettyPairs
    • map
      • Jump to source: libraries/common/map.effekt
      Example usage: examples/stdlib/map
      • Map [K, V] (tree: Tree[K, V], compare: (K, K) => Ordering at {})
        • Ordered finite immutable map, backed by balanced binary trees of logarithmic depth.
      • empty [K, V] (compare: (K, K) => Ordering at {}): Map[K, V] / {} 
        • Create a new empty map using a pure, first-class comparison function.

O(1)
      • emptyGeneric [K, V]: Map[K, V] / {} 
        • Create a new empty map using a generic comparison function.
Only available on JavaScript backends!

O(1)
      • isEmpty [K, V] (m: Map[K, V]): Bool / {} 
        • Check if map `m` is empty.

O(1)
      • nonEmpty [K, V] (m: Map[K, V]): Bool / {} 
        • Check if map `m` is nonempty.

O(1)
      • singleton [K, V] (k: K, v: V, compare: (K, K) => Ordering at {}): Map[K, V] / {} 
        • Create a new map containing the mapping from `k` to `v` and a pure, first-class comparison function.

O(1)
      • singletonGeneric [K, V] (k: K, v: V): Map[K, V] / {} 
        • Create a new map containing the mapping from `k` to `v` using a generic comparison function.
Only available on the JavaScript backends!

O(1)
      • size [K, V] (m: Map[K, V]): Int / {} 
        • Get the size of the map (the number of keys/values).

O(1)
      • put [K, V] (m: Map[K, V], k: K, v: V): Map[K, V] / {} 
        • Insert a new key `k` and value `v` into the map `m`.
If the key `k` is already present in `m`, its associated value is replaced with `v`.

O(log N)
      • putWithKey [K, V] (m: Map[K, V], k: K, v: V) { combine: (K, V, V) => V }: Map[K, V] / {} 
        • Insert a new key `k` and value `v` into the map `m`.
If the key `k` is already present in `m` with value `v2`, the function `combine` is called on `k`, `v`, `v2`.

O(log N)
      • get [K, V] (m: Map[K, V], k: K): Option[V] / {} 
        • Lookup the value at a key `k` in the map `m`.

O(log N)
      • getOrElse [K, V] (m: Map[K, V], k: K) { default: => V }: V / {} 
        • Lookup the value at a key `k` in the map `m`.
If there is no key, use the `default` block to retrieve a default value.

O(log N)
      • contains [K, V] (m: Map[K, V], k: K): Bool / {} 
        • Check if map `m` contains a key `k`.

O(log N)
      • getMin [K, V] (m: Map[K, V]): Option[Tuple2[K, V]] / {} 
        • Get minimum in the map `m`.

O(log N)
      • getMax [K, V] (m: Map[K, V]): Option[Tuple2[K, V]] / {} 
        • Get maximum in the map `m`.

O(log N)
      • map [K, V1, V2] (m: Map[K, V1]) { f: (K, V1) => V2 }: Map[K, V2] / {} 
        • Tree a function `f` over values in map `m`.

O(N)
      • map [K, V1, V2] (m: Map[K, V1]) { f: (V1) => V2 }: Map[K, V2] / {} 
        • Tree a function `f` over values in map `m`.

O(N)
      • mapMaybe [K, V1, V2] (m: Map[K, V1]) { f: (K, V1) => Option[V2] }: Map[K, V2] / {} 
        • Tree a function `f` over values in map `m`, keeping only the values where `f` returns `Some(...)`

O(N)
      • filter [K, V] (m: Map[K, V]) { shouldKeep: (K, V) => Bool }: Map[K, V] / {} 
        • Filters a map `m` with a `shouldKeep` function,
keeping only the elements where `shouldKeep` returns `true`.

Law: `m.filter { f } === m.mapMaybe { (k, v) => if (f(k, v)) Some(v) else None() }`

O(N)
      • filter [K, V] (m: Map[K, V]) { shouldKeep: (V) => Bool }: Map[K, V] / {} 
        • Filters a map `m` with a `shouldKeep` function,
keeping only the values where `shouldKeep` returns `true`.

O(N)
      • foreach [K, V] (m: Map[K, V]) { action: (K, V) => Unit }: Unit / {} 
        • Traverse all keys and their associated values in map `m` in order,
running the function `action` on a key and its associated value.

Law: `m.foreach { action } === m.toList.foreach { action }`

O(N)

TODO: Support {Control} for early exits.
      • foreachReversed [K, V] (m: Map[K, V]) { action: (K, V) => Unit }: Unit / {} 
        • Traverse all keys and their associated values in map `m` in *reverse*order,
running the function `action` on a key and its associated value.

Law: `m.foreachReversed { action } === m.toList.reverse.foreach { action }`

O(N)

TODO: Support {Control} for early exits.
      • toList [K, V] (m: Map[K, V]): List[Tuple2[K, V]] / {} 
        • Convert a map `m` into a list of (key, value) pairs.

O(N)
      • keys [K, V] (m: Map[K, V]): List[K] / {} 
        • Get a list of keys of the map `m`.

O(N)
      • values [K, V] (m: Map[K, V]): List[V] / {} 
        • Get a list of values of the map `m`.

O(N)
      • fromList [K, V] (pairs: List[Tuple2[K, V]], compare: (K, K) => Ordering at {}): Map[K, V] / {} 
        • Create a map from a list of (key, value) pairs and a pure, first-class comparison function.
If the list contains more than one value for the same key,
only the last value is used in the map.

O(N) if the list is sorted by key,
O(N log N) otherwise
      • fromListGeneric [K, V] (pairs: List[Tuple2[K, V]]): Map[K, V] / {} 
        • Create a map from a list of (key, value) pairs and a generic comparison function.
If the list contains more than one value for the same key,
only the last value is used in the map.
Works only on JavaScript backends!

O(N) if the list is sorted by key,
O(N log N) otherwise
      • delete [K, V] (m: Map[K, V], k: K): Map[K, V] / {} 
        • Remove a key `k` from a map `m`.
If `k` is not in `m`, `m` is returned.

O(log N)
      • alter [K, V] (m: Map[K, V], k: K) { f: (Option[V]) => Option[V] }: Map[K, V] / {} 
        • Can be used to insert, delete, or update a value.
Law: `get(m.alter(k){f}, k) === f(get(m, k))`

O(log N)
      • update [K, V] (m: Map[K, V], k: K) { f: (K, V) => Option[V] }: Map[K, V] / {} 
        • Update or delete a value associated with key `k` in map `m`.

O(log N)
      • update [K, V] (m: Map[K, V], k: K) { f: (V) => Option[V] }: Map[K, V] / {} 
        • Update or delete a value associated with key `k` in map `m`.

O(log N)
      • getIndex [K, V] (m: Map[K, V], n: Int): Option[Tuple2[K, V]] / {} 
        • Get `n`-th (key, value) pair in the map `m`.

O(log N)
      • difference [K, V] (m1: Map[K, V], m2: Map[K, V], compare: (K, K) => Ordering at {})
        • Construct a new map which contains all elements of `m1`
except those where the key is found in `m2`.
Uses an explicit pure, first-class comparison function.

O(???)
      • difference [K, V] (m1: Map[K, V], m2: Map[K, V])
        • Construct a new map which contains all elements of `m1`
except those where the key is found in `m2`.
Uses the comparison function from `m1`.

O(???)
      • union [K, V] (m1: Map[K, V], m2: Map[K, V], compare: (K, K) => Ordering at {}) { combine: (K, V, V) => V }: Map[K, V] / {} 
        • Construct a new map which contains the elements of both `m1` and `m2`.
When a key is associated with a value in both `m1` and `m2`, the new value is determined using the `combine` function.
Uses an explicit pure, first-class comparison function.

O(???)
      • union [K, V] (m1: Map[K, V], m2: Map[K, V], compare: (K, K) => Ordering at {}) { combine: (V, V) => V }: Map[K, V] / {} 
        • Construct a new map which contains the elements of both `m1` and `m2`.
When a key is associated with a value in both `m1` and `m2`, the new value is determined using the `combine` function.
Uses an explicit pure, first-class comparison function.

O(???)
      • union [K, V] (m1: Map[K, V], m2: Map[K, V]): Map[K, V] / {} 
        • Construct a new map which contains the elements of both `m1` and `m2`.
Left-biased: Uses values from `m1` if there are duplicate keys and
uses the comparison function from `m1`.

O(???)
      • intersection [K, A, B, C] (m1: Map[K, A], m2: Map[K, B], compare: (K, K) => Ordering at {}) { combine: (K, A, B) => C }: Map[K, C] / {} 
        • Construct a new map which combines all elements that are in both `m1` and `m2` using the `combine` function.

O(???)
      • intersection [K, A, B, C] (m1: Map[K, A], m2: Map[K, B], compare: (K, K) => Ordering at {}) { combine: (A, B) => C }: Map[K, C] / {} 
        • Construct a new map which combines all elements that are in both `m1` and `m2` using the `combine` function.

O(???)
      • intersection [K, A, B] (m1: Map[K, A], m2: Map[K, B]): Map[K, A] / {} 
        • Construct a new map which combines all elements that are in both `m1` and `m2`.
Left-biased: Always uses values from `m1` and the comparison function from `m1`.

O(???)
      • each [K, V] (map: Map[K, V]): Unit / {emit[Tuple2[K, V]]} 
        • Turns a `map` into a producer of a push stream
of `(key, value)` pairs by emitting each contained *in order*.
      • eachKey [K, V] (map: Map[K, V]): Unit / {emit[K]} 
        • Turns a `map` into a producer of a push stream
of its keys by emitting each contained *in order*.
      • eachValue [K, V] (map: Map[K, V]): Unit / {emit[V]} 
        • Turns a `map` into a producer of a push stream
of its values by emitting each contained.
      • collect [K, V] (compare: (K, K) => Ordering at {}) { stream: => Unit / {emit[Tuple2[K, V]]} }: Map[K, V] / {} 
        • Collects `(key, value)` pairs from a push stream producer `stream` into a new `map`
using the provided `compare` function, discarding the result of the producer.
      • returning
        • collect [K, V, R] (compare: (K, K) => Ordering at {}) { stream: => R / {emit[Tuple2[K, V]]} }: Tuple2[R, Map[K, V]] / {} 
          • Collects `(key, value)` pairs from a push stream producer `stream` into a new `map`,
using the provided `compare` function, returning the result of the producer as well as the collected map.
      • internal 
        • Please don't directly use:
- the `Tree` type
- its internal constructors `Bin` & `Tip`,
- and these functions.
As they might change down the line and are not considered stable / public.
        • Tree [K, V]
          • Balanced binary trees of logarithmic depth.
          • Bin (size: Int, k: K, v: V, left: Tree[K, V], right: Tree[K, V])
          • Tip
        • empty [K, V]: Tree[K, V] / {} 
          • Create a new empty tree.

O(1)
        • isEmpty [K, V] (m: Tree[K, V]): Bool / {} 
          • Check if tree `m` is empty.

O(1)
        • nonEmpty [K, V] (m: Tree[K, V]): Bool / {} 
          • Check if tree `m` is nonempty.

O(1)
        • singleton [K, V] (k: K, v: V): Tree[K, V] / {} 
          • Create a new tree containing only the mapping from `k` to `v`.

O(1)
        • size [K, V] (m: Tree[K, V]): Int / {} 
          • Get the size of the tree (the number of keys/values).

O(1)
        • getWith [K, V, R] (m: Tree[K, V], compare: (K, K) => Ordering at {}, k: K) { found: (V) => R } { missing: => R }: R / {} 
          • Look up `k` in the tree `m`, handing the value it is bound to to `found`,
or running `missing` if there is none.

O(log N)
        • contains [K, V] (m: Tree[K, V], compare: (K, K) => Ordering at {}, k: K): Bool / {} 
          • Whether the tree `m` binds the key `k`.

O(log N)
        • getOrElse [K, V] (m: Tree[K, V], compare: (K, K) => Ordering at {}, k: K) { default: => V }: V / {} 
          • The value bound to `k` in the tree `m`, or `default` if there is none.

O(log N)
        • put [K, V] (m: Tree[K, V], compare: (K, K) => Ordering at {}, k: K, v: V): Tree[K, V] / {} 
          • Insert a new key `k` and value `v` into the tree `m`.
If the key `k` is already present in `m`, its associated value is replaced with `v`.

O(log N)
        • putWithKey [K, V] (m: Tree[K, V], compare: (K, K) => Ordering at {}, k: K, v: V) { combine: (K, V, V) => V }: Tree[K, V] / {} 
          • Insert a new key `k` and value `v` into the tree `m`.
If the key `k` is already present in `m` with value `v2`, the function `combine` is called on `k`, `v`, `v2`.

O(log N)
        • get [K, V] (m: Tree[K, V], compare: (K, K) => Ordering at {}, k: K): Option[V] / {} 
          • Lookup the value at a key `k` in the tree `m`.

O(log N)
        • getMin [K, V] (m: Tree[K, V]): Option[Tuple2[K, V]] / {} 
          • Get minimum in the tree `m`.

O(log N)
        • getMax [K, V] (m: Tree[K, V]): Option[Tuple2[K, V]] / {} 
          • Get maximum in the tree `m`.

O(log N)
        • forget [K, V] (m: Tree[K, V]): Tree[K, Unit] / {} 
          • Forgets the values of a tree, setting them all to `(): Unit`.
Used by `set`s internally.

Law: `m.forget === m.map { (_k, _v) => () }`

O(N)
        • map [K, V1, V2] (m: Tree[K, V1]) { f: (K, V1) => V2 }: Tree[K, V2] / {} 
          • Tree a function `f` over values in tree `m`.

O(N)
        • mapMaybe [K, V1, V2] (m: Tree[K, V1]) { f: (K, V1) => Option[V2] }: Tree[K, V2] / {} 
          • Tree a function `f` over values in tree `m`, keeping only the values where `f` returns `Some(...)`

O(N)
        • filter [K, V] (m: Tree[K, V]) { shouldKeep: (K, V) => Bool }: Tree[K, V] / {} 
          • Filters a tree `m` with a `shouldKeep` function,
keeping only the elements where `shouldKeep` returns `true`.

Law: `m.filter { f } === m.mapMaybe { (k, v) => if (f(k, v)) Some(v) else None() }`

O(N)
        • foreach [K, V] (m: Tree[K, V]) { action: (K, V) => Unit }: Unit / {} 
          • Traverse all keys and their associated values in tree `m` in order,
running the function `action` on a key and its associated value.

Law: `m.foreach { action } === m.toList.foreach { action }`

O(N)

TODO: Support {Control} for early exits.
        • foreachReversed [K, V] (m: Tree[K, V]) { action: (K, V) => Unit }: Unit / {} 
          • Traverse all keys and their associated values in tree `m` in *reverse* order,
running the function `action` on a key and its associated value.

Law: `m.foreachReversed { action } === m.toList.reverse.foreach { action }`

O(N)

TODO: Support {Control} for early exits.
        • Waiting [K, V] (size: Int, key: K, value: V, tree: Tree[K, V])
          • A balanced subtree waiting to be joined, and the key separating it from the pairs collected after it.

A list of these is the *right* spine of the tree being built.
Their sizes strictly increase towards the back, so the list is the digits of a binary counter.
        • collect [K, V, R] (compare: (K, K) => Ordering at {}) { stream: => R / {emit[Tuple2[K, V]]} }: Tuple2[R, Tree[K, V]] / {} 
          • Collect `(key, value)` pairs from a push stream producer `stream` into a tree,
returning the result of the producer as well.
Consider using `map::fromList` if you know the full list.

O(N) if the stream is sorted by key (in _either_ direction),
O(N log N) otherwise
        • fromList [K, V] (pairs: List[Tuple2[K, V]], compare: (K, K) => Ordering at {}): Tree[K, V] / {} 
          • Create a tree from a list of (key, value) pairs.
If the list contains more than one value for the same key,
only the last value is used in the tree.

O(N) if the list is sorted by key (in _either_ direction),
O(N log N) otherwise
        • delete [K, V] (m: Tree[K, V], compare: (K, K) => Ordering at {}, k: K): Tree[K, V] / {} 
          • Remove a key `k` from a tree `m`.
If `k` is not in `m`, `m` is returned.

O(log N)
        • alter [K, V] (m: Tree[K, V], compare: (K, K) => Ordering at {}, k: K) { f: (Option[V]) => Option[V] }: Tree[K, V] / {} 
          • Can be used to insert, delete, or update a value.
Law: `get(m.alter(k){f}, k) === f(get(m, k))`

O(log N)
        • update [K, V] (m: Tree[K, V], compare: (K, K) => Ordering at {}, k: K) { f: (K, V) => Option[V] }: Tree[K, V] / {} 
          • Update or delete a value associated with key `k` in tree `m`.

O(log N)
        • getIndex [K, V] (m: Tree[K, V], n: Int): Option[Tuple2[K, V]] / {} 
          • Get `n`-th (key, value) pair in the tree `m`.

O(log N)
        • difference [K, V] (m1: Tree[K, V], m2: Tree[K, V], compare: (K, K) => Ordering at {}): Tree[K, V] / {} 
          • Construct a new tree which contains all elements of `m1`
except those where the key is found in `m2`.

O(???)
        • union [K, V] (m1: Tree[K, V], m2: Tree[K, V], compare: (K, K) => Ordering at {}) { combine: (K, V, V) => V }: Tree[K, V] / {} 
          • Construct a new tree which contains the elements of both `m1` and `m2`.
When a key is associated with a value in both `m1` and `m2`, the new value is determined using the `combine` function.

O(???)
        • intersection [K, A, B, C] (m1: Tree[K, A], m2: Tree[K, B], compare: (K, K) => Ordering at {}) { combine: (K, A, B) => C }: Tree[K, C] / {} 
          • Construct a new tree which combines all elements that are in both `m1` and `m2` using the `combine` function.

O(???)
        • ratio
        • delta
        • bin [K, V] (k: K, v: V, l: Tree[K, V], r: Tree[K, V]): Tree[K, V] / {}
        • balance [K, V] (k: K, v: V, l: Tree[K, V], r: Tree[K, V]): Tree[K, V] / {}
        • MaxView [K, V] (k: K, v: V, m: Tree[K, V])
        • MinView [K, V] (k: K, v: V, m: Tree[K, V])
        • maxViewSure [K, V] (k: K, v: V, l: Tree[K, V], r: Tree[K, V]): MaxView[K, V] / {}
        • minViewSure [K, V] (k: K, v: V, l: Tree[K, V], r: Tree[K, V]): MinView[K, V] / {}
        • glue [K, V] (l: Tree[K, V], r: Tree[K, V]): Tree[K, V] / {} 
          • Internal: Glues two balanced trees (with respect to each other) together.
        • splitLookup [K, V] (m: Tree[K, V], compare: (K, K) => Ordering at {}, k: K): Tuple3[Tree[K, V], Option[V], Tree[K, V]] / {}
        • link [K, V] (k: K, v: V, l: Tree[K, V], r: Tree[K, V]): Tree[K, V] / {}
        • link2 [K, V] (l: Tree[K, V], r: Tree[K, V]): Tree[K, V] / {} 
          • Internal: merge two trees
        • putMin [K, V] (m: Tree[K, V], k: K, v: V): Tree[K, V] / {}
        • putMax [K, V] (m: Tree[K, V], k: K, v: V): Tree[K, V] / {}
        • isBalanced [K, V] (m: Tree[K, V]): Bool / {} 
          • Check if a tree `m` is balanced.
        • prettyTree [K, V] (m: Tree[K, V]) { show: (K) => String } { show: (V) => String }: String / {} 
          • Works only on the backends that support `genericShow` (JavaScript)!
        • prettyPairs [K, V] (list: List[Tuple2[K, V]]) { show: (K) => String } { show: (V) => String }: String / {}