Data.POMap.Internal

This module doesn't respect the PVP! Breaking changes may happen at any minor version (>= *.*.m.*)

Documentation

This is some setup code for doctest. >>> :set -XGeneralizedNewtypeDeriving >>> import Algebra.PartialOrd >>> import Data.POMap.Lazy >>> import Data.POMap.Internal >>> :{ newtype Divisibility = Div Int deriving (Eq, Num) instance Show Divisibility where show (Div a) = show a instance PartialOrd Divisibility where Div a leq Div b = b mod a == 0 type DivMap a = POMap Divisibility a default (Divisibility, DivMap String) :}

class SingIAreWeStrict (s :: AreWeStrict) where

Allows us to abstract over value-strictness in a zero-cost manner. GHC should always be able to specialise the two instances of this and consequently inline areWeStrict.

It's a little sad we can't just use regular singletons, for reasons outlined here.

Methods

areWeStrict :: Proxy# s -> AreWeStrict

Instances

SingIAreWeStrict Lazy

Defined in Data.POMap.Internal

Methods

areWeStrict :: Proxy# Lazy -> AreWeStrict

SingIAreWeStrict Strict

Defined in Data.POMap.Internal

Methods

areWeStrict :: Proxy# Strict -> AreWeStrict

seq' :: SingIAreWeStrict s => Proxy# s -> a -> b -> b

Should be inlined and specialised at all call sites.

seqList :: [a] -> [a]

data POMap k v

A map from partially-ordered keys k to values v.

Constructors

POMap !Int ![Map k v]

Instances

Functor (POMap k)

Defined in Data.POMap.Internal

Methods

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

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

Foldable (POMap k)

Defined in Data.POMap.Internal

Methods

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

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

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

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

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

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

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

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

toList :: POMap k a -> [a]

null :: POMap k a -> Bool

length :: POMap k a -> Int

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

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

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

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

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

Traversable (POMap k)

Defined in Data.POMap.Internal

Methods

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

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

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

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

PartialOrd k => IsList (POMap k v)

Defined in Data.POMap.Internal

Associated Types

type Item (POMap k v) :: Type

Methods

fromList :: [Item (POMap k v)] -> POMap k v

fromListN :: Int -> [Item (POMap k v)] -> POMap k v

toList :: POMap k v -> [Item (POMap k v)]

(PartialOrd k, Eq v) => Eq (POMap k v)

\(\mathcal{O}(wn\log n)\), where \(w=\max(w_1,w_2)), n=\max(n_1,n_2)\).

Defined in Data.POMap.Internal

Methods

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

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

(PartialOrd k, Read k, Read e) => Read (POMap k e)

Defined in Data.POMap.Internal

Methods

readsPrec :: Int -> ReadS (POMap k e)

readList :: ReadS [POMap k e]

readPrec :: ReadPrec (POMap k e)

readListPrec :: ReadPrec [POMap k e]

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

Defined in Data.POMap.Internal

Methods

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

show :: POMap k v -> String

showList :: [POMap k v] -> ShowS

(NFData k, NFData v) => NFData (POMap k v)

Defined in Data.POMap.Internal

Methods

rnf :: POMap k v -> ()

(PartialOrd k, PartialOrd v) => PartialOrd (POMap k v)

\(\mathcal{O}(wn\log n)\), where \(w=\max(w_1,w_2)), n=\max(n_1,n_2)\).

Defined in Data.POMap.Internal

Methods

leq :: POMap k v -> POMap k v -> Bool

comparable :: POMap k v -> POMap k v -> Bool

type Item (POMap k v)

Defined in Data.POMap.Internal

type Item (POMap k v) = (k, v)

mkPOMap :: [Map k v] -> POMap k v

Internal smart constructor so that we can be sure that we are always spine-strict, discard empty maps and have appropriate size information.

chainDecomposition :: POMap k v -> [Map k v]

Instances

Query

size :: POMap k v -> Int

\(\mathcal{O}(1)\). The number of elements in this map.

width :: POMap k v -> Int

\(\mathcal{O}(w)\). The width \(w\) of the chain decomposition in the internal data structure. This is always at least as big as the size of the biggest possible anti-chain.

foldEntry :: (Monoid m, PartialOrd k) => k -> (v -> m) -> POMap k v -> m

lookup :: PartialOrd k => k -> POMap k v -> Maybe v

\(\mathcal{O}(w\log n)\). Is the key a member of the map?

member :: PartialOrd k => k -> POMap k v -> Bool

