Safe Haskell	Safe-Inferred
Language	Haskell98

Data.Set.Ordered

Contents

Trivial sets
Insertion
Query
Deletion
Indexing
List conversions
Set conversion

Description

An OSet behaves much like a Set, with mostly the same asymptotics, but also remembers the order that values were inserted. All operations whose asymptotics are worse than Set have documentation saying so.

Synopsis

data OSet a
empty :: OSet a
singleton :: a -> OSet a
(<|) :: Ord a => a -> OSet a -> OSet a
(|<) :: Ord a => a -> OSet a -> OSet a
(>|) :: Ord a => OSet a -> a -> OSet a
(|>) :: Ord a => OSet a -> a -> OSet a
(<>|) :: Ord a => OSet a -> OSet a -> OSet a
(|<>) :: Ord a => OSet a -> OSet a -> OSet a
newtype Bias (dir :: IndexPreference) a = Bias {
- unbiased :: a
}
type L = 'L
type R = 'R
null :: OSet a -> Bool
size :: OSet a -> Int
member :: Ord a => a -> OSet a -> Bool
notMember :: Ord a => a -> OSet a -> Bool
delete :: Ord a => a -> OSet a -> OSet a
filter :: Ord a => (a -> Bool) -> OSet a -> OSet a
(\\) :: Ord a => OSet a -> OSet a -> OSet a
(|/\) :: Ord a => OSet a -> OSet a -> OSet a
(/\|) :: Ord a => OSet a -> OSet a -> OSet a
type Index = Int
findIndex :: Ord a => a -> OSet a -> Maybe Index
elemAt :: OSet a -> Index -> Maybe a
fromList :: Ord a => [a] -> OSet a
toAscList :: OSet a -> [a]
toSet :: OSet a -> Set a

Documentation

data OSet a Source #

Instances

Instances details

Foldable OSet Source #	Values appear in insertion order, not ascending order.
Instance details Defined in Data.Set.Ordered Methods fold :: Monoid m => OSet m -> m # foldMap :: Monoid m => (a -> m) -> OSet a -> 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 # toList :: OSet a -> [a] # null :: OSet a -> Bool # length :: OSet a -> Int # elem :: Eq a => a -> OSet a -> Bool # maximum :: Ord a => OSet a -> a # minimum :: Ord a => OSet a -> a # sum :: Num a => OSet a -> a # product :: Num a => OSet a -> a #
(Data a, Ord a) => Data (OSet a) Source #	Since: 0.2
Instance details Defined in Data.Set.Ordered Methods 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 :: forall r r'. (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 => IsList (OSet a) Source #	`fromList = fromList` and `toList = toList`. Since: 0.2.4
Instance details Defined in Data.Set.Ordered Associated Types type Item (OSet a) # Methods fromList :: [Item (OSet a)] -> OSet a # fromListN :: Int -> [Item (OSet a)] -> OSet a # toList :: OSet a -> [Item (OSet a)] #
(Ord a, Read a) => Read (OSet a) Source #
Instance details Defined in Data.Set.Ordered Methods readsPrec :: Int -> ReadS (OSet a) # readList :: ReadS [OSet a] # readPrec :: ReadPrec (OSet a) # readListPrec :: ReadPrec [OSet a] #
Show a => Show (OSet a) Source #
Instance details Defined in Data.Set.Ordered Methods showsPrec :: Int -> OSet a -> ShowS # show :: OSet a -> String # showList :: [OSet a] -> ShowS #
Eq a => Eq (OSet a) Source #
Instance details Defined in Data.Set.Ordered Methods (==) :: OSet a -> OSet a -> Bool # (/=) :: OSet a -> OSet a -> Bool #
Ord a => Ord (OSet a) Source #
Instance details Defined in Data.Set.Ordered Methods compare :: OSet a -> OSet a -> Ordering # (<) :: OSet a -> OSet a -> Bool # (<=) :: OSet a -> OSet a -> Bool # (>) :: OSet a -> OSet a -> Bool # (>=) :: OSet a -> OSet a -> Bool # max :: OSet a -> OSet a -> OSet a # min :: OSet a -> OSet a -> OSet a #
Hashable a => Hashable (OSet a) Source #	Since: 0.2.4
Instance details Defined in Data.Set.Ordered Methods hashWithSalt :: Int -> OSet a -> Int # hash :: OSet a -> Int #
Ord a => Monoid (Bias L (OSet a)) Source #	Empty sets and set union. When combining two sets that share elements, the indices of the left argument are preferred. See the asymptotics of (`\|<>`). Since: 0.2
Instance details Defined in Data.Set.Ordered Methods mempty :: Bias L (OSet a) # mappend :: Bias L (OSet a) -> Bias L (OSet a) -> Bias L (OSet a) # mconcat :: [Bias L (OSet a)] -> Bias L (OSet a) #
Ord a => Monoid (Bias R (OSet a)) Source #	Empty sets and set union. When combining two sets that share elements, the indices of the right argument are preferred. See the asymptotics of (`<>\|`). Since: 0.2
Instance details Defined in Data.Set.Ordered Methods mempty :: Bias R (OSet a) # mappend :: Bias R (OSet a) -> Bias R (OSet a) -> Bias R (OSet a) # mconcat :: [Bias R (OSet a)] -> Bias R (OSet a) #
Ord a => Semigroup (Bias L (OSet a)) Source #	Since: 0.2
Instance details Defined in Data.Set.Ordered Methods (<>) :: Bias L (OSet a) -> Bias L (OSet a) -> Bias L (OSet a) # sconcat :: NonEmpty (Bias L (OSet a)) -> Bias L (OSet a) # stimes :: Integral b => b -> Bias L (OSet a) -> Bias L (OSet a) #
Ord a => Semigroup (Bias R (OSet a)) Source #	Since: 0.2
Instance details Defined in Data.Set.Ordered Methods (<>) :: Bias R (OSet a) -> Bias R (OSet a) -> Bias R (OSet a) # sconcat :: NonEmpty (Bias R (OSet a)) -> Bias R (OSet a) # stimes :: Integral b => b -> Bias R (OSet a) -> Bias R (OSet a) #
type Item (OSet a) Source #
Instance details Defined in Data.Set.Ordered type Item (OSet a) = a

