Copyright | (C) Richard Cook 2019 |
---|---|

License | MIT |

Maintainer | rcook@rcook.org |

Stability | stable |

Portability | portable |

Safe Haskell | Safe |

Language | Haskell2010 |

## Synopsis

- type Index = Int
- class OrderedSet a c where
- empty :: c a
- singleton :: a -> c a
- fromListL :: Ord a => [a] -> c a
- fromListR :: Ord a => [a] -> c a
- member :: Ord a => a -> c a -> Bool
- notMember :: Ord a => a -> c a -> Bool
- map :: Ord b => (a -> b) -> c a -> c b
- filter :: (a -> Bool) -> c a -> c a
- size :: c a -> Int
- toSeq :: c a -> Seq a
- toAscList :: c a -> [a]
- findIndex :: Eq a => a -> c a -> Maybe Index
- elemAt :: c a -> Index -> Maybe a
- delete :: Ord a => a -> c a -> c a
- (\\) :: Ord a => c a -> c a -> c a

- class PreserveL a c where
- class PreserveR a c where

# Common operations on ordered sets

class OrderedSet a c where Source #

Common operations on ordered sets. Set type is `c`

, element
type is `a`

.

\(O(1)\). The empty set.

singleton :: a -> c a Source #

\(O(1)\). A singleton set containing the given element.

fromListL :: Ord a => [a] -> c a Source #

\(O(N log(N))\). Create a set from a finite list of elements.
If an element occurs multiple times in the original list, only
the first occurrence is retained in the resulting set. The
function `toList`

, \(O(N)\), can be used
to return a list of the elements in the original insert order
with duplicates removed.

fromListR :: Ord a => [a] -> c a Source #

\(O(N log(N))\). Create a set from a finite list of elements.
If an element occurs multiple times in the original list, only
the last occurrence is retained in the resulting set. The
function `toList`

, \(O(N)\), can be used
to return a list of the elements in the original insert order
with duplicates removed.

member :: Ord a => a -> c a -> Bool Source #

\(O(log(N))\). Determine if the element is in the set.
Evaluate to `True`

if element is in set,
`False`

otherwise.

notMember :: Ord a => a -> c a -> Bool Source #

\(O(log(N))\). Determine if the element is not in the set.
Evaluate to `True`

if element is not in set,
`False`

otherwise.

map :: Ord b => (a -> b) -> c a -> c b Source #

\(O(N log(N))\). Return the set obtained by applying a function
to each element of this set. Note that the resulting set may be
smaller than the original. Along with the `Ord`

constraint, this
means that `OSet`

cannot provide a lawful
`Functor`

instance.

filter :: (a -> Bool) -> c a -> c a Source #

\(O(N)\). Filter a set by returning a set whose elements satisfy the predicate.

\(O(1)\). The number of elements in the set.

toSeq :: c a -> Seq a Source #

\(O(1)\). Return ordered sequence of elements in set. For
obtaining a useful `Functor`

instance this is
recommended over `toList`

due to its
\(O(1)\) performance. Similarly, if you want to pattern-match on
the `OSet`

, obtain the sequence and use
view patterns or pattern synonyms instead of converting to a
list.

toAscList :: c a -> [a] Source #

\(O(N)\). Convert the set to an ascending list of elements.

findIndex :: Eq a => a -> c a -> Maybe Index Source #

\(O(N)\). Finds the index of the leftmost element that matches
the specified element or returns `Nothing`

if no
matching element can be found.

elemAt :: c a -> Index -> Maybe a Source #

\(O(log(min(i, N - i)))\). Return the element at the specified
position, \(i\), counting from 0. If the specified position is
out of range, this function returns `Nothing`

.

delete :: Ord a => a -> c a -> c a Source #

\(O(log N)\). Delete an element from the set.

(\\) :: Ord a => c a -> c a -> c a Source #

\(O(N M)\). Find the set difference: `r \\ s`

removes all `M`

values in `s`

from `r`

with `N`

values.

## Instances

# Insertion

class PreserveL a c where Source #

`OSet`

and `OSetL`

operations that preserve elements from the left-hand operand in the
case of duplicate elements. Set type is `c`

, element type is `a`

.

(|<) :: a -> c a -> c a infixr 5 Source #

\(O(log(N))\) if the element is not in the set, \(O(N)\) if the element is already in the set. Add an element to the left end of the sequence if the set does not already contain the element. Move the element to the left end of the sequence if the element is already present in the set.

(|>) :: c a -> a -> c a infixl 5 Source #

\(O(log(N))\). Add an element to the right end of the sequence if the set does not already contain the element. Otherwise ignore the element.

(|<>) :: c a -> c a -> c a infixr 6 Source #

\(O(Nlog(N))\) worst case. Add elements from the right-hand set to the left-hand set. If elements occur in both sets, then this operation discards elements from the right-hand set and preserves those from the left.

class PreserveR a c where Source #

`OSet`

and `OSetR`

operations that preserve elements from the right-hand operand in the
case of duplicate elements. Set type is `c`

, element type is `a`

.

(<|) :: a -> c a -> c a infixr 5 Source #

\(O(log(N))\). Add an element to the left end of the sequence if the set does not already contain the element. Otherwise ignore the element.

(>|) :: c a -> a -> c a infixl 5 Source #

\(O(log(N))\) if the element is not in the set, \(O(N)\) if the element is already in the set. Add an element to the right end of the sequence if the set does not already contain the element. Move the element to the right end of the sequence if the element is already present in the set.

(<>|) :: c a -> c a -> c a infixr 6 Source #

\(O(N^2)\) worst case. Add elements from the right-hand set to the left-hand set. If elements occur in both sets, then this operation discards elements from the left-hand set and preserves those from the right.