\(\mathcal{O}(w\log n)\). Is the key a member of the map? See also notMember.

>>> member 5 (fromList [(5,'a'), (3,'b')]) == True
True
>>> member 1 (fromList [(5,'a'), (3,'b')]) == False
True

notMember :: PartialOrd k => k -> POMap k v -> Bool

\(\mathcal{O}(w\log n)\). Is the key not a member of the map? See also member.

>>> notMember 5 (fromList [(5,'a'), (3,'b')]) == False
True
>>> notMember 1 (fromList [(5,'a'), (3,'b')]) == True
True

findWithDefault :: PartialOrd k => v -> k -> POMap k v -> v

\(\mathcal{O}(w\log n)\). The expression (findWithDefault def k map) returns the value at key k or returns default value def when the key is not in the map.

>>> findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
True
>>> findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
True

data RelationalOperator

Constructors

LessThan

LessEqual

Equal

GreaterEqual

GreaterThan

Instances

Eq RelationalOperator

Defined in Data.POMap.Internal

Methods

(==) :: RelationalOperator -> RelationalOperator -> Bool

(/=) :: RelationalOperator -> RelationalOperator -> Bool

Ord RelationalOperator

Defined in Data.POMap.Internal

Methods

compare :: RelationalOperator -> RelationalOperator -> Ordering

(<) :: RelationalOperator -> RelationalOperator -> Bool

(<=) :: RelationalOperator -> RelationalOperator -> Bool

(>) :: RelationalOperator -> RelationalOperator -> Bool

(>=) :: RelationalOperator -> RelationalOperator -> Bool

max :: RelationalOperator -> RelationalOperator -> RelationalOperator

min :: RelationalOperator -> RelationalOperator -> RelationalOperator

Show RelationalOperator

Defined in Data.POMap.Internal

Methods

showsPrec :: Int -> RelationalOperator -> ShowS

show :: RelationalOperator -> String

showList :: [RelationalOperator] -> ShowS

flipRelationalOperator :: RelationalOperator -> RelationalOperator

containsOrdering :: Ordering -> RelationalOperator -> Bool

comparePartial :: PartialOrd k => k -> k -> Maybe Ordering

addToAntichain :: PartialOrd k => RelationalOperator -> (k, v) -> [(k, v)] -> [(k, v)]

dedupAntichain :: PartialOrd k => RelationalOperator -> [(k, v)] -> [(k, v)]

lookupX :: PartialOrd k => RelationalOperator -> k -> POMap k v -> [(k, v)]

lookupLT :: PartialOrd k => k -> POMap k v -> [(k, v)]

\(\mathcal{O}(w\log n)\). Find the largest set of keys smaller than the given one and return the corresponding list of (key, value) pairs.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupLT 3  (fromList [(3,'a'), (5,'b')])
[]
>>> lookupLT 9 (fromList [(3,'a'), (5,'b')])
[(3,'a')]

lookupLE :: PartialOrd k => k -> POMap k v -> [(k, v)]

\(\mathcal{O}(w\log n)\). Find the largest key smaller or equal to the given one and return the corresponding list of (key, value) pairs.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupLE 2 (fromList [(3,'a'), (5,'b')])
[]
>>> lookupLE 3 (fromList [(3,'a'), (5,'b')])
[(3,'a')]
>>> lookupLE 10 (fromList [(3,'a'), (5,'b')])
[(5,'b')]

lookupGE :: PartialOrd k => k -> POMap k v -> [(k, v)]

\(\mathcal{O}(w\log n)\). Find the smallest key greater or equal to the given one and return the corresponding list of (key, value) pairs.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupGE 3 (fromList [(3,'a'), (5,'b')])
[(3,'a')]
>>> lookupGE 5 (fromList [(3,'a'), (10,'b')])
[(10,'b')]
>>> lookupGE 6 (fromList [(3,'a'), (5,'b')])
[]

lookupGT :: PartialOrd k => k -> POMap k v -> [(k, v)]

\(\mathcal{O}(w\log n)\). Find the smallest key greater than the given one and return the corresponding list of (key, value) pairs.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupGT 5 (fromList [(3,'a'), (10,'b')])
[(10,'b')]
>>> lookupGT 5 (fromList [(3,'a'), (5,'b')])
[]

Construction

empty :: POMap k v

\(\mathcal{O}(1)\). The empty map.

>>> empty
fromList []
>>> size empty
0

singleton :: SingIAreWeStrict s => Proxy# s -> k -> v -> POMap k v

Insertion

