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

Safe Haskell | None
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 Source #

foldMap :: Monoid m => (a -> m) -> OSet a -> m Source #

foldMap' :: Monoid m => (a -> m) -> OSet a -> m Source #

foldr :: (a -> b -> b) -> b -> OSet a -> b Source #

foldr' :: (a -> b -> b) -> b -> OSet a -> b Source #

foldl :: (b -> a -> b) -> b -> OSet a -> b Source #

foldl' :: (b -> a -> b) -> b -> OSet a -> b Source #

foldr1 :: (a -> a -> a) -> OSet a -> a Source #

foldl1 :: (a -> a -> a) -> OSet a -> a Source #

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

null :: OSet a -> Bool Source #

length :: OSet a -> Int Source #

elem :: Eq a => a -> OSet a -> Bool Source #

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

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

sum :: Num a => OSet a -> a Source #

product :: Num a => OSet a -> a Source #

(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) Source #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (OSet a) Source #

toConstr :: OSet a -> Constr Source #

dataTypeOf :: OSet a -> DataType Source #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (OSet a)) Source #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (OSet a)) Source #

gmapT :: (forall b. Data b => b -> b) -> OSet a -> OSet a Source #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> OSet a -> r Source #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> OSet a -> r Source #

gmapQ :: (forall d. Data d => d -> u) -> OSet a -> [u] Source #

gmapQi :: Int -> (forall d. Data d => d -> u) -> OSet a -> u Source #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> OSet a -> m (OSet a) Source #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> OSet a -> m (OSet a) Source #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> OSet a -> m (OSet a) Source #

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) |
Instance details Defined in Data.Set.Ordered type Item (OSet a) = a

Methods

fromList :: [Item (OSet a)] -> OSet a Source #

fromListN :: Int -> [Item (OSet a)] -> OSet a Source #

toList :: OSet a -> [Item (OSet a)] Source #

(Ord a, Read a) => Read (OSet a) Source # |
Instance details Defined in Data.Set.Ordered Methods readsPrec :: Int -> ReadS (OSet a) Source # readList :: ReadS [OSet a] Source # readPrec :: ReadPrec (OSet a) Source # readListPrec :: ReadPrec [OSet a] Source #
Show a => Show (OSet a) Source # |
Instance details Defined in Data.Set.Ordered Methods showsPrec :: Int -> OSet a -> ShowS Source # show :: OSet a -> String Source # showList :: [OSet a] -> ShowS Source #
Eq a => Eq (OSet a) Source # |
Instance details Defined in Data.Set.Ordered Methods (==) :: OSet a -> OSet a -> Bool Source # (/=) :: OSet a -> OSet a -> Bool Source #
Ord a => Ord (OSet a) Source # |
Instance details Defined in Data.Set.Ordered Methods compare :: OSet a -> OSet a -> Ordering Source # (<) :: OSet a -> OSet a -> Bool Source # (<=) :: OSet a -> OSet a -> Bool Source # (>) :: OSet a -> OSet a -> Bool Source # (>=) :: OSet a -> OSet a -> Bool Source # max :: OSet a -> OSet a -> OSet a Source # min :: OSet a -> OSet a -> OSet a Source #
Hashable a => Hashable (OSet a) Source # | Since: 0.2.4
Instance details Defined in Data.Set.Ordered Methods hashWithSalt :: Int -> OSet a -> Int Source # hash :: OSet a -> Int Source #
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) Source # mappend :: Bias L (OSet a) -> Bias L (OSet a) -> Bias L (OSet a) Source # mconcat :: [Bias L (OSet a)] -> Bias L (OSet a) Source #
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) Source # mappend :: Bias R (OSet a) -> Bias R (OSet a) -> Bias R (OSet a) Source # mconcat :: [Bias R (OSet a)] -> Bias R (OSet a) Source #
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) Source # sconcat :: NonEmpty (Bias L (OSet a)) -> Bias L (OSet a) Source # stimes :: Integral b => b -> Bias L (OSet a) -> Bias L (OSet a) Source #
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) Source # sconcat :: NonEmpty (Bias R (OSet a)) -> Bias R (OSet a) Source # stimes :: Integral b => b -> Bias R (OSet a) -> Bias R (OSet a) Source #
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

Functor (Bias dir) Source # |
Instance details Defined in Data.Map.Util Methods fmap :: (a -> b) -> Bias dir a -> Bias dir b Source # (<$) :: a -> Bias dir b -> Bias dir a Source #
Foldable (Bias dir) Source # |

Instance details

Defined in Data.Map.Util

Methods

fold :: Monoid m => Bias dir m -> m Source #

foldMap :: Monoid m => (a -> m) -> Bias dir a -> m Source #

foldMap' :: Monoid m => (a -> m) -> Bias dir a -> m Source #

foldr :: (a -> b -> b) -> b -> Bias dir a -> b Source #

foldr' :: (a -> b -> b) -> b -> Bias dir a -> b Source #

foldl :: (b -> a -> b) -> b -> Bias dir a -> b Source #

