Moduleordered-containers-0.2.4Haskell98

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.

5 types
22 values

Packageordered-containers-0.2.4
Exports27
LanguageHaskell98
LicenceBSD-3-Clause
SourceOrdered.hs

datadata OSet a

Instances13Foldable, IsList, Eq, Data, Ord, Read, …

Foldable OSetDefined in ordered-containers-0.2.4 · Data.Set.Ordered
Values appear in insertion order, not ascending order.
Ord a => IsList (OSet a)Defined in ordered-containers-0.2.4 · Data.Set.Ordered
fromList = fromList and toList = toList.
Eq a => Eq (OSet a)Defined in ordered-containers-0.2.4 · Data.Set.Ordered
(Data a, Ord a) => Data (OSet a)Defined in ordered-containers-0.2.4 · Data.Set.Ordered
Ord a => Ord (OSet a)Defined in ordered-containers-0.2.4 · Data.Set.Ordered
(Ord a, Read a) => Read (OSet a)Defined in ordered-containers-0.2.4 · Data.Set.Ordered
Show a => Show (OSet a)Defined in ordered-containers-0.2.4 · Data.Set.Ordered
Hashable a => Hashable (OSet a)Defined in ordered-containers-0.2.4 · Data.Set.Ordered
Ord a => Semigroup (Bias L (OSet a))Defined in ordered-containers-0.2.4 · Data.Set.Ordered
Ord a => Semigroup (Bias R (OSet a))Defined in ordered-containers-0.2.4 · Data.Set.Ordered
Ord a => Monoid (Bias L (OSet a))Defined in ordered-containers-0.2.4 · Data.Set.Ordered
Empty sets and set union. When combining two sets that share elements, the indices of the left argument are preferred.
See the asymptotics of (|<>).
Ord a => Monoid (Bias R (OSet a))Defined in ordered-containers-0.2.4 · Data.Set.Ordered
Empty sets and set union. When combining two sets that share elements, the indices of the right argument are preferred.
See the asymptotics of (<>|).
type Item (OSet a) = aDefined in ordered-containers-0.2.4 · Data.Set.Ordered

Trivial sets

2 declarations

valueempty :: OSet a

valuesingleton :: a -> OSet a

Insertion

9 declarations

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

value(<|) :: Ord a => a -> OSet a -> OSet a

value(|<) :: Ord a => a -> OSet a -> OSet a

value(>|) :: Ord a => OSet a -> a -> OSet a

value(|>) :: Ord a => OSet a -> a -> OSet a

value(<>|) :: Ord a => OSet a -> OSet a -> OSet a

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

value(|<>) :: Ord a => OSet a -> OSet a -> OSet a

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

newtypenewtype Bias (dir :: IndexPreference) a

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.

Constructors

Bias
- unbiased :: a

Instances16Functor, Foldable, Traversable, Eq, Data, Ord, …

Functor (Bias dir)Defined in ordered-containers-0.2.4 · Data.Map.Util
Foldable (Bias dir)Defined in ordered-containers-0.2.4 · Data.Map.Util
Traversable (Bias dir)Defined in ordered-containers-0.2.4 · Data.Map.Util
Eq a => Eq (Bias dir a)Defined in ordered-containers-0.2.4 · Data.Map.Util
(Typeable dir, Data a) => Data (Bias dir a)Defined in ordered-containers-0.2.4 · Data.Map.Util
Ord a => Ord (Bias dir a)Defined in ordered-containers-0.2.4 · Data.Map.Util
Read a => Read (Bias dir a)Defined in ordered-containers-0.2.4 · Data.Map.Util
Show a => Show (Bias dir a)Defined in ordered-containers-0.2.4 · Data.Map.Util
Ord a => Semigroup (Bias L (OSet a))Defined in ordered-containers-0.2.4 · Data.Set.Ordered
Ord a => Semigroup (Bias R (OSet a))Defined in ordered-containers-0.2.4 · Data.Set.Ordered
(Ord k, Semigroup v) => Semigroup (Bias L (OMap k v))Defined in ordered-containers-0.2.4 · Data.Map.Ordered.Internal
Uses the value-lazy variant of unionWithL.
(Ord k, Semigroup v) => Semigroup (Bias R (OMap k v))Defined in ordered-containers-0.2.4 · Data.Map.Ordered.Internal
Uses the value-lazy variant of unionWithR.
Ord a => Monoid (Bias L (OSet a))Defined in ordered-containers-0.2.4 · Data.Set.Ordered
Empty sets and set union. When combining two sets that share elements, the indices of the left argument are preferred.
See the asymptotics of (|<>).
Ord a => Monoid (Bias R (OSet a))Defined in ordered-containers-0.2.4 · Data.Set.Ordered
Empty sets and set union. When combining two sets that share elements, the indices of the right argument are preferred.
See the asymptotics of (<>|).
(Ord k, Monoid v) => Monoid (Bias L (OMap k v))Defined in ordered-containers-0.2.4 · Data.Map.Ordered.Internal
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.
(Ord k, Monoid v) => Monoid (Bias R (OMap k v))Defined in ordered-containers-0.2.4 · Data.Map.Ordered.Internal
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.

typetype L = 'L

typetype R = 'R

Query

4 declarations

valuenull :: OSet a -> Bool

valuesize :: OSet a -> Int

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

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

Deletion

5 declarations

valuedelete :: Ord a => a -> OSet a -> OSet a

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

value(\\) :: 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.

value(|/\) :: 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.

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

flip (|/\)

See asymptotics of |/\.

Indexing

3 declarations

typetype Index = Int

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

valuefindIndex :: Ord a => a -> OSet a -> Maybe Index

valueelemAt :: OSet a -> Index -> Maybe a

List conversions

2 declarations

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

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

valuetoAscList :: OSet a -> [a]

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

Set conversion

1 declaration

valuetoSet :: OSet a -> Set a

Convert an OSet to a Set.

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