insert :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> k -> v -> POMap k v -> POMap k v

insertWith :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (v -> v -> v) -> k -> v -> POMap k v -> POMap k v

insertWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> v -> v) -> k -> v -> POMap k v -> POMap k v

insertLookupWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> v -> v) -> k -> v -> POMap k v -> (Maybe v, POMap k v)

keyedInsertAsAlter :: (k -> v -> v -> v) -> v -> k -> Maybe v -> Maybe v

Deletion

data LookupResult a

Constructors

Incomparable

NotFound a

Found a

Instances

Functor LookupResult

Defined in Data.POMap.Internal

Methods

fmap :: (a -> b) -> LookupResult a -> LookupResult b

(<$) :: a -> LookupResult b -> LookupResult a

Eq a => Eq (LookupResult a)

Defined in Data.POMap.Internal

Methods

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

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

Ord a => Ord (LookupResult a)

Defined in Data.POMap.Internal

Methods

compare :: LookupResult a -> LookupResult a -> Ordering

(<) :: LookupResult a -> LookupResult a -> Bool

(<=) :: LookupResult a -> LookupResult a -> Bool

(>) :: LookupResult a -> LookupResult a -> Bool

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

max :: LookupResult a -> LookupResult a -> LookupResult a

min :: LookupResult a -> LookupResult a -> LookupResult a

Show a => Show (LookupResult a)

Defined in Data.POMap.Internal

Methods

showsPrec :: Int -> LookupResult a -> ShowS

show :: LookupResult a -> String

showList :: [LookupResult a] -> ShowS

overChains :: (Map k v -> LookupResult a) -> (Map k v -> b -> b) -> (a -> [Map k v] -> b) -> ([Map k v] -> b) -> POMap k v -> b

delete :: PartialOrd k => k -> POMap k v -> POMap k v

\(\mathcal{O}(w\log n)\). Delete a key and its value from the map. When the key is not a member of the map, the original map is returned.

>>> delete 5 (fromList [(5,"a"), (3,"b")])
fromList [(3,"b")]
>>> delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
True
>>> delete 5 empty
fromList []

deleteLookup :: PartialOrd k => k -> POMap k v -> (Maybe v, POMap k v)

\(\mathcal{O}(w\log n)\). Simultaneous delete and lookup.

adjust :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (v -> v) -> k -> POMap k v -> POMap k v

adjustWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> v) -> k -> POMap k v -> POMap k v

adjustLookupWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> v) -> k -> POMap k v -> (Maybe v, POMap k v)

update :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (v -> Maybe v) -> k -> POMap k v -> POMap k v

updateWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> Maybe v) -> k -> POMap k v -> POMap k v

updateLookupWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v)

alter :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v

alterWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v

alterChain :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> Maybe v -> Maybe v) -> k -> Map k v -> LookupResult (Map k v)

alterLookupWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v)

alterLookupChain :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> Maybe v -> Maybe v) -> k -> Map k v -> LookupResult (Maybe v, Map k v)

alterF :: (Functor f, PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (Maybe v -> f (Maybe v)) -> k -> POMap k v -> f (POMap k v)

alterFChain :: (Functor f, PartialOrd k, SingIAreWeStrict s) => Proxy# s -> k -> Map k v -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))

Combine

Union

union :: PartialOrd k => POMap k v -> POMap k v -> POMap k v

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). The expression (union t1 t2) takes the left-biased union of t1 and t2. It prefers t1 when duplicate keys are encountered, i.e. (union == unionWith const).

>>> union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
True

unionWith :: PartialOrd k => (v -> v -> v) -> POMap k v -> POMap k v -> POMap k v

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Union with a combining function.

>>> unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
True

unionWithKey :: PartialOrd k => (k -> v -> v -> v) -> POMap k v -> POMap k v -> POMap k v

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Union with a combining function.

>>> let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value
>>> unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]
True

unions :: PartialOrd k => [POMap k v] -> POMap k v

\(\mathcal{O}(wn\log n)\), where \(n=\max_i n_i\) and \(w=\max_i w_i\). The union of a list of maps: (unions == foldl union empty).

>>> :{
  unions [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
     == fromList [(3, "b"), (5, "a"), (7, "C")]
:}
True

>>> :{
 unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])]
     == fromList [(3, "B3"), (5, "A3"), (7, "C")]
:}
True

unionsWith :: PartialOrd k => (v -> v -> v) -> [POMap k v] -> POMap k v

