Data.Set.Ordered

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.

Documentation

data OSet a

Instances

Foldable OSet

Values appear in insertion order, not ascending order.

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)

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, Read a) => Read (OSet a)

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)

Defined in Data.Set.Ordered

Methods

showsPrec :: Int -> OSet a -> ShowS

show :: OSet a -> String

showList :: [OSet a] -> ShowS

Eq a => Eq (OSet a)

Defined in Data.Set.Ordered

Methods

(==) :: OSet a -> OSet a -> Bool

(/=) :: OSet a -> OSet a -> Bool

Ord a => Ord (OSet a)

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 => Monoid (Bias L (OSet a))

Empty sets and set union. When combining two sets that share elements, the indices of the left argument are preferred.

See the asymptotics of (|<>).

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

Empty sets and set union. When combining two sets that share elements, the indices of the right argument are preferred.

See the asymptotics of (<>|).

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

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

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)

Trivial sets

empty :: OSet a

singleton :: a -> OSet a

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

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

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

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

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

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

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

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

Foldable (Bias dir)

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)

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)

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)

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

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.

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

Empty sets and set union. When combining two sets that share elements, the indices of the left argument are preferred.

See the asymptotics of (|<>).

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

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.

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

Empty sets and set union. When combining two sets that share elements, the indices of the right argument are preferred.

See the asymptotics of (<>|).

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

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

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

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

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)

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)

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)

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)

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

type R = 'R

Query

null :: OSet a -> Bool

size :: OSet a -> Int

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

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

Deletion

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

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

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

flip (|/\)

See asymptotics of |/\.

Indexing

type Index = Int

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

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

List conversions

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

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

toAscList :: OSet a -> [a]

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

Set conversion

toSet :: OSet a -> Set a

Convert an OSet to a Set.

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