ordered-containers-0.2.3: Set- and Map-like types that remember the order elements were inserted
Safe HaskellSafe-Inferred
LanguageHaskell98

Data.Set.Ordered

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

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

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

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

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

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

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.

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.

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 #

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 #

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 #

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

Set conversion

toSet :: OSet a -> Set a Source #

Convert an OSet to a Set.

O(n), where n is the size of the OSet.