Safe Haskell	Safe
Language	Haskell98

Data.Set.Ordered

Contents

Trivial sets
Insertion
Query
Deletion
Indexing
List conversions

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]

Documentation

data OSet a Source #

Instances

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 # 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 #
Eq a => Eq (OSet a) Source #
Instance details Defined in Data.Set.Ordered Methods (==) :: OSet a -> OSet a -> Bool # (/=) :: OSet a -> OSet a -> Bool #
(Data a, Ord a) => Data (OSet a) Source #
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 :: (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 #
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 #
(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 #
Ord a => Semigroup (Bias R (OSet a)) Source #
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) #
Ord a => Semigroup (Bias L (OSet a)) Source #
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 => 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 (`<>\|`).
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 => 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 (`\|<>`).
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) #

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 hand 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.

Constructors

Bias
Fields unbiased :: a

Instances

(Ord k, Semigroup v) => Semigroup (Bias R (OMap k v)) Source #
Instance details Defined in Data.Map.Ordered 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 #
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) #
(Ord k, Semigroup v) => Semigroup (Bias L (OMap k v)) Source #
Instance details Defined in Data.Map.Ordered 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 #
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, 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`.
Instance details Defined in Data.Map.Ordered 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 (`<>\|`).
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, 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`.
Instance details Defined in Data.Map.Ordered 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 (`\|<>`).
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) #

type L = L Source #

type R = R Source #

Query

null :: OSet a -> Bool Source #

size :: OSet a -> Int Source #

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

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

Deletion

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

filter :: Ord a => (a -> Bool) -> OSet a -> OSet a Source #

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

Set difference: r \\ s deletes all the values in s from r. The order of r is unchanged.

O(m*log(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 Source #

Intersection. (/\ is meant to look a bit like the standard mathematical notation for intersection.)

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

(/\|) :: Ord a => OSet a -> OSet a -> OSet a Source #

flip (|/\)

See asymptotics of |/\.

Indexing

type Index = Int Source #

A 0-based index, much like the indices used by lists' !! operation. All indices are with respect to insertion order.

findIndex :: Ord a => a -> OSet a -> Maybe Index Source #

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

List conversions

fromList :: Ord a => [a] -> OSet a Source #

If a value occurs multiple times, only the first occurrence is used.

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

Returns values in ascending order. (Use toList to return them in insertion order.)