Trivial sets

empty :: OSet a Source #

singleton :: a -> OSet a Source #

Insertion

Conventions:

The open side of an angle bracket points to an OSet
The pipe appears on the side whose indices take precedence for keys that appear on both sides
The left argument's indices are lower than the right argument's indices

(<|) :: Ord a => a -> OSet a -> OSet a infixr 5 Source #

(|<) :: Ord a => a -> OSet a -> OSet a infixr 5 Source #

(>|) :: Ord a => OSet a -> a -> OSet a infixl 5 Source #

(|>) :: Ord a => OSet a -> a -> OSet a infixl 5 Source #

(<>|) :: Ord a => OSet a -> OSet a -> OSet a infixr 6 Source #

O(m*log(n)+n), where m is the size of the smaller set and n is the size of the larger set.

(|<>) :: Ord a => OSet a -> OSet a -> OSet a infixr 6 Source #

O(m*log(n)+n), where m is the size of the smaller set and n is the size of the larger set.

newtype Bias (dir :: IndexPreference) a Source #

A newtype to hang a Monoid instance on. The phantom first parameter tells whether mappend will prefer the indices of its first or second argument if there are shared elements in both.

Since: 0.2

Constructors

Bias
Fields unbiased :: a

Instances

Instances details

Foldable (Bias dir) Source #
Instance details Defined in Data.Map.Util Methods fold :: Monoid m => Bias dir m -> m # foldMap :: Monoid m => (a -> m) -> Bias dir a -> m # foldMap' :: Monoid m => (a -> m) -> Bias dir a -> m # foldr :: (a -> b -> b) -> b -> Bias dir a -> b # foldr' :: (a -> b -> b) -> b -> Bias dir a -> b # foldl :: (b -> a -> b) -> b -> Bias dir a -> b # foldl' :: (b -> a -> b) -> b -> Bias dir a -> b # foldr1 :: (a -> a -> a) -> Bias dir a -> a # foldl1 :: (a -> a -> a) -> Bias dir a -> a # toList :: Bias dir a -> [a] # null :: Bias dir a -> Bool # length :: Bias dir a -> Int # elem :: Eq a => a -> Bias dir a -> Bool # maximum :: Ord a => Bias dir a -> a # minimum :: Ord a => Bias dir a -> a # sum :: Num a => Bias dir a -> a # product :: Num a => Bias dir a -> a #
Traversable (Bias dir) Source #
Instance details Defined in Data.Map.Util Methods traverse :: Applicative f => (a -> f b) -> Bias dir a -> f (Bias dir b) # sequenceA :: Applicative f => Bias dir (f a) -> f (Bias dir a) # mapM :: Monad m => (a -> m b) -> Bias dir a -> m (Bias dir b) # sequence :: Monad m => Bias dir (m a) -> m (Bias dir a) #
Functor (Bias dir) Source #
Instance details Defined in Data.Map.Util Methods fmap :: (a -> b) -> Bias dir a -> Bias dir b # (<$) :: a -> Bias dir b -> Bias dir a #
(Typeable dir, Data a) => Data (Bias dir a) Source #
Instance details Defined in Data.Map.Util Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Bias dir a -> c (Bias dir a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Bias dir a) # toConstr :: Bias dir a -> Constr # dataTypeOf :: Bias dir a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Bias dir a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Bias dir a)) # gmapT :: (forall b. Data b => b -> b) -> Bias dir a -> Bias dir a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Bias dir a -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Bias dir a -> r # gmapQ :: (forall d. Data d => d -> u) -> Bias dir a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Bias dir a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Bias dir a -> m (Bias dir a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Bias dir a -> m (Bias dir a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Bias dir a -> m (Bias dir a) #
(Ord k, Monoid v) => Monoid (Bias L (OMap k v)) Source #	Empty maps and map union. When combining two sets that share elements, the indices of the left argument are preferred, and the values are combined with `mappend`. See the asymptotics of `unionWithL`. Uses the value-lazy variant. Since: 0.2
Instance details Defined in Data.Map.Ordered.Internal Methods mempty :: Bias L (OMap k v) # mappend :: Bias L (OMap k v) -> Bias L (OMap k v) -> Bias L (OMap k v) # mconcat :: [Bias L (OMap k v)] -> Bias L (OMap k v) #
Ord a => Monoid (Bias L (OSet a)) Source #	Empty sets and set union. When combining two sets that share elements, the indices of the left argument are preferred. See the asymptotics of (`\|<>`). Since: 0.2
Instance details Defined in Data.Set.Ordered Methods mempty :: Bias L (OSet a) # mappend :: Bias L (OSet a) -> Bias L (OSet a) -> Bias L (OSet a) # mconcat :: [Bias L (OSet a)] -> Bias L (OSet a) #
(Ord k, Monoid v) => Monoid (Bias R (OMap k v)) Source #	Empty maps and map union. When combining two sets that share elements, the indices of the right argument are preferred, and the values are combined with `mappend`. See the asymptotics of `unionWithR`. Uses the value-lazy variant. Since: 0.2
Instance details Defined in Data.Map.Ordered.Internal Methods mempty :: Bias R (OMap k v) # mappend :: Bias R (OMap k v) -> Bias R (OMap k v) -> Bias R (OMap k v) # mconcat :: [Bias R (OMap k v)] -> Bias R (OMap k v) #
Ord a => Monoid (Bias R (OSet a)) Source #	Empty sets and set union. When combining two sets that share elements, the indices of the right argument are preferred. See the asymptotics of (`<>\|`). Since: 0.2
Instance details Defined in Data.Set.Ordered Methods mempty :: Bias R (OSet a) # mappend :: Bias R (OSet a) -> Bias R (OSet a) -> Bias R (OSet a) # mconcat :: [Bias R (OSet a)] -> Bias R (OSet a) #
(Ord k, Semigroup v) => Semigroup (Bias L (OMap k v)) Source #	Uses the value-lazy variant of `unionWithL`. Since: 0.2
Instance details Defined in Data.Map.Ordered.Internal Methods (<>) :: Bias L (OMap k v) -> Bias L (OMap k v) -> Bias L (OMap k v) # sconcat :: NonEmpty (Bias L (OMap k v)) -> Bias L (OMap k v) # stimes :: Integral b => b -> Bias L (OMap k v) -> Bias L (OMap k v) #
Ord a => Semigroup (Bias L (OSet a)) Source #	Since: 0.2
Instance details Defined in Data.Set.Ordered Methods (<>) :: Bias L (OSet a) -> Bias L (OSet a) -> Bias L (OSet a) # sconcat :: NonEmpty (Bias L (OSet a)) -> Bias L (OSet a) # stimes :: Integral b => b -> Bias L (OSet a) -> Bias L (OSet a) #
(Ord k, Semigroup v) => Semigroup (Bias R (OMap k v)) Source #	Uses the value-lazy variant of `unionWithR`. Since: 0.2
Instance details Defined in Data.Map.Ordered.Internal Methods (<>) :: Bias R (OMap k v) -> Bias R (OMap k v) -> Bias R (OMap k v) # sconcat :: NonEmpty (Bias R (OMap k v)) -> Bias R (OMap k v) # stimes :: Integral b => b -> Bias R (OMap k v) -> Bias R (OMap k v) #
Ord a => Semigroup (Bias R (OSet a)) Source #	Since: 0.2
Instance details Defined in Data.Set.Ordered Methods (<>) :: Bias R (OSet a) -> Bias R (OSet a) -> Bias R (OSet a) # sconcat :: NonEmpty (Bias R (OSet a)) -> Bias R (OSet a) # stimes :: Integral b => b -> Bias R (OSet a) -> Bias R (OSet a) #
Read a => Read (Bias dir a) Source #
Instance details Defined in Data.Map.Util Methods readsPrec :: Int -> ReadS (Bias dir a) # readList :: ReadS [Bias dir a] # readPrec :: ReadPrec (Bias dir a) # readListPrec :: ReadPrec [Bias dir a] #
Show a => Show (Bias dir a) Source #
Instance details Defined in Data.Map.Util Methods showsPrec :: Int -> Bias dir a -> ShowS # show :: Bias dir a -> String # showList :: [Bias dir a] -> ShowS #
Eq a => Eq (Bias dir a) Source #
Instance details Defined in Data.Map.Util Methods (==) :: Bias dir a -> Bias dir a -> Bool # (/=) :: Bias dir a -> Bias dir a -> Bool #
Ord a => Ord (Bias dir a) Source #
Instance details Defined in Data.Map.Util Methods compare :: Bias dir a -> Bias dir a -> Ordering # (<) :: Bias dir a -> Bias dir a -> Bool # (<=) :: Bias dir a -> Bias dir a -> Bool # (>) :: Bias dir a -> Bias dir a -> Bool # (>=) :: Bias dir a -> Bias dir a -> Bool # max :: Bias dir a -> Bias dir a -> Bias dir a # min :: Bias dir a -> Bias dir a -> Bias dir a #