Data.POMap.Strict

A reasonably efficient implementation of partially ordered maps from keys to values (dictionaries).

The API of this module is strict in both the keys and the values. If you need value-lazy maps, use Data.POMap.Lazy instead. The POMap type is shared between the lazy and strict modules, meaning that the same POMap value can be passed to functions in both modules (although that is rarely needed).

A consequence of this is that the Functor, Traversable and Data instances are the same as for the Data.POMap.Lazy module, so if they are used on strict maps, the resulting maps will be lazy.

These modules are intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.

import qualified Data.POMap.Strict as POMap

The implementation of POMap is based on a decomposition of chains (totally ordered submaps), inspired by "Sorting and Selection in Posets".

Operation comments contain the operation time complexity in Big-O notation and commonly refer to two characteristics of the poset from which keys are drawn: The number of elements in the map \(n\) and the width \(w\) of the poset, referring to the size of the biggest anti-chain (set of incomparable elements).

Generally speaking, lookup and mutation operations incur an additional factor of \(\mathcal{O}(w)\) compared to their counter-parts in Data.Map.Strict.

Note that for practical applications, the width of the poset should be in the order of \(w\in \mathcal{O}(\frac{n}{\log n})\), otherwise a simple lookup list is asymptotically superior. Even if that holds, the constants might be too big to be useful for any \(n\) that can can happen in practice.

The following examples assume the following definitions for a map on the divisibility relation on Integers:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

import           Algebra.PartialOrd
import           Data.POMap.Strict (POMap)
import qualified Data.POMap.Strict as POMap

newtype Divisibility
  = Div Int
  deriving (Eq, Read, Show, Num)

default (Divisibility)

instance PartialOrd Divisibility where
  Div a `leq` Div b = b `mod` a == 0

type DivMap a = POMap Divisibility a

-- We want integer literals to be interpreted as Divisibilitys
-- and default emptys to DivMap String.
default (Divisibility, DivMap String)

Divisility is actually an example for a PartialOrd that should not be used as keys of POMap. Its width is \(w=\frac{n}{2}\in\Omega(n)\)!

Map type

data POMap k v

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

Instances

Functor (POMap k)

Methods

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

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

Foldable (POMap k)

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)

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)

Associated Types

type Item (POMap k v) :: *

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

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)

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)

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)

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

Methods

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

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

type Item (POMap k v)

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

Query

null :: Foldable t => forall a. t a -> Bool

Test whether the structure is empty. The default implementation is optimized for structures that are similar to cons-lists, because there is no general way to do better.

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.

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

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

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

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

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')]

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')])
[]

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')])
[]

Construction

empty :: POMap k v

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

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

singleton :: k -> v -> POMap k v

\(\mathcal{O}(1)\). A map with a single element.

>>> singleton 1 'a'
fromList [(1,'a')]
>>> size (singleton 1 'a')
1

Insertion

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

\(\mathcal{O}(w\log n)\). Insert a new key and value in the map. If the key is already present in the map, the associated value is replaced with the supplied value. insert is equivalent to insertWith const.

>>> insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3,'b'), (5,'x')]
True
>>> insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3,'b'), (5,'a'), (7,'x')]
True
>>> insert 5 'x' empty                         == singleton 5 'x'
True

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

\(\mathcal{O}(w\log n)\). Insert with a function, combining new value and old value. insertWith f key value mp will insert the pair (key, value) into mp if key does not exist in the map. If the key does exist, the function will insert the pair (key, f new_value old_value).

>>> insertWith (++) 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "xxxa")]
True
>>> insertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
True
>>> insertWith (++) 5 "xxx" empty                         == singleton 5 "xxx"
True

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

\(\mathcal{O}(w\log n)\). Insert with a function, combining key, new value and old value. insertWithKey f key value mp will insert the pair (key, value) into mp if key does not exist in the map. If the key does exist, the function will insert the pair (key,f key new_value old_value). Note that the key passed to f is the same key passed to insertWithKey.

>>> let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
>>> insertWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:xxx|a")]
True
>>> insertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
True
>>> insertWithKey f 5 "xxx" empty                         == singleton 5 "xxx"
True

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

\(\mathcal{O}(w\log n)\). Combines insert operation with old value retrieval. The expression (insertLookupWithKey f k x map) is a pair where the first element is equal to (lookup k map) and the second element equal to (insertWithKey f k x map).

>>> let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
>>> insertLookupWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:xxx|a")])
True
>>> insertLookupWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "xxx")])
True
>>> insertLookupWithKey f 5 "xxx" empty                         == (Nothing,  singleton 5 "xxx")
True

This is how to define insertLookup using insertLookupWithKey:

>>> let insertLookup kx x t = insertLookupWithKey (\_ a _ -> a) kx x t
>>> insertLookup 5 "x" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "x")])
True
>>> insertLookup 7 "x" (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "x")])
True

Delete/Update

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 => (v -> v) -> k -> POMap k v -> POMap k v

\(\mathcal{O}(w\log n)\). Adjust a value at a specific key with the result of the provided function. When the key is not a member of the map, the original map is returned.

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

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

\(\mathcal{O}(w\log n)\). Adjust a value at a specific key with the result of the provided function. When the key is not a member of the map, the original map is returned.

>>> let f key x = (show key) ++ ":new " ++ x
>>> adjustWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
True
>>> adjustWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
True
>>> adjustWithKey f 7 empty                         == empty
True

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

\(\mathcal{O}(w\log n)\). Adjust a value at a specific key with the result of the provided function and simultaneously look up the old value at that key. When the key is not a member of the map, the original map is returned.

>>> let f key old_value = show key ++ ":" ++ show 42 ++ "|" ++ old_value
>>> adjustLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:42|a")])
True
>>> adjustLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a")])
True
>>> adjustLookupWithKey f 5 empty                         == (Nothing,  empty)
True

update :: PartialOrd k => (v -> Maybe v) -> k -> POMap k v -> POMap k v

\(\mathcal{O}(w\log n)\). The expression (update f k map) updates the value x at k (if it is in the map). If (f x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y.

>>> let f x = if x == "a" then Just "new a" else Nothing
>>> update f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
True
>>> update f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
True
>>> update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
True

updateWithKey :: PartialOrd k => (k -> v -> Maybe v) -> k -> POMap k v -> POMap k v

\(\mathcal{O}(w\log n)\). The expression (updateWithKey f k map) updates the value x at k (if it is in the map). If (f k x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y.

>>> let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
>>> updateWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
True
>>> updateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
True
>>> updateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
True

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

\(\mathcal{O}(w\log n)\). Lookup and update. See also updateWithKey. Warning: Contrary to Data.Map.Strict, the lookup does not return the updated value, but the old value. This is consistent with insertLookupWithKey and also Data.IntMap.Strict.updateLookupWithKey.

Re-apply the updating function to the looked-up value once more to get the value in the map, like in the last example:

>>> let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
>>> updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:new a")])
True
>>> updateLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a")])
True
>>> updateLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")
True
>>> fst (updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")])) >>= f 5
Just "5:new a"

alter :: PartialOrd k => (Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v

\(\mathcal{O}(w\log n)\). The expression (alter f k map) alters the value x at k, or absence thereof. alter can be used to insert, delete, or update a value in a Map. In short : lookup k (alter f k m) = f (lookup k m).

>>> let f _ = Nothing
>>> alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
True
>>> alter f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
True
>>> let f _ = Just "c"
>>> alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "c")]
True
>>> alter f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "c")]
True

alterWithKey :: PartialOrd k => (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v

\(\mathcal{O}(w\log n)\). The expression (alterWithKey f k map) alters the value x at k, or absence thereof. alterWithKey can be used to insert, delete, or update a value in a Map. In short : lookup k (alter f k m) = f k (lookup k m).

>>> let f _ _ = Nothing
>>> alterWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
True
>>> alterWithKey f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
True
>>> let f k _ = Just (show k ++ ":c")
>>> alterWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "7:c")]
True
>>> alterWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:c")]
True

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

\(\mathcal{O}(w\log n)\). Lookup and alteration. See also alterWithKey.

>>> let f k x = if x == Nothing then Just ((show k) ++ ":new a") else Nothing
>>> alterLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b")])
True
>>> alterLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "7:new a")])
True
>>> alterLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")
True

alterF :: (Functor f, PartialOrd k) => (Maybe v -> f (Maybe v)) -> k -> POMap k v -> f (POMap k v)

\(\mathcal{O}(w\log n)\). The expression (alterF f k map) alters the value x at k, or absence thereof. alterF can be used to inspect, insert, delete, or update a value in a Map. In short: lookup k <$> alterF f k m = f (lookup k m).

Example:

interactiveAlter :: Divibility -> DivMap String -> IO (DivMap String)
interactiveAlter k m = alterF f k m where
  f Nothing -> do
     putStrLn $ show k ++
         " was not found in the map. Would you like to add it?"
     getUserResponse1 :: IO (Maybe String)
  f (Just old) -> do
     putStrLn "The key is currently bound to " ++ show old ++
         ". Would you like to change or delete it?"
     getUserresponse2 :: IO (Maybe String)

alterF is the most general operation for working with an individual key that may or may not be in a given map. When used with trivial functors like Identity and Const, it is often slightly slower than more specialized combinators like lookup and insert. However, when the functor is non-trivial and key comparison is not particularly cheap, it is the fastest way.

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")]

Traversal

Map

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

\(\mathcal{O}(n)\). Map a function over all values in the map.

>>> map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
True

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

\(\mathcal{O}(n)\). Map a function over all values in the map.

>>> let f key x = (show key) ++ ":" ++ x
>>> mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]
True

traverseWithKey :: Applicative t => (k -> a -> t b) -> POMap k a -> t (POMap k b)

\(\mathcal{O}(n)\). traverseWithKey f m == fromList $ traverse ((k, v) -> (v' -> v' seq (k,v')) $ f k v) (toList m) That is, it behaves much like a regular traverse except that the traversing function also has access to the key associated with a value and the values are forced before they are installed in the result map.

>>> traverseWithKey (\(Div k) v -> if odd k then Just (succ v) else Nothing) (fromList [(1, 'a'), (5, 'e')]) == Just (fromList [(1, 'b'), (5, 'f')])
True
>>> traverseWithKey (\(Div k) v -> if odd k then Just (succ v) else Nothing) (fromList [(2, 'c')])           == Nothing
True

traverseMaybeWithKey :: Applicative t => (k -> a -> t (Maybe b)) -> POMap k a -> t (POMap k b)

\(\mathcal{O}(n)\). Traverse keys/values and collect the Just results.

Contrary to traverse, this is value-strict.

mapAccum :: (a -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c)

\(\mathcal{O}(n)\). The function mapAccum threads an accumulating argument through the map in ascending order of keys.

>>> let f a b = (a ++ b, b ++ "X")
>>> mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
True

mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c)

\(\mathcal{O}(n)\). The function mapAccumWithKey threads an accumulating argument through the map in ascending order of keys.

>>> let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")
>>> mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])
True

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 => (v -> v -> v) -> (k1 -> k2) -> POMap k1 v -> POMap k2 v

\(\mathcal{O}(wn\log n)\). mapKeysWith c 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 associated values will be combined using c.

>>> mapKeysWith (+) (\ _ -> 1) (fromList [(1,1), (2,2), (3,3), (4,4)]) == singleton 1 10
True
>>> mapKeysWith (+) (\ _ -> 3) (fromList [(1,1), (2,1), (3,1), (4,1)]) == singleton 3 4
True

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

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

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

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

Strict 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.

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.

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.

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.

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
[]

Lists

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

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

Currently, toList = assocs.

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

\(\mathcal{O}(wn\log n)\). Build a map from a list of key/value pairs. If the list contains more than one value for the same key, the last value for the key is retained.

This version is strict in its values, as opposed to the IsList instance for POMap.

>>> fromList [] == (empty :: DivMap String)
True
>>> fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]
True
>>> fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]
True

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

\(\mathcal{O}(wn\log n)\). Build a map from a list of key/value pairs with a combining function.

This version is strict in its values, as opposed to the IsList instance for POMap.

>>> fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
True
>>> fromListWith (++) [] == (empty :: DivMap String)
True

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

\(\mathcal{O}(wn\log n)\). Build a map from a list of key/value pairs with a combining function.

>>> let f k a1 a2 = (show k) ++ a1 ++ a2
>>> fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "3ab"), (5, "5a5ba")]
True
>>> fromListWithKey f [] == (empty :: DivMap String)
True

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 :: (a -> Maybe b) -> POMap k a -> POMap k b

\(\mathcal{O}(n)\). Map values and collect the Just results.

>>> let f x = if x == "a" then Just "new a" else Nothing
>>> mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"
True

mapMaybeWithKey :: (k -> a -> Maybe b) -> POMap k a -> POMap k b

\(\mathcal{O}(n)\). Map keys/values and collect the Just results.

>>> let f k _ = if k == 3 then Just ("key : " ++ (show k)) else Nothing
>>> mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"
True

mapEither :: (a -> Either b c) -> POMap k a -> (POMap k b, POMap k c)

\(\mathcal{O}(n)\). Map values and separate the Left and Right results.

>>> let f a = if a < "c" then Left a else Right a

>>> :{
  mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")])
:}
True

>>> :{
  mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
:}
True

mapEitherWithKey :: (k -> a -> Either b c) -> POMap k a -> (POMap k b, POMap k c)

\(\mathcal{O}(n)\). Map keys/values and separate the Left and Right results.

>>> let f (Div k) a = if k < 5 then Left (k * 2) else Right (a ++ a)

>>> :{
  mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")])
:}
True

>>> :{
  mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")])
:}
True

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
[]