• 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
      • toList
      • keys
      • values
      • fromList
      • fromListGeneric
      • delete
      • alter
      • update
      • update
      • getIndex
      • difference
      • difference
      • union
      • union
      • union
      • intersection
      • intersection
      • intersection
      • Tree
        • Bin
        • Tip
      • empty
      • isEmpty
      • nonEmpty
      • singleton
      • size
      • put
      • putWithKey
      • get
      • getMin
      • getMax
      • forget
      • map
      • mapMaybe
      • filter
      • foreach
      • 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.
      • 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(???)
      • 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)
      • 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.
      • 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,
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]): String / {} 
        • Works only on the backends that support `genericShow` (JavaScript)!
      • prettyPairs [K, V] (list: List[Tuple2[K, V]]) { showLeft: (K) => String } { showRight: (V) => String }: String / {}