Data.Map.Ordered

An OMap behaves much like a Map, with mostly the same asymptotics, but also remembers the order that keys were inserted. All operations whose asymptotics are worse than Map have documentation saying so.

Documentation

data OMap k v

Instances

Foldable (OMap k)

Values are produced in insertion order, not key order.

Defined in Data.Map.Ordered.Internal

Methods

fold :: Monoid m => OMap k m -> m

foldMap :: Monoid m => (a -> m) -> OMap k a -> m

foldMap' :: Monoid m => (a -> m) -> OMap k a -> m

foldr :: (a -> b -> b) -> b -> OMap k a -> b

foldr' :: (a -> b -> b) -> b -> OMap k a -> b

foldl :: (b -> a -> b) -> b -> OMap k a -> b

foldl' :: (b -> a -> b) -> b -> OMap k a -> b

foldr1 :: (a -> a -> a) -> OMap k a -> a

foldl1 :: (a -> a -> a) -> OMap k a -> a

toList :: OMap k a -> [a]

null :: OMap k a -> Bool

length :: OMap k a -> Int

elem :: Eq a => a -> OMap k a -> Bool

maximum :: Ord a => OMap k a -> a

minimum :: Ord a => OMap k a -> a

sum :: Num a => OMap k a -> a

product :: Num a => OMap k a -> a

Ord k => Traversable (OMap k)

Values are traversed in insertion order, not key order.

O(n*log(n)) where n is the size of the map.

Defined in Data.Map.Ordered.Internal

Methods

traverse :: Applicative f => (a -> f b) -> OMap k a -> f (OMap k b)

sequenceA :: Applicative f => OMap k (f a) -> f (OMap k a)

mapM :: Monad m => (a -> m b) -> OMap k a -> m (OMap k b)

sequence :: Monad m => OMap k (m a) -> m (OMap k a)

Functor (OMap k)

Defined in Data.Map.Ordered.Internal

Methods

fmap :: (a -> b) -> OMap k a -> OMap k b

(<$) :: a -> OMap k b -> OMap k a

(Data k, Data a, Ord k) => Data (OMap k a)

Defined in Data.Map.Ordered.Internal

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> OMap k a -> c (OMap k a)

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (OMap k a)

toConstr :: OMap k a -> Constr

dataTypeOf :: OMap k a -> DataType

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (OMap k a))

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (OMap k a))

gmapT :: (forall b. Data b => b -> b) -> OMap k a -> OMap k a

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> OMap k a -> r

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> OMap k a -> r

gmapQ :: (forall d. Data d => d -> u) -> OMap k a -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> OMap k a -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> OMap k a -> m (OMap k a)

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> OMap k a -> m (OMap k a)

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> OMap k a -> m (OMap k 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 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 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 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 k, Read k, Read v) => Read (OMap k v)

Defined in Data.Map.Ordered.Internal

Methods

readsPrec :: Int -> ReadS (OMap k v)

readList :: ReadS [OMap k v]

readPrec :: ReadPrec (OMap k v)

readListPrec :: ReadPrec [OMap k v]

(Show k, Show v) => Show (OMap k v)

Defined in Data.Map.Ordered.Internal

Methods

showsPrec :: Int -> OMap k v -> ShowS

show :: OMap k v -> String

showList :: [OMap k v] -> ShowS

(Eq k, Eq v) => Eq (OMap k v)

Defined in Data.Map.Ordered.Internal

Methods

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

(/=) :: OMap k v -> OMap k v -> Bool

(Ord k, Ord v) => Ord (OMap k v)

Defined in Data.Map.Ordered.Internal

Methods

compare :: OMap k v -> OMap k v -> Ordering

(<) :: OMap k v -> OMap k v -> Bool

(<=) :: OMap k v -> OMap k v -> Bool

(>) :: OMap k v -> OMap k v -> Bool

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

max :: OMap k v -> OMap k v -> OMap k v

min :: OMap k v -> OMap k v -> OMap k v

Trivial maps

empty :: OMap k v

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

Insertion

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

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

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

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

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

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

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

See asymptotics of unionWithR.

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

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

See asymptotics of unionWithL.

unionWithL :: 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

unionWithR :: 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

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

Deletion/Update

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

filter :: 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

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

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

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

intersectionWith :: 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.

alter :: Ord k => (Maybe v -> Maybe v) -> k -> OMap k v -> OMap k v

Alter the value at k, or absence of. Can be used to insert delete or update with the same semantics as Maps alter

Query

null :: OMap k v -> Bool

size :: OMap k v -> Int

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

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

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

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

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

List conversions

fromList :: 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.

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

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

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

Return key-value pairs in order of increasing key.

Map conversion

toMap :: OMap k v -> Map k v

Convert an OMap to a Map.

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