| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.OSet.Strict
Synopsis
- data OSet a where
- null ∷ OSet a → Bool
- size ∷ OSet a → Int
- empty ∷ OSet a
- singleton ∷ a → OSet a
- lookup ∷ Int → OSet a → Maybe a
- member ∷ Ord a ⇒ a → OSet a → Bool
- (!?) ∷ OSet a → Int → Maybe a
- fromList ∷ Ord a ⇒ [a] → OSet a
- fromStrictSeq ∷ Ord a ⇒ StrictSeq a → OSet a
- fromStrictSeqDuplicates ∷ Ord a ⇒ StrictSeq a → (Set a, OSet a)
- toStrictSeq ∷ OSet a → StrictSeq a
- toSet ∷ OSet a → Set a
- fromSet ∷ Set a → OSet a
- fromFoldable ∷ (Foldable f, Ord a) ⇒ f a → OSet a
- fromFoldableDuplicates ∷ (Foldable f, Ord a) ⇒ f a → (Set a, OSet a)
- invariantHolds ∷ OSet a → Bool
- invariantHolds' ∷ Ord a ⇒ OSet a → Bool
- (|>) ∷ Ord a ⇒ OSet a → a → OSet a
- (<|) ∷ Ord a ⇒ a → OSet a → OSet a
- (|><) ∷ Ord a ⇒ OSet a → OSet a → OSet a
- (><|) ∷ Ord a ⇒ OSet a → OSet a → OSet a
- filter ∷ Ord a ⇒ (a → Bool) → OSet a → OSet a
Documentation
A general-purpose finite, ordered, set that is strict in its values.
The strictness is enforced by the underlying StrictSeq from base,
and the uniqueness of the values is enforced in this module, by the
constructing functions by leveraging an accompanying Set.
TODO: @aniketd Implement DecShareCBOR
Bundled Patterns
| pattern Empty ∷ OSet a | |
| pattern (:<|:) ∷ Ord a ⇒ a → OSet a → OSet a infixr 5 | \(O(\log n)\). |
| pattern (:|>:) ∷ Ord a ⇒ OSet a → a → OSet a infixl 5 | \(O(\log n)\). |
Instances
fromStrictSeq ∷ Ord a ⇒ StrictSeq a → OSet a Source #
\(O(n \log n)\). Checks membership before snoc-ing. De-duplicates the StrictSeq without overwriting.
toStrictSeq ∷ OSet a → StrictSeq a Source #
\( O(1) \) - Extract underlying strict sequence
invariantHolds' ∷ Ord a ⇒ OSet a → Bool Source #
\( O(n \log n) \). Deep invariant using set membership check for each value. By the pigeon-hole principle, this check is exhaustive.
(|><) ∷ Ord a ⇒ OSet a → OSet a → OSet a infixl 5 Source #
\( O(n\log(m*n)) \). For every uncons-ed element from the sequence on the right, checks its membership in the sequence on the left, before snoc'ing it. Preserves order. Remove duplicates from sequence on the right.