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

License | MIT |

Maintainer | rcook@rcook.org |

Stability | stable |

Portability | portable |

Safe Haskell | None |

Language | Haskell2010 |

This module provides `OSet`

, an insertion-order-preserving set as well
as left- and right-biased wrappers `OSetL`

and `OSetR`

respectively.
`OSet`

has instances for `Foldable`

and `Data`

as well as a `map`

function and other features.
`Semigroup`

and `Monoid`

type class instances
are provided for `OSetL`

and `OSetR`

.

This is intended to be mostly API-compatible with OSet
in unordered-containers
but with a few extra type class instances provided via `newtype`

wrappers.

Here's the quick-start guide to using this package:

module Main (main) where import Data.Set.Ordered ((|>), (|<), (|<>), OSet) import qualified Data.Set.Ordered as OSet import Data.Sequence (Seq(..)) main :: IO () main = do -- Create from list let s0 :: OSet Int s0 = OSet.fromListL [1, 2, 3, 4, 4, 3, 2, 1, -1, -2, -3] print s0 -- outputs: "fromList [1,2,3,4,-1,-2,-3]" -- Append let s1 = s0 |> 4 print s1 -- outputs: "fromList [1,2,3,4,-1,-2,-3]" -- Prepend let s2 = 4 |< s0 print s2 -- outputs: "fromList [4,1,2,3,-1,-2,-3]" -- Append let s3 = s0 |<> OSet.fromListL [10, 10, 20, 20, 30, 30] print s3 -- outputs: "fromList [1,2,3,4,-1,-2,-3,10,20,30]" -- Map (but note that OSet is not a functor) let s4 = OSet.map (\x -> x * x) s3 print s4 -- outputs: "fromList [1,4,9,16,100,400,900]" -- Filter let s5 = OSet.filter (>= 100) s4 print s5 -- outputs: "fromList [100,400,900]" -- Pattern matching print $ foldWithPatternSynonyms (OSet.toSeq s5) foldWithPatternSynonyms :: Show a => Seq a -> String foldWithPatternSynonyms Empty = "" foldWithPatternSynonyms (x :<| xs) = show x ++ foldWithPatternSynonyms xs

There are cases where the developer's natural instinct would be to
convert the `OSet`

instance to a list using
`toList`

. While this is possible, it will often
be more efficient to use `toSeq`

and operate on the sequence that way.
You can even use view patterns to pattern-match on the resulting
sequence:

module Main (main) where import Data.Sequence (ViewL(..), viewl) import Data.Set.Ordered (OSet) import qualified Data.Set.Ordered as OSet showFromLeft :: Show a => OSet a -> String showFromLeft o = go (OSet.toSeq o) where go (viewl -> EmptyL) = "" go (viewl -> h :< t) = show h ++ go t go _ = error "Should not happen" -- suppress warning about non-exhaustive patterns main :: IO () main = do let a = OSet.fromListL [4 :: Int, 1, 3, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9] print $ showFromLeft a -- outputs: "4139025678"

## Synopsis

- data OSet a
- data OSetL a
- data OSetR a
- empty :: OrderedSet a c => c a
- singleton :: OrderedSet a c => a -> c a
- (<|) :: PreserveR a c => a -> c a -> c a
- (|<) :: PreserveL a c => a -> c a -> c a
- (>|) :: PreserveR a c => c a -> a -> c a
- (|>) :: PreserveL a c => c a -> a -> c a
- (<>|) :: PreserveR a c => c a -> c a -> c a
- (|<>) :: PreserveL a c => c a -> c a -> c a
- member :: (OrderedSet a c, Ord a) => a -> c a -> Bool
- notMember :: (OrderedSet a c, Ord a) => a -> c a -> Bool
- size :: OrderedSet a c => c a -> Int
- (\\) :: (OrderedSet a c, Ord a) => c a -> c a -> c a
- delete :: (OrderedSet a c, Ord a) => a -> c a -> c a
- filter :: OrderedSet a c => (a -> Bool) -> c a -> c a
- type Index = Int
- elemAt :: OrderedSet a c => c a -> Index -> Maybe a
- findIndex :: (OrderedSet a c, Eq a) => a -> c a -> Maybe Index
- fromListL :: (OrderedSet a c, Ord a) => [a] -> c a
- fromListR :: (OrderedSet a c, Ord a) => [a] -> c a
- toAscList :: OrderedSet a c => c a -> [a]
- toSeq :: OrderedSet a c => c a -> Seq a
- map :: (OrderedSet a c, Ord b) => (a -> b) -> c a -> c b