\(\mathcal{O}(wn\log n)\), where \(n=\max_i n_i\) and \(w=\max_i w_i\). The union of a list of maps, with a combining operation: (unionsWith f == foldl (unionWith f) empty).

>>> :{
 unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
     == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
:}
True

Difference

difference :: PartialOrd k => POMap k a -> POMap k b -> POMap k a

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Difference of two maps. Return elements of the first map not existing in the second map.

>>> difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
fromList [(3,"b")]

differenceWith :: PartialOrd k => (a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the values of these keys. If it returns Nothing, the element is discarded (proper set difference). If it returns (Just y), the element is updated with a new value y.

>>> let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
>>> differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])
fromList [(3,"b:B")]

differenceWithKey :: PartialOrd k => (k -> a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the key and both values. If it returns Nothing, the element is discarded (proper set difference). If it returns (Just y), the element is updated with a new value y.

>>> let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
>>> differenceWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (10, "C")])
fromList [(3,"3:b|B")]

Intersection

intersection :: PartialOrd k => POMap k a -> POMap k b -> POMap k a

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Intersection of two maps. Return data in the first map for the keys existing in both maps. (intersection m1 m2 == intersectionWith const m1 m2).

>>> intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
fromList [(5,"a")]

intersectionWith :: PartialOrd k => (a -> b -> c) -> POMap k a -> POMap k b -> POMap k c

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Intersection with a combining function.

>>> intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
fromList [(5,"aA")]

intersectionWithKey :: PartialOrd k => (k -> a -> b -> c) -> POMap k a -> POMap k b -> POMap k c

\(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\). Intersection with a combining function.

>>> let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar
>>> intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
fromList [(5,"5:a|A")]

Traversals

map :: SingIAreWeStrict s => Proxy# s -> (a -> b) -> POMap k a -> POMap k b

mapWithKey :: SingIAreWeStrict s => Proxy# s -> (k -> a -> b) -> POMap k a -> POMap k b

traverseWithKey :: (Applicative t, SingIAreWeStrict s) => Proxy# s -> (k -> a -> t b) -> POMap k a -> t (POMap k b)

mapAccum :: SingIAreWeStrict s => Proxy# s -> (a -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c)

mapAccumWithKey :: SingIAreWeStrict s => Proxy# s -> (a -> k -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c)

mapKeys :: PartialOrd k2 => (k1 -> k2) -> POMap k1 v -> POMap k2 v

\(\mathcal{O}(wn\log n)\). mapKeys f s is the map obtained by applying f to each key of s.

The size of the result may be smaller if f maps two or more distinct keys to the same new key. In this case the value at the greatest of the original keys is retained.

>>> mapKeys (+ 1) (fromList [(5,"a"), (3,"b")]) == fromList [(4, "b"), (6, "a")]
True
>>> mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
fromList [(1,"c")]
>>> mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
fromList [(3,"c")]

mapKeysWith :: (PartialOrd k2, SingIAreWeStrict s) => Proxy# s -> (v -> v -> v) -> (k1 -> k2) -> POMap k1 v -> POMap k2 v

mapKeysMonotonic :: (k1 -> k2) -> POMap k1 v -> POMap k2 v

\(\mathcal{O}(n)\). mapKeysMonotonic f s == mapKeys f s, but works only when f is strictly monotonic. That is, for any values x and y, if x < y then f x < f y. The precondition is not checked. Semi-formally, for every chain ls in s we have:

and [x < y ==> f x < f y | x <- ls, y <- ls]
                    ==> mapKeysMonotonic f s == mapKeys f s

This means that f maps distinct original keys to distinct resulting keys. This function has better performance than mapKeys.

>>> mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
True

Folds

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

\(\mathcal{O}(n)\). A strict version of foldr. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

foldrWithKey :: (k -> a -> b -> b) -> b -> POMap k a -> b

\(\mathcal{O}(n)\). Fold the keys and values in the map using the given right-associative binary operator, such that foldrWithKey f z == foldr (uncurry f) z . toAscList.

For example,

>>> keys map = foldrWithKey (\k x ks -> k:ks) [] map

>>> let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
>>> foldrWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
True

foldrWithKey' :: (k -> a -> b -> b) -> b -> POMap k a -> b

\(\mathcal{O}(n)\). A strict version of foldrWithKey. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

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

\(\mathcal{O}(n)\). A strict version of foldl. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

foldlWithKey :: (b -> k -> a -> b) -> b -> POMap k a -> b

\(\mathcal{O}(n)\). Fold the keys and values in the map using the given left-associative binary operator, such that foldlWithKey f z == foldl (\z' (kx, x) -> f z' kx x) z . toAscList.

>>> keys = reverse . foldlWithKey (\ks k x -> k:ks) []

>>> let f result k a = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
>>> foldlWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (3:b)(5:a)"
True

foldlWithKey' :: (b -> k -> a -> b) -> b -> POMap k a -> b

\(\mathcal{O}(n)\). A strict version of foldlWithKey. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

foldMapWithKey :: Monoid m => (k -> a -> m) -> POMap k a -> m

\(\mathcal{O}(n)\). Fold the keys and values in the map using the given monoid, such that

foldMapWithKey f = fold . mapWithKey f

Conversion

elems :: POMap k v -> [v]

\(\mathcal{O}(n)\). Return all elements of the map in unspecified order.

>>> elems (fromList [(5,"a"), (3,"b")])
["b","a"]
>>> elems empty
[]

keys :: POMap k v -> [k]

\(\mathcal{O}(n)\). Return all keys of the map in unspecified order.

>>> keys (fromList [(5,"a"), (3,"b")])
[3,5]
>>> keys empty
[]

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

\(\mathcal{O}(n)\). Return all key/value pairs in the map in unspecified order.

>>> assocs (fromList [(5,"a"), (3,"b")])
[(3,"b"),(5,"a")]
>>> assocs empty
[]

toList :: POMap k v -> [(k, v)]

\(\mathcal{O}(n)\). Return all key/value pairs in the map in unspecified order.

Currently, toList = assocs.

toLinearisation :: PartialOrd k => POMap k v -> [(k, v)]

\(\mathcal{O}(w^2n)\). Return all key/value pairs in the map such that map fst (toLinearisation m) is a linearisation of the all keys present in the map. E.g., for any key k1 occuring before k2 in the linearisation, it cannot happen that k1 is strictly greater than k2 (so they are either incomparable or k1 <= k2).

fromLinearisation :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> [(k, v)] -> POMap k v

fromListImpl :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> [(k, v)] -> POMap k v

Intentionally named this way, to disambiguate it from fromList. This is so that we can doctest this module.

fromListWith :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (v -> v -> v) -> [(k, v)] -> POMap k v

fromListWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> v -> v) -> [(k, v)] -> POMap k v

Filter

filter :: (v -> Bool) -> POMap k v -> POMap k v

\(\mathcal{O}(n)\). Filter all values that satisfy the predicate.

>>> filter (> "a") (fromList [(5,"a"), (3,"b")])
fromList [(3,"b")]
>>> filter (> "x") (fromList [(5,"a"), (3,"b")])
fromList []
>>> filter (< "a") (fromList [(5,"a"), (3,"b")])
fromList []

filterWithKey :: (k -> v -> Bool) -> POMap k v -> POMap k v

\(\mathcal{O}(n)\). Filter all keys/values that satisfy the predicate.

>>> filterWithKey (\(Div k) _ -> k > 4) (fromList [(5,"a"), (3,"b")])
fromList [(5,"a")]

partition :: (v -> Bool) -> POMap k v -> (POMap k v, POMap k v)

\(\mathcal{O}(n)\). Partition the map according to a predicate. The first map contains all elements that satisfy the predicate, the second all elements that fail the predicate. See also split.

>>> partition (> "a") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b")], fromList [(5, "a")])
True
>>> partition (< "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
True
>>> partition (> "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
True

partitionWithKey :: (k -> v -> Bool) -> POMap k v -> (POMap k v, POMap k v)

\(\mathcal{O}(n)\). Partition the map according to a predicate. The first map contains all elements that satisfy the predicate, the second all elements that fail the predicate. See also split.

>>> partitionWithKey (\ (Div k) _ -> k > 3) (fromList [(5,"a"), (3,"b")]) == (fromList [(5, "a")], fromList [(3, "b")])
True
>>> partitionWithKey (\ (Div k) _ -> k < 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
True
>>> partitionWithKey (\ (Div k) _ -> k > 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
True

takeWhileAntitone :: (k -> Bool) -> POMap k v -> POMap k v

\(\mathcal{O}(\log n)\). Take while a predicate on the keys holds. The user is responsible for ensuring that for all keys j and k in the map, j < k ==> p j >= p k. See note at spanAntitone.

takeWhileAntitone p = filterWithKey (k _ -> p k)

Since: 0.0.1.0

dropWhileAntitone :: (k -> Bool) -> POMap k v -> POMap k v

\(\mathcal{O}(\log n)\). Drop while a predicate on the keys holds. The user is responsible for ensuring that for all keys j and k in the map, j < k ==> p j >= p k. See note at spanAntitone.

dropWhileAntitone p = filterWithKey (k -> not (p k))

Since: 0.0.1.0

spanAntitone :: (k -> Bool) -> POMap k v -> (POMap k v, POMap k v)

\(\mathcal{O}(log n)\). Divide a map at the point where a predicate on the keys stops holding. The user is responsible for ensuring that for all keys j and k in the map, j < k ==> p j >= p k.

spanAntitone p xs = partitionWithKey (k _ -> p k) xs

Note: if p is not actually antitone, then spanAntitone will split the map at some unspecified point where the predicate switches from holding to not holding (where the predicate is seen to hold before the first key and to fail after the last key).

Since: 0.0.1.0

mapMaybe :: SingIAreWeStrict s => Proxy# s -> (a -> Maybe b) -> POMap k a -> POMap k b

mapMaybeWithKey :: SingIAreWeStrict s => Proxy# s -> (k -> a -> Maybe b) -> POMap k a -> POMap k b

traverseMaybeWithKey :: (Applicative f, SingIAreWeStrict s) => Proxy# s -> (k -> a -> f (Maybe b)) -> POMap k a -> f (POMap k b)

mapEither :: SingIAreWeStrict s => Proxy# s -> (a -> Either b c) -> POMap k a -> (POMap k b, POMap k c)

mapEitherWithKey :: SingIAreWeStrict s => Proxy# s -> (k -> a -> Either b c) -> POMap k a -> (POMap k b, POMap k c)

Submap

isSubmapOf :: (PartialOrd k, Eq v) => POMap k v -> POMap k v -> Bool

\(\mathcal{O}(n_2 w_1 n_1 \log n_1)\). This function is defined as (isSubmapOf = isSubmapOfBy (==)).

isSubmapOfBy :: PartialOrd k => (a -> b -> Bool) -> POMap k a -> POMap k b -> Bool

\(\mathcal{O}(n_2 w_1 n_1 \log n_1)\). The expression (isSubmapOfBy f t1 t2) returns True if all keys in t1 are in tree t2, and when f returns True when applied to their respective values. For example, the following expressions are all True:

>>> isSubmapOfBy (==) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
True
>>> isSubmapOfBy (<=) (fromList [(1,'a')]) (fromList [(1,'b'),(2,'c')])
True
>>> isSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a'),(2,'b')])
True

But the following are all False:

>>> isSubmapOfBy (==) (fromList [(2,'a')]) (fromList [(1,'a'),(2,'b')])
False
>>> isSubmapOfBy (<)  (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
False
>>> isSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a')])
False

isProperSubmapOf :: (PartialOrd k, Eq v) => POMap k v -> POMap k v -> Bool

\(\mathcal{O}(n_2 w_1 n_1 \log n_1)\). Is this a proper submap? (ie. a submap but not equal). Defined as (isProperSubmapOf = isProperSubmapOfBy (==)).

isProperSubmapOfBy :: PartialOrd k => (a -> b -> Bool) -> POMap k a -> POMap k b -> Bool

\(\mathcal{O}(n_2 w_1 n_1 \log n_1)\). Is this a proper submap? (ie. a submap but not equal). The expression (isProperSubmapOfBy f m1 m2) returns True when m1 and m2 are not equal, all keys in m1 are in m2, and when f returns True when applied to their respective values. For example, the following expressions are all True:

>>> isProperSubmapOfBy (==) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
True
>>> isProperSubmapOfBy (<=) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
True

But the following are all False:

>>> isProperSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a'),(2,'b')])
False
>>> isProperSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a')])
False
>>> isProperSubmapOfBy (<)  (fromList [(1,'a')])         (fromList [(1,'a'),(2,'b')])
False

Min/Max

lookupMin :: PartialOrd k => POMap k v -> [(k, v)]

\(\mathcal{O}(w\log n)\). The minimal keys of the map.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupMin (fromList [(6,"a"), (3,"b")])
[(3,"b")]
>>> lookupMin empty
[]

lookupMax :: PartialOrd k => POMap k v -> [(k, v)]

\(\mathcal{O}(w\log n)\). The maximal keys of the map.

Note that the following examples assume the Divisibility partial order defined at the top.

>>> lookupMax (fromList [(6,"a"), (3,"b")])
[(6,"a")]
>>> lookupMax empty
[]