foldl' :: (b -> a -> b) -> b -> Bias dir a -> b Source #

foldr1 :: (a -> a -> a) -> Bias dir a -> a Source #

foldl1 :: (a -> a -> a) -> Bias dir a -> a Source #

toList :: Bias dir a -> [a] Source #

null :: Bias dir a -> Bool Source #

length :: Bias dir a -> Int Source #

elem :: Eq a => a -> Bias dir a -> Bool Source #

maximum :: Ord a => Bias dir a -> a Source #

minimum :: Ord a => Bias dir a -> a Source #

sum :: Num a => Bias dir a -> a Source #

product :: Num a => Bias dir a -> a Source #

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) Source # sequenceA :: Applicative f => Bias dir (f a) -> f (Bias dir a) Source # mapM :: Monad m => (a -> m b) -> Bias dir a -> m (Bias dir b) Source # sequence :: Monad m => Bias dir (m a) -> m (Bias dir a) Source #
(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) Source # mappend :: Bias L (OMap k v) -> Bias L (OMap k v) -> Bias L (OMap k v) Source # mconcat :: [Bias L (OMap k v)] -> Bias L (OMap k v) Source #
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) Source # mappend :: Bias L (OSet a) -> Bias L (OSet a) -> Bias L (OSet a) Source # mconcat :: [Bias L (OSet a)] -> Bias L (OSet a) Source #
(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) Source # mappend :: Bias R (OMap k v) -> Bias R (OMap k v) -> Bias R (OMap k v) Source # mconcat :: [Bias R (OMap k v)] -> Bias R (OMap k v) Source #
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) Source # mappend :: Bias R (OSet a) -> Bias R (OSet a) -> Bias R (OSet a) Source # mconcat :: [Bias R (OSet a)] -> Bias R (OSet a) Source #
(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) Source # sconcat :: NonEmpty (Bias L (OMap k v)) -> Bias L (OMap k v) Source # stimes :: Integral b => b -> Bias L (OMap k v) -> Bias L (OMap k v) Source #
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) Source # sconcat :: NonEmpty (Bias L (OSet a)) -> Bias L (OSet a) Source # stimes :: Integral b => b -> Bias L (OSet a) -> Bias L (OSet a) Source #
(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) Source # sconcat :: NonEmpty (Bias R (OMap k v)) -> Bias R (OMap k v) Source # stimes :: Integral b => b -> Bias R (OMap k v) -> Bias R (OMap k v) Source #
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) Source # sconcat :: NonEmpty (Bias R (OSet a)) -> Bias R (OSet a) Source # stimes :: Integral b => b -> Bias R (OSet a) -> Bias R (OSet a) Source #
(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) Source #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Bias dir a) Source #

toConstr :: Bias dir a -> Constr Source #

dataTypeOf :: Bias dir a -> DataType Source #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Bias dir a)) Source #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Bias dir a)) Source #

gmapT :: (forall b. Data b => b -> b) -> Bias dir a -> Bias dir a Source #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Bias dir a -> r Source #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Bias dir a -> r Source #

gmapQ :: (forall d. Data d => d -> u) -> Bias dir a -> [u] Source #

gmapQi :: Int -> (forall d. Data d => d -> u) -> Bias dir a -> u Source #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Bias dir a -> m (Bias dir a) Source #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Bias dir a -> m (Bias dir a) Source #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Bias dir a -> m (Bias dir a) Source #

Read a => Read (Bias dir a) Source # |
Instance details Defined in Data.Map.Util Methods readsPrec :: Int -> ReadS (Bias dir a) Source # readList :: ReadS [Bias dir a] Source # readPrec :: ReadPrec (Bias dir a) Source # readListPrec :: ReadPrec [Bias dir a] Source #
Show a => Show (Bias dir a) Source # |
Instance details Defined in Data.Map.Util Methods showsPrec :: Int -> Bias dir a -> ShowS Source # show :: Bias dir a -> String Source # showList :: [Bias dir a] -> ShowS Source #
Eq a => Eq (Bias dir a) Source # |
Instance details Defined in Data.Map.Util Methods (==) :: Bias dir a -> Bias dir a -> Bool Source # (/=) :: Bias dir a -> Bias dir a -> Bool Source #
Ord a => Ord (Bias dir a) Source # |

Instance details

Defined in Data.Map.Util

Methods

compare :: Bias dir a -> Bias dir a -> Ordering Source #

(<) :: Bias dir a -> Bias dir a -> Bool Source #

(<=) :: Bias dir a -> Bias dir a -> Bool Source #

(>) :: Bias dir a -> Bias dir a -> Bool Source #

(>=) :: Bias dir a -> Bias dir a -> Bool Source #

max :: Bias dir a -> Bias dir a -> Bias dir a Source #

min :: Bias dir a -> Bias dir a -> Bias dir a Source #

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.

Since: 0.2

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

    flip (|/\)

See asymptotics of `|/\`.

Since: 0.2

# 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`.

Since: 0.2.2