# Documentation

An `OSet`

behaves much like a `Set`

but remembers the order in
which the elements were originally inserted.

## Instances

Foldable OSet Source # | |

Defined in Data.Set.Ordered.OSet fold :: Monoid m => OSet m -> m # foldMap :: Monoid m => (a -> m) -> OSet a -> m # foldr :: (a -> b -> b) -> b -> OSet a -> b # foldr' :: (a -> b -> b) -> b -> OSet a -> b # foldl :: (b -> a -> b) -> b -> OSet a -> b # foldl' :: (b -> a -> b) -> b -> OSet a -> b # foldr1 :: (a -> a -> a) -> OSet a -> a # foldl1 :: (a -> a -> a) -> OSet a -> a # elem :: Eq a => a -> OSet a -> Bool # maximum :: Ord a => OSet a -> a # | |

Ord a => PreserveR a OSet Source # | |

Ord a => PreserveL a OSet Source # | |

OrderedSet a OSet Source # | |

Defined in Data.Set.Ordered.OSet singleton :: a -> OSet a Source # fromListL :: [a] -> OSet a Source # fromListR :: [a] -> OSet a Source # member :: a -> OSet a -> Bool Source # notMember :: a -> OSet a -> Bool Source # map :: Ord b => (a -> b) -> OSet a -> OSet b Source # filter :: (a -> Bool) -> OSet a -> OSet a Source # size :: OSet a -> Int Source # toSeq :: OSet a -> Seq a Source # toAscList :: OSet a -> [a] Source # findIndex :: a -> OSet a -> Maybe Index Source # elemAt :: OSet a -> Index -> Maybe a Source # | |

Eq a => Eq (OSet a) Source # | |

(Data a, Ord a) => Data (OSet a) Source # | |

Defined in Data.Set.Ordered.OSet gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> OSet a -> c (OSet a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (OSet a) # toConstr :: OSet a -> Constr # dataTypeOf :: OSet a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (OSet a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (OSet a)) # gmapT :: (forall b. Data b => b -> b) -> OSet a -> OSet a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> OSet a -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> OSet a -> r # gmapQ :: (forall d. Data d => d -> u) -> OSet a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> OSet a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> OSet a -> m (OSet a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> OSet a -> m (OSet a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> OSet a -> m (OSet a) # | |

Ord a => Ord (OSet a) Source # | |

Show a => Show (OSet a) Source # | |

A left-biased `OSet`

.

## Instances

Foldable OSetL Source # | |

Defined in Data.Set.Ordered.LR fold :: Monoid m => OSetL m -> m # foldMap :: Monoid m => (a -> m) -> OSetL a -> m # foldr :: (a -> b -> b) -> b -> OSetL a -> b # foldr' :: (a -> b -> b) -> b -> OSetL a -> b # foldl :: (b -> a -> b) -> b -> OSetL a -> b # foldl' :: (b -> a -> b) -> b -> OSetL a -> b # foldr1 :: (a -> a -> a) -> OSetL a -> a # foldl1 :: (a -> a -> a) -> OSetL a -> a # elem :: Eq a => a -> OSetL a -> Bool # maximum :: Ord a => OSetL a -> a # minimum :: Ord a => OSetL a -> a # | |

Ord a => PreserveL a OSetL Source # | |

OrderedSet a OSetL Source # | |

Defined in Data.Set.Ordered.LR singleton :: a -> OSetL a Source # fromListL :: [a] -> OSetL a Source # fromListR :: [a] -> OSetL a Source # member :: a -> OSetL a -> Bool Source # notMember :: a -> OSetL a -> Bool Source # map :: Ord b => (a -> b) -> OSetL a -> OSetL b Source # filter :: (a -> Bool) -> OSetL a -> OSetL a Source # size :: OSetL a -> Int Source # toSeq :: OSetL a -> Seq a Source # toAscList :: OSetL a -> [a] Source # findIndex :: a -> OSetL a -> Maybe Index Source # elemAt :: OSetL a -> Index -> Maybe a Source # | |

Eq a => Eq (OSetL a) Source # | |

(Data a, Ord a) => Data (OSetL a) Source # | |

Defined in Data.Set.Ordered.LR gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> OSetL a -> c (OSetL a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (OSetL a) # toConstr :: OSetL a -> Constr # dataTypeOf :: OSetL a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (OSetL a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (OSetL a)) # gmapT :: (forall b. Data b => b -> b) -> OSetL a -> OSetL a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> OSetL a -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> OSetL a -> r # gmapQ :: (forall d. Data d => d -> u) -> OSetL a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> OSetL a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> OSetL a -> m (OSetL a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> OSetL a -> m (OSetL a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> OSetL a -> m (OSetL a) # | |

Ord a => Ord (OSetL a) Source # | |

Show a => Show (OSetL a) Source # | |

Ord a => Semigroup (OSetL a) Source # | |

Ord a => Monoid (OSetL a) Source # | |

A right-biased `OSet`

.

## Instances

Foldable OSetR Source # | |

Defined in Data.Set.Ordered.LR fold :: Monoid m => OSetR m -> m # foldMap :: Monoid m => (a -> m) -> OSetR a -> m # foldr :: (a -> b -> b) -> b -> OSetR a -> b # foldr' :: (a -> b -> b) -> b -> OSetR a -> b # foldl :: (b -> a -> b) -> b -> OSetR a -> b # foldl' :: (b -> a -> b) -> b -> OSetR a -> b # foldr1 :: (a -> a -> a) -> OSetR a -> a # foldl1 :: (a -> a -> a) -> OSetR a -> a # elem :: Eq a => a -> OSetR a -> Bool # maximum :: Ord a => OSetR a -> a # minimum :: Ord a => OSetR a -> a # | |

Ord a => PreserveR a OSetR Source # | |

OrderedSet a OSetR Source # | |

Defined in Data.Set.Ordered.LR singleton :: a -> OSetR a Source # fromListL :: [a] -> OSetR a Source # fromListR :: [a] -> OSetR a Source # member :: a -> OSetR a -> Bool Source # notMember :: a -> OSetR a -> Bool Source # map :: Ord b => (a -> b) -> OSetR a -> OSetR b Source # filter :: (a -> Bool) -> OSetR a -> OSetR a Source # size :: OSetR a -> Int Source # toSeq :: OSetR a -> Seq a Source # toAscList :: OSetR a -> [a] Source # findIndex :: a -> OSetR a -> Maybe Index Source # elemAt :: OSetR a -> Index -> Maybe a Source # | |

Eq a => Eq (OSetR a) Source # | |

(Data a, Ord a) => Data (OSetR a) Source # | |

Defined in Data.Set.Ordered.LR gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> OSetR a -> c (OSetR a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (OSetR a) # toConstr :: OSetR a -> Constr # dataTypeOf :: OSetR a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (OSetR a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (OSetR a)) # gmapT :: (forall b. Data b => b -> b) -> OSetR a -> OSetR a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> OSetR a -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> OSetR a -> r # gmapQ :: (forall d. Data d => d -> u) -> OSetR a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> OSetR a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> OSetR a -> m (OSetR a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> OSetR a -> m (OSetR a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> OSetR a -> m (OSetR a) # | |

Ord a => Ord (OSetR a) Source # | |

Show a => Show (OSetR a) Source # | |

Ord a => Semigroup (OSetR a) Source # | |

Ord a => Monoid (OSetR a) Source # | |

# Trivial sets

empty :: OrderedSet a c => c a Source #

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

singleton :: OrderedSet a c => a -> c a Source #

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

# Insertion

(<|) :: PreserveR a c => 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.

(|<) :: PreserveL a c => 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.

(>|) :: PreserveR a c => 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.

(|>) :: PreserveL a c => 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.

(<>|) :: PreserveR a c => 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.

(|<>) :: PreserveL a c => 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.

# Query

size :: OrderedSet a c => c a -> Int Source #

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

# Deletion

(\\) :: (OrderedSet a c, 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.

delete :: (OrderedSet a c, Ord a) => a -> c a -> c a Source #

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

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

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

# Indexing

elemAt :: OrderedSet a c => 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`

.

findIndex :: (OrderedSet a c, 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.

# Conversion

fromListL :: (OrderedSet a c, 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 :: (OrderedSet a c, 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.

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

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

toSeq :: OrderedSet a c => 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.

# Miscellaneous

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