ordered-containers-0.2.1: Set- and Map-like types that remember the order elements were inserted

Safe HaskellSafe
LanguageHaskell98

Data.Set.Ordered

Contents

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

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

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

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

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

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