Documentation

A general-purpose finite, insert-ordered, map that is strict in its keys and values.

The strictness is enforced by the underlying strict Map, and the ordering is maintained by the constructing functions, leveraging StrictSeq to hold the insert-order of the keys.

TODO: DecShareCBOR instance

\(O(1)\).

\(O(1)\).

\(O(1)\).

\(O(1)\). Strict in its arguments.

\(O(\log n)\). If the key is not present lookup returns Nothing.

\(O(\log n)\). Key membership check.

fliped version of lookup

\(O(n \log n)\).

\(O(n \log n)\). Checks membership before snoc'ing. De-duplicates the StrictSeq without overwriting. Starts from the left or head, using foldl'

\(O(n \log n)\). Checks membership before snoc'ing. De-duplicates the StrictSeq and collects and returns the duplicates found. Starts from the left or head, using foldl'

\(O(1)\).

\(O(n \log n)\).

\(O(1)\).

\(O(n \log n)\).

\(O(1)\). Shallow invariant using just length and size.

\(O(n \log n)\). Deep, costly invariant using membership check for each value. By the pigeon-hole principle, this check is exhaustive.

\(O(\log n)\). Checks membership before snoc'ing.

\(O(\log n)\). Checks membership before cons'ing.

\(O(\log n)\). Checks membership before cons'ing. Overwrites a duplicate.

\(O(\log n)\). Checks membership before snoc'ing. Overwrites a duplicate.

\( O(n \log m) \). For every uncons-ed element from the sequence on the right, check its membership in the sequence on the left, before snoc'ing it. Preserve order. Remove duplicates from sequence on the right.

\( O(m \log n) \). For every unsnoc-ed element from the sequence on the left, check its membership in the sequence on the right, before cons'ing it. Preserve order. Remove duplicates from sequence on the left.

\(O(\log n)\). Key-value pair membership check.

\(O(n)\). Given a Set of ks, and an OMap k v return a pair of Map and OMap where the ks in the Set have been removed from the OMap and presented as a separate Map.

\(O(\log n)\). Like adjust.

Update a value at a specific key with the result of the provided function. Returns the original OMap unaltered when the key does not exist.

Examples:

>>> import Data.SimpleOMap.Strict
>>> let m = fromFoldable $ zip [1,2] ['a','b'] :: OMap Int Char
>>> m
StrictSeq {fromStrict = fromList [(1,'a'),(2,'b')]}
>>> adjust succ 1 m
StrictSeq {fromStrict = fromList [(1,'b'),(2,'b')]}
>>> adjust succ 3 m
StrictSeq {fromStrict = fromList [(1,'a'),(2,'b')]}

\( O(n \log n) \)