Data.Map.Ordered.Strict · ordered-containers-0.2.4

datadata OMap k v

#

Instances15Functor, Foldable, Traversable, IsList, Eq, Data, …

Functor (OMap k)Defined in ordered-containers-0.2.4 · Data.Map.Ordered.Internal
Foldable (OMap k)Defined in ordered-containers-0.2.4 · Data.Map.Ordered.Internal
Values are produced in insertion order, not key order.
Ord k => Traversable (OMap k)Defined in ordered-containers-0.2.4 · Data.Map.Ordered.Internal
Values are traversed in insertion order, not key order.
O(n*log(n)) where n is the size of the map.
Ord k => IsList (OMap k v)Defined in ordered-containers-0.2.4 · Data.Map.Ordered.Internal
fromList = fromList (the value-lazy variant) and toList = assocs.
(Eq k, Eq v) => Eq (OMap k v)Defined in ordered-containers-0.2.4 · Data.Map.Ordered.Internal
(Data k, Data a, Ord k) => Data (OMap k a)Defined in ordered-containers-0.2.4 · Data.Map.Ordered.Internal
(Ord k, Ord v) => Ord (OMap k v)Defined in ordered-containers-0.2.4 · Data.Map.Ordered.Internal
(Ord k, Read k, Read v) => Read (OMap k v)Defined in ordered-containers-0.2.4 · Data.Map.Ordered.Internal
Value-lazy
(Show k, Show v) => Show (OMap k v)Defined in ordered-containers-0.2.4 · Data.Map.Ordered.Internal
(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 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.
(Hashable k, Hashable v) => Hashable (OMap k v)Defined in ordered-containers-0.2.4 · Data.Map.Ordered.Internal
type Item (OMap k v) = (k, v)Defined in ordered-containers-0.2.4 · Data.Map.Ordered.Internal

Trivial maps

2 declarations

valueempty :: OMap k v

#

valuesingleton :: (k, v) -> OMap k v

#

Insertion

11 declarations

Conventions:

The open side of an angle bracket points to an OMap
The pipe appears on the side whose indices take precedence if both sides contain the same key
The left argument's indices are lower than the right argument's indices
If both sides contain the same key, the tuple's value wins

value(<|) :: Ord k => (k, v) -> OMap k v -> OMap k v

#

value(|<) :: Ord k => (k, v) -> OMap k v -> OMap k v

#

value(>|) :: Ord k => OMap k v -> (k, v) -> OMap k v

#

value(|>) :: Ord k => OMap k v -> (k, v) -> OMap k v

#

value(<>|) :: Ord k => OMap k v -> OMap k v -> OMap k v

#

When a key occurs in both maps, prefer the value from the second map.

See asymptotics of unionWithR.

value(|<>) :: Ord k => OMap k v -> OMap k v -> OMap k v

#

When a key occurs in both maps, prefer the value from the first map.

See asymptotics of unionWithL.

valueunionWithL

:: Ord k
=> k -> v -> v -> v
-> OMap k v
-> OMap k v
-> OMap k v

#

Take the union. The first OMap 's argument's indices are lower than the second. If a key appears in both maps, the first argument's index takes precedence, and the supplied function is used to combine the values.

O(r*log(r)) where r is the size of the result

valueunionWithR

:: Ord k
=> k -> v -> v -> v
-> OMap k v
-> OMap k v
-> OMap k v

#

Take the union. The first OMap 's argument's indices are lower than the second. If a key appears in both maps, the second argument's index takes precedence, and the supplied function is used to combine the values.

O(r*log(r)) where r is the size of the result

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

#

Deletion

6 declarations

valuedelete :: Ord k => k -> OMap k v -> OMap k v

#

valuefilter :: Ord k => (k -> v -> Bool) -> OMap k v -> OMap k v

#

filter f m contains exactly the key-value pairs of m that satisfy f, without changing the order they appear

value(\\) :: Ord k => OMap k v -> OMap k v' -> OMap k v

#

m \\ n deletes all the keys that exist in n from m

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

value(|/\) :: Ord k => OMap k v -> OMap k v' -> OMap k v

#

Intersection. (The /\ is intended to look a bit like the standard mathematical notation for set intersection.)

See asymptotics of intersectionWith.

value(/\|) :: Ord k => OMap k v -> OMap k v' -> OMap k v

#

Intersection. (The /\ is intended to look a bit like the standard mathematical notation for set intersection.)

See asymptotics of intersectionWith.

valueintersectionWith

:: Ord k
=> k -> v -> v' -> v''
-> OMap k v
-> OMap k v'
-> OMap k v''

#

Take the intersection. The first OMap 's argument's indices are used for the result.

O(m*log(n/(m+1)) + r*log(r)) where m is the size of the smaller map, n is the size of the larger map, and r is the size of the result.

Query

5 declarations

valuenull :: OMap k v -> Bool

#

valuesize :: OMap k v -> Int

#

valuemember :: Ord k => k -> OMap k v -> Bool

#

valuenotMember :: Ord k => k -> OMap k v -> Bool

#

valuelookup :: Ord k => k -> OMap k v -> Maybe v

#

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 k => k -> OMap k v -> Maybe Index

#

valueelemAt :: OMap k v -> Index -> Maybe (k, v)

#

List conversions

3 declarations

valuefromList :: Ord k => [(k, v)] -> OMap k v

#

If a key appears multiple times, the first occurrence is used for ordering and the last occurrence is used for its value. The library author welcomes comments on whether this default is sane.

valueassocs :: OMap k v -> [(k, v)]

#

Return key-value pairs in the order they were inserted.

valuetoAscList :: OMap k v -> [(k, v)]

#

Return key-value pairs in order of increasing key.

Map conversion

1 declaration

valuetoMap :: OMap k v -> Map k v

#

Convert an OMap to a Map.

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