Data.MonoidMap.Internal

Provides internal operations for the MonoidMap type.

Types

newtype MonoidMap k v

Constructors

MonoidMap (Map k (NonNull v))

Instances

Bifoldable MonoidMap

Defined in Data.MonoidMap.Internal

Methods

bifold :: Monoid m => MonoidMap m m -> m

bifoldMap :: Monoid m => (a -> m) -> (b -> m) -> MonoidMap a b -> m

bifoldr :: (a -> c -> c) -> (b -> c -> c) -> c -> MonoidMap a b -> c

bifoldl :: (c -> a -> c) -> (c -> b -> c) -> c -> MonoidMap a b -> c

Eq2 MonoidMap

Defined in Data.MonoidMap.Internal

Methods

liftEq2 :: (a -> b -> Bool) -> (c -> d -> Bool) -> MonoidMap a c -> MonoidMap b d -> Bool

Show2 MonoidMap

Defined in Data.MonoidMap.Internal

Methods

liftShowsPrec2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> Int -> MonoidMap a b -> ShowS

liftShowList2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> [MonoidMap a b] -> ShowS

Foldable (MonoidMap k)

Defined in Data.MonoidMap.Internal

Methods

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

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

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

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

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

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

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

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

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

toList :: MonoidMap k a -> [a]

null :: MonoidMap k a -> Bool

length :: MonoidMap k a -> Int

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

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

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

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

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

Eq k => Eq1 (MonoidMap k)

Defined in Data.MonoidMap.Internal

Methods

liftEq :: (a -> b -> Bool) -> MonoidMap k a -> MonoidMap k b -> Bool

Show k => Show1 (MonoidMap k)

Defined in Data.MonoidMap.Internal

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> MonoidMap k a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [MonoidMap k a] -> ShowS

(Ord k, MonoidNull v) => Monoid (MonoidMap k v)

Defined in Data.MonoidMap.Internal

Methods

mempty :: MonoidMap k v

mappend :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v

mconcat :: [MonoidMap k v] -> MonoidMap k v

(Ord k, MonoidNull v) => Semigroup (MonoidMap k v)

Defined in Data.MonoidMap.Internal

Methods

(<>) :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v

sconcat :: NonEmpty (MonoidMap k v) -> MonoidMap k v

stimes :: Integral b => b -> MonoidMap k v -> MonoidMap k v

(Ord k, MonoidNull v) => IsList (MonoidMap k v)

Defined in Data.MonoidMap.Internal

Associated Types

type Item (MonoidMap k v)

Methods

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

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

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

(Ord k, Read k, MonoidNull v, Read v) => Read (MonoidMap k v)

Defined in Data.MonoidMap.Internal

Methods

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

readList :: ReadS [MonoidMap k v]

readPrec :: ReadPrec (MonoidMap k v)

readListPrec :: ReadPrec [MonoidMap k v]

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

Defined in Data.MonoidMap.Internal

Methods

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

show :: MonoidMap k v -> String

showList :: [MonoidMap k v] -> ShowS

(Ord k, MonoidNull v, Commutative v) => Commutative (MonoidMap k v)

Defined in Data.MonoidMap.Internal

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

Defined in Data.MonoidMap.Internal

Methods

rnf :: MonoidMap k v -> ()

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

Defined in Data.MonoidMap.Internal

Methods

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

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

(Ord k, MonoidNull v, Abelian v) => Abelian (MonoidMap k v)

Defined in Data.MonoidMap.Internal

(Ord k, MonoidNull v, Group v) => Group (MonoidMap k v)

Defined in Data.MonoidMap.Internal

Methods

invert :: MonoidMap k v -> MonoidMap k v

(~~) :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v

pow :: Integral x => MonoidMap k v -> x -> MonoidMap k v

(Ord k, MonoidNull v, DistributiveGCDMonoid v) => DistributiveGCDMonoid (MonoidMap k v)

Defined in Data.MonoidMap.Internal

(Ord k, MonoidNull v, GCDMonoid v) => GCDMonoid (MonoidMap k v)

Defined in Data.MonoidMap.Internal

Methods

gcd :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v

(Ord k, MonoidNull v, LeftDistributiveGCDMonoid v) => LeftDistributiveGCDMonoid (MonoidMap k v)

Defined in Data.MonoidMap.Internal

(Ord k, MonoidNull v, LeftGCDMonoid v) => LeftGCDMonoid (MonoidMap k v)

Defined in Data.MonoidMap.Internal

Methods

commonPrefix :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v

stripCommonPrefix :: MonoidMap k v -> MonoidMap k v -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)

(Ord k, MonoidNull v, RightDistributiveGCDMonoid v) => RightDistributiveGCDMonoid (MonoidMap k v)

Defined in Data.MonoidMap.Internal

(Ord k, MonoidNull v, RightGCDMonoid v) => RightGCDMonoid (MonoidMap k v)

Defined in Data.MonoidMap.Internal

Methods

commonSuffix :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v

stripCommonSuffix :: MonoidMap k v -> MonoidMap k v -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)

(Ord k, MonoidNull v, DistributiveLCMMonoid v) => DistributiveLCMMonoid (MonoidMap k v)

Defined in Data.MonoidMap.Internal

(Ord k, MonoidNull v, LCMMonoid v) => LCMMonoid (MonoidMap k v)

Defined in Data.MonoidMap.Internal

Methods

lcm :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v

(Ord k, MonoidNull v, Monus v) => Monus (MonoidMap k v)

Defined in Data.MonoidMap.Internal

Methods

(<\>) :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v

(Ord k, MonoidNull v, OverlappingGCDMonoid v) => OverlappingGCDMonoid (MonoidMap k v)

Defined in Data.MonoidMap.Internal

Methods

stripPrefixOverlap :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v

stripSuffixOverlap :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v

overlap :: MonoidMap k v -> MonoidMap k v -> MonoidMap k v

stripOverlap :: MonoidMap k v -> MonoidMap k v -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)

(Ord k, MonoidNull v) => MonoidNull (MonoidMap k v)

Defined in Data.MonoidMap.Internal

Methods

null :: MonoidMap k v -> Bool

(Ord k, PositiveMonoid v) => PositiveMonoid (MonoidMap k v)

Defined in Data.MonoidMap.Internal

(Ord k, MonoidNull v, Cancellative v) => Cancellative (MonoidMap k v)

Defined in Data.MonoidMap.Internal

(Ord k, MonoidNull v, LeftCancellative v) => LeftCancellative (MonoidMap k v)

Defined in Data.MonoidMap.Internal

(Ord k, MonoidNull v, LeftReductive v) => LeftReductive (MonoidMap k v)

Defined in Data.MonoidMap.Internal

Methods

isPrefixOf :: MonoidMap k v -> MonoidMap k v -> Bool

stripPrefix :: MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)

(Ord k, MonoidNull v, Reductive v) => Reductive (MonoidMap k v)

Defined in Data.MonoidMap.Internal

Methods

(</>) :: MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)

(Ord k, MonoidNull v, RightCancellative v) => RightCancellative (MonoidMap k v)

Defined in Data.MonoidMap.Internal

(Ord k, MonoidNull v, RightReductive v) => RightReductive (MonoidMap k v)

Defined in Data.MonoidMap.Internal

Methods

isSuffixOf :: MonoidMap k v -> MonoidMap k v -> Bool

stripSuffix :: MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)

(NoThunks k, NoThunks v) => NoThunks (MonoidMap k v)

Defined in Data.MonoidMap.Internal

Methods

noThunks :: Context -> MonoidMap k v -> IO (Maybe ThunkInfo)

wNoThunks :: Context -> MonoidMap k v -> IO (Maybe ThunkInfo)

showTypeOf :: Proxy (MonoidMap k v) -> String

type Item (MonoidMap k v)

Defined in Data.MonoidMap.Internal

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

newtype NonNull v

Constructors

UnsafeNonNull

Fields

• getNonNull :: v

General operations

Construction

empty :: MonoidMap k v

\(O(1)\). The empty MonoidMap.

Satisfies the following property for all possible keys k:

get k empty == mempty

Provides the definition of mempty for the MonoidMap instance of Monoid.

fromList :: (Ord k, MonoidNull v) => [(k, v)] -> MonoidMap k v

\(O(n \log n)\). Constructs a MonoidMap from a list of key-value pairs.

If the list contains more than one value for the same key, values are combined together in the order that they appear with the (<>) operator.

Satisfies the following property for all possible keys k:

get k (fromList kvs) ==
    foldMap snd (filter ((== k) . fst) kvs)

Satisfies the following round-trip property:

fromList (toList m) == m

Examples

With String values:

>>> fromList [(1,"a"), (2,"x"), (1,"b"), (2,"y"), (1,"c"), (2,"z")]
fromList [(1,"abc"), (2,"xyz")]

fromListWith

Arguments

:: (Ord k, MonoidNull v)

=> (v -> v -> v)

Function with which to combine values for duplicate keys.

-> [(k, v)]

-> MonoidMap k v

\(O(n \log n)\). Constructs a MonoidMap from a list of key-value pairs, with a combining function for values.

If the list contains more than one value for the same key, values are combined together in the order that they appear with the given combining function.

Satisfies the following property for all possible keys k:

get k (fromListWith f kvs) ==
    maybe mempty (foldl1 f)
        (nonEmpty (snd <$> filter ((== k) . fst) kvs))

fromMap :: MonoidNull v => Map k v -> MonoidMap k v

\(O(n)\). Constructs a MonoidMap from an ordinary Map.

Satisfies the following property for all possible keys k:

get k (fromMap m) == findWithDefault mempty k m

This function performs canonicalisation of null values, and has a time complexity that is linear in the length of the list.

singleton :: (Ord k, MonoidNull v) => k -> v -> MonoidMap k v

\(O(1)\). Constructs a MonoidMap from a single key-value pair.

Satisfies the following property:

get k (singleton k v) == v

Nullifying the value for key k produces an empty map:

nullify k (singleton k v) == empty

Deconstruction

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

\(O(n)\). Converts a MonoidMap to a list of key-value pairs, where the keys are in ascending order.

The result only includes entries with values that are not null.

Satisfies the following round-trip property:

fromList (toList m) == m

The resulting list is sorted in ascending key order:

sortOn fst (toList m) == toList m

toMap :: forall k v. MonoidMap k v -> Map k v

\(O(1)\). Converts a MonoidMap to an ordinary Map.

The result only includes entries with values that are not null.

Satisfies the following round-trip property:

fromMap (toMap m) == m

Lookup

get :: (Ord k, Monoid v) => k -> MonoidMap k v -> v

\(O(\log n)\). Gets the value associated with the given key.

By default, every key in an empty map is associated with a value of mempty:

∀ k. get k empty == mempty

Modification

set :: (Ord k, MonoidNull v) => k -> v -> MonoidMap k v -> MonoidMap k v

\(O(\log n)\). Sets the value associated with the given key.

Satisfies the following property:

get k (set k v m) == v

adjust :: (Ord k, MonoidNull v) => (v -> v) -> k -> MonoidMap k v -> MonoidMap k v

\(O(\log n)\). Adjusts the value associated with the given key.

Satisfies the following property:

adjust f k m == set k (f (get k m)) m

nullify :: Ord k => k -> MonoidMap k v -> MonoidMap k v

\(O(\log n)\). Sets the value associated with the given key to mempty.

Satisfies the following property:

get k (nullify k m) == mempty

Membership

null :: MonoidMap k v -> Bool

\(O(1)\). Returns True if (and only if) all values in the map are null.

Satisfies the following property:

null m == (∀ k. nullKey k m)

Provides the definition of null for the MonoidMap instance of MonoidNull.

nullKey :: Ord k => k -> MonoidMap k v -> Bool

\(O(\log n)\). Returns True if (and only if) the given key is associated with a value that is null.

Satisfies the following property:

nullKey k m == null (get k m)

nonNull :: MonoidMap k v -> Bool

\(O(1)\). Returns True if (and only if) the map contains at least one value that is not null.

Satisfies the following property:

nonNull m == (∃ k. nonNullKey k m)

nonNullCount :: MonoidMap k v -> Int

\(O(1)\). Returns a count of all values in the map that are not null.

Satisfies the following property:

nonNullCount m == size (nonNullKeys m)

nonNullKey :: Ord k => k -> MonoidMap k v -> Bool

\(O(\log n)\). Returns True if (and only if) the given key is associated with a value that is not null.

Satisfies the following property:

nonNullKey k m == not (null (get k m))

nonNullKeys :: MonoidMap k v -> Set k

\(O(n)\). Returns the set of keys associated with values that are not null.

Satisfies the following property:

k `member` (nonNullKeys m) == nonNullKey k m

Slicing

take :: Int -> MonoidMap k v -> MonoidMap k v

\(O(\log n)\). Takes a slice from a map.

This function takes a given number of non-null entries from a map, producing a new map from the entries that were taken.

Entries are taken in key order, beginning with the smallest keys.

Satifies the following property:

take n == fromList . take n . toList

drop :: Int -> MonoidMap k v -> MonoidMap k v

\(O(\log n)\). Drops a slice from a map.

This function drops a given number of non-null entries from a map, producing a new map from the entries that remain.

Entries are dropped in key order, beginning with the smallest keys.

Satifies the following property:

drop n == fromList . drop n . toList

splitAt :: Int -> MonoidMap k a -> (MonoidMap k a, MonoidMap k a)

\(O(\log n)\). Splits a map into two slices.

This function is equivalent to a combination of take and drop:

splitAt n m == (take n m, drop n m)

The resulting maps can be combined to reproduce the original map:

splitAt n m &
    \(m1, m2) -> m1 <> m2 == m

The resulting maps have disjoint sets of non-null entries:

splitAt n m &
    \(m1, m2) -> disjoint (nonNullKeys m1) (nonNullKeys m2)

Filtering

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

\(O(n)\). Filters a map according to a predicate on values.

Satisfies the following property for all possible keys k:

get k (filter f m) ==
    if f (get k m)
    then get k m
    else mempty

The resulting map is identical to that obtained by constructing a map from a filtered list of key-value pairs:

filter f m == fromList (filter (f . snd) (toList m))

filterKeys :: (k -> Bool) -> MonoidMap k v -> MonoidMap k v

\(O(n)\). Filters a map according to a predicate on keys.

Satisfies the following property for all possible keys k:

get k (filterKeys f m) ==
    if f k
    then get k m
    else mempty

The resulting map is identical to that obtained by constructing a map from a filtered list of key-value pairs:

filter f m == fromList (filter (f . fst) (toList m))

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

\(O(n)\). Filters a map according to a predicate on keys and values.

Satisfies the following property for all possible keys k:

get k (filterWithKey f m) ==
    if f k (get k m)
    then get k m
    else mempty

The resulting map is identical to that obtained by constructing a map from a filtered list of key-value pairs:

filterWithKey f m == fromList (filter (uncurry f) (toList m))

Partitioning

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

\(O(n)\). Partitions a map according to a predicate on values.

Satisfies the following property:

partition f m ==
    ( filter        f  m
    , filter (not . f) m
    )

The resulting maps can be combined to reproduce the original map:

partition f m & \(m1, m2) ->
    m1 <> m2 == m

The resulting maps have disjoint sets of non-null entries:

partition f m & \(m1, m2) ->
    disjoint
        (nonNullKeys m1)
        (nonNullKeys m2)

partitionKeys :: (k -> Bool) -> MonoidMap k v -> (MonoidMap k v, MonoidMap k v)

\(O(n)\). Partitions a map according to a predicate on keys.

Satisfies the following property:

partitionKeys f m ==
    ( filterKeys        f  m
    , filterKeys (not . f) m
    )

The resulting maps can be combined to reproduce the original map:

partitionKeys f m & \(m1, m2) ->
    m1 <> m2 == m

The resulting maps have disjoint sets of non-null entries:

partitionKeys f m & \(m1, m2) ->
    disjoint
        (nonNullKeys m1)
        (nonNullKeys m2)

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

\(O(n)\). Partitions a map according to a predicate on keys and values.

Satisfies the following property:

partitionWithKey f m ==
    ( filterWithKey                    f  m
    , filterWithKey ((fmap . fmap) not f) m
    )

The resulting maps can be combined to reproduce the original map:

partitionWithKey f m & \(m1, m2) ->
    m1 <> m2 == m

The resulting maps have disjoint sets of non-null entries:

partitionWithKey f m & \(m1, m2) ->
    disjoint
        (nonNullKeys m1)
        (nonNullKeys m2)

Mapping

map :: MonoidNull v2 => (v1 -> v2) -> MonoidMap k v1 -> MonoidMap k v2

\(O(n)\). Applies a function to all non-null values of a MonoidMap.

Satisfies the following properties for all functions f:

(get k m == mempty) ==> (get k (map f m) == mempty     )
(get k m /= mempty) ==> (get k (map f m) == f (get k m))

Conditional properties

If applying function f to mempty produces mempty, then the following additional properties hold:

(f mempty == mempty)
    ==>
    (∀ k. get k (map f m) == f (get k m))

(f mempty == mempty)
    ==>
    (∀ g. map (f . g) m == map f (map g m))

mapKeys :: (Ord k2, MonoidNull v) => (k1 -> k2) -> MonoidMap k1 v -> MonoidMap k2 v

\(O(n \log n)\). Applies a function to all the keys of a MonoidMap that are associated with non-null values.

If the resultant map would contain more than one value for the same key, values are combined together in ascending key order with the (<>) operator.

Satisfies the following property for all possible keys k:

get k (mapKeys f m) ==
    foldMap
        (`get` m)
        (filter ((==) k . f) (nonNullKeys m))

mapKeysWith

Arguments

:: (Ord k2, MonoidNull v)

=> (v -> v -> v)

Function with which to combine values for duplicate keys.

-> (k1 -> k2)

-> MonoidMap k1 v

-> MonoidMap k2 v

\(O(n \log n)\). Applies a function to all the keys of a MonoidMap that are associated with non-null values, with a combining function for values.

If the resultant map would contain more than one value for the same key, values are combined together in ascending key order with the given combining function.

Satisfies the following property:

mapKeysWith c f == fromListWith c . fmap (first f) . toList

Monoidal operations

Association

append :: (Ord k, MonoidNull v) => MonoidMap k v -> MonoidMap k v -> MonoidMap k v

Appends a pair of maps together.

Uses the Semigroup operator (<>) to append each value in the first map to its matching value in the second map.

Satisfies the following property for all possible keys k:

get k (append m1 m2) == get k m1 <> get k m2

This function provides the definition of (<>) for the MonoidMap instance of Semigroup.

Examples

With String values:

>>> m1 = fromList [(1, "abc"), (2, "ij" ), (3, "p"  )            ]
>>> m2 = fromList [            (2, "  k"), (3,  "qr"), (4, "xyz")]
>>> m3 = fromList [(1, "abc"), (2, "ijk"), (3, "pqr"), (4, "xyz")]

>>> append m1 m2 == m3
True

With Sum Natural values:

>>> m1 = fromList [("a", 4), ("b", 2), ("c", 1)          ]
>>> m2 = fromList [          ("b", 1), ("c", 2), ("d", 4)]
>>> m3 = fromList [("a", 4), ("b", 3), ("c", 3), ("d", 4)]

>>> append m1 m2 == m3
True

Subtraction

minus :: (Ord k, MonoidNull v, Group v) => MonoidMap k v -> MonoidMap k v -> MonoidMap k v

Performs group subtraction of the second map from the first.

Uses the Group subtraction operator (~~) to subtract each value in the second map from its matching value in the first map.

Satisfies the following property for all possible keys k:

get k (m1 `minus` m2) == get k m1 ~~ get k m2

This function provides the definition of (~~) for the MonoidMap instance of Group.

Examples

With Sum Integer values, this function performs normal integer subtraction of matching values:

>>> m1 = fromList [("a", (-1)), ("b",   0 ), ("c", 1)]
>>> m2 = fromList [("a",   1 ), ("b",   1 ), ("c", 1)]
>>> m3 = fromList [("a", (-2)), ("b", (-1)), ("c", 0)]

>>> m1 `minus` m2 == m3
True

>>> m1 = fromList [("a", (-1)), ("b",   0 ), ("c",   1 )]
>>> m2 = fromList [("a", (-1)), ("b", (-1)), ("c", (-1))]
>>> m3 = fromList [("a",   0 ), ("b",   1 ), ("c",   2 )]

>>> m1 `minus` m2 == m3
True

minusMaybe :: (Ord k, MonoidNull v, Reductive v) => MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)

Performs reductive subtraction of the second map from the first.

Uses the Reductive subtraction operator (</>) to subtract each value in the second map from its matching value in the first map.

This function produces a result if (and only if) for all possible keys k, it is possible to subtract the value for k in the second map from the value for k in the first map:

isJust (m1 `minusMaybe` m2)
    == (∀ k. isJust (get k m1 </> get k m2))

Otherwise, this function returns Nothing.

This function satisfies the following property:

all
   (\r -> Just (get k r) == get k m1 </> get k m2)
   (m1 `minusMaybe` m2)

This function provides the definition of (</>) for the MonoidMap instance of Reductive.

Examples

With Set Natural values, this function performs set subtraction of matching values, succeeding if (and only if) each value from the second map is a subset of its matching value from the first map:

f xs = fromList (fromList <$> xs)

>>> m1 = f [("a", [0,1,2]), ("b", [0,1,2])]
>>> m2 = f [("a", [     ]), ("b", [0,1,2])]
>>> m3 = f [("a", [0,1,2]), ("b", [     ])]

>>> m1 `minusMaybe` m2 == Just m3
True

>>> m1 = f [("a", [0,1,2]), ("b", [0,1,2]), ("c", [0,1,2])]
>>> m2 = f [("a", [0    ]), ("b", [  1  ]), ("c", [    2])]
>>> m3 = f [("a", [  1,2]), ("b", [0,  2]), ("c", [0,1  ])]

>>> m1 `minusMaybe` m2 == Just m3
True

>>> m1 = f [("a", [0,1,2    ]), ("b", [0,1,2    ]), ("c", [0,1,2    ])]
>>> m2 = f [("a", [    2,3,4]), ("b", [  1,2,3,4]), ("c", [0,1,2,3,4])]

>>> m1 `minusMaybe` m2 == Nothing
True

With Sum Natural values, this function performs ordinary subtraction of matching values, succeeding if (and only if) each value from the second map is less than or equal to its matching value from the first map:

>>> m1 = fromList [("a", 2), ("b", 3), ("c", 5), ("d", 8)]
>>> m2 = fromList [("a", 0), ("b", 0), ("c", 0), ("d", 0)]
>>> m3 = fromList [("a", 2), ("b", 3), ("c", 5), ("d", 8)]

>>> m1 `minusMaybe` m2 == Just m3
True

>>> m1 = fromList [("a", 2), ("b", 3), ("c", 5), ("d", 8)]
>>> m2 = fromList [("a", 1), ("b", 2), ("c", 3), ("d", 5)]
>>> m3 = fromList [("a", 1), ("b", 1), ("c", 2), ("d", 3)]

>>> m1 `minusMaybe` m2 == Just m3
True

>>> m1 = fromList [("a", 2), ("b", 3), ("c", 5), ("d", 8)]
>>> m2 = fromList [("a", 2), ("b", 3), ("c", 5), ("d", 8)]
>>> m3 = fromList [("a", 0), ("b", 0), ("c", 0), ("d", 0)]

>>> m1 `minusMaybe` m2 == Just m3
True

>>> m1 = fromList [("a", 2), ("b", 3), ("c", 5), ("d", 8)]
>>> m2 = fromList [("a", 3), ("b", 3), ("c", 5), ("d", 8)]

>>> m1 `minusMaybe` m2 == Nothing
True

monus :: (Ord k, MonoidNull v, Monus v) => MonoidMap k v -> MonoidMap k v -> MonoidMap k v

Performs monus subtraction of the second map from the first.

Uses the Monus subtraction operator (<\>) to subtract each value in the second map from its matching value in the first map.

Satisfies the following property for all possible keys k:

get k (m1 `monus` m2) == get k m1 <\> get k m2

This function provides the definition of (<\>) for the MonoidMap instance of Monus.

Examples

With Set Natural values, this function performs set subtraction of matching values:

f xs = fromList (fromList <$> xs)

>>> m1 = f [("a", [0,1,2]), ("b", [0,1,2])]
>>> m2 = f [("a", [     ]), ("b", [0,1,2])]
>>> m3 = f [("a", [0,1,2]), ("b", [     ])]

>>> m1 `monus` m2 == m3
True

>>> m1 = f [("a", [0,1,2]), ("b", [0,1,2]), ("c", [0,1,2])]
>>> m2 = f [("a", [0    ]), ("b", [  1  ]), ("c", [    2])]
>>> m3 = f [("a", [  1,2]), ("b", [0,  2]), ("c", [0,1  ])]

>>> m1 `monus` m2 == m3
True

>>> m1 = f [("a", [0,1,2    ]), ("b", [0,1,2    ]), ("c", [0,1,2    ])]
>>> m2 = f [("a", [    2,3,4]), ("b", [  1,2,3,4]), ("c", [0,1,2,3,4])]
>>> m3 = f [("a", [0,1      ]), ("b", [0        ]), ("c", [         ])]

>>> m1 `monus` m2 == m3
True

With Sum Natural values, this function performs truncated subtraction of matching values:

>>> m1 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
>>> m2 = fromList [("a", 0), ("b", 0), ("c", 0), ("d", 0)]
>>> m3 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3)]

>>> m1 `monus` m2 == m3
True

>>> m1 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
>>> m2 = fromList [("a", 1), ("b", 1), ("c", 1), ("d", 1)]
>>> m3 = fromList [("a", 0), ("b", 0), ("c", 1), ("d", 2)]

>>> m1 `monus` m2 == m3
True

>>> m1 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
>>> m2 = fromList [("a", 2), ("b", 2), ("c", 2), ("d", 2)]
>>> m3 = fromList [("a", 0), ("b", 0), ("c", 0), ("d", 1)]

>>> m1 `monus` m2 == m3
True

>>> m1 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
>>> m2 = fromList [("a", 4), ("b", 4), ("c", 4), ("d", 4)]
>>> m3 = fromList [("a", 0), ("b", 0), ("c", 0), ("d", 0)]

>>> m1 `monus` m2 == m3
True

Inversion

invert :: (MonoidNull v, Group v) => MonoidMap k v -> MonoidMap k v

Inverts every value in a map.

Applies the Group method invert to every value in a map.

Satisfies the following property for all possible keys k:

get k (invert m) == invert (get k m)

This function provides the definition of invert for the MonoidMap instance of Group.

Examples

With Sum Integer values, this function performs negation of values:

>>> m1 = fromList [("a", (-1)), ("b", 0), ("c",   1) ]
>>> m2 = fromList [("a",   1 ), ("b", 0), ("c", (-1))]

>>> negate m1 == m2
True

Exponentiation

power :: (Integral i, MonoidNull v, Group v) => MonoidMap k v -> i -> MonoidMap k v

Performs exponentiation of every value in a map.

Uses the Group exponentiation method pow to raise every value in a map to the power of the given exponent.

Satisfies the following property for all possible keys k:

get k (m `power` i) == get k m `pow` i

This function provides the definition of pow for the MonoidMap instance of Group.

Examples

With Sum Natural values, this function performs ordinary multiplication of all values by the given exponent:

>>> m1 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
>>> m2 = fromList [("a", 0), ("b", 2), ("c", 4), ("d", 6)]

>>> m1 `power` 2 == m2
True

>>> m1 = fromList [("a", 0), ("b",   1 ), ("c",   2 ), ("d",   3 )]
>>> m2 = fromList [("a", 0), ("b", (-1)), ("c", (-2)), ("d", (-3))]

>>> m1 `power` (-1) == m2
True

Comparison

isSubmapOf :: (Ord k, Monoid v, Reductive v) => MonoidMap k v -> MonoidMap k v -> Bool

Indicates whether or not the first map is a submap of the second.

Map m1 is a submap of map m2 if (and only if) m1 can be subtracted from m2 with the minusMaybe operation:

m1 `isSubmapOf` m2 == isJust (m2 `minusMaybe` m1)

Equivalently, map m1 is a submap of map m2 if (and only if) for all possible keys k, the value for k in m1 can be subtracted from the value for k in m2 with the (</>) operator:

m1 `isSubmapOf` m2 == (∀ k. isJust (get k m2 </> get k m1))

isSubmapOfBy

Arguments

:: (Ord k, Monoid v1, Monoid v2)

=> (v1 -> v2 -> Bool)

Function with which to compare values for matching keys.

-> MonoidMap k v1

-> MonoidMap k v2

-> Bool

Indicates whether or not the first map is a submap of the second, using the given function to compare values for matching keys.

Satisfies the following property:

isSubmapOfBy f m1 m2 ==
    all (\k -> f (get k m1) (get k m2)) (nonNullKeys m1)

Conditional totality

If the given comparison function f always evaluates to True when its first argument is mempty:

∀ v. f mempty v

Then the following property holds:

isSubmapOfBy f m1 m2 == (∀ k. f (get k m1) (get k m2))

disjoint :: (Ord k, GCDMonoid v, MonoidNull v) => MonoidMap k v -> MonoidMap k v -> Bool

Indicates whether or not a pair of maps are disjoint.

Maps m1 and m2 are disjoint if (and only if) their intersection is empty:

disjoint m1 m2 == (intersection m1 m2 == mempty)

Equivalently, maps m1 and m2 are disjoint if (and only if) for all possible keys k, the values for k in m1 and m2 have a gcd that is null:

disjoint m1 m2 == (∀ k. null (gcd (get k m1) (get k m2)))

disjointBy

Arguments

:: (Ord k, Monoid v1, Monoid v2)

=> (v1 -> v2 -> Bool)

Function with which to test pairs of values for matching keys.

-> MonoidMap k v1

-> MonoidMap k v2

-> Bool

Indicates whether or not a pair of maps are disjoint using the given indicator function to test pairs of values for matching keys.

Satisfies the following property:

disjointBy f m1 m2 ==
    all
        (\k -> f (get k m1) (get k m2))
        (intersection (nonNullKeys m1) (nonNullKeys m2))

Conditional totality

If the given indicator function f always evaluates to True when either or both of its arguments are mempty:

∀ v. (f v mempty) && (f mempty v)

Then the following property holds:

disjointBy f m1 m2 == (∀ k. f (get k m1) (get k m2))

Intersection

intersection :: (Ord k, MonoidNull v, GCDMonoid v) => MonoidMap k v -> MonoidMap k v -> MonoidMap k v

Finds the intersection of two maps.

The intersection of maps m1 and m2 is the greatest single map m that is a submap of both m1 and m2:

intersection m1 m2 `isSubmapOf` m1
intersection m1 m2 `isSubmapOf` m2

The intersection is unique:

and
    [ intersection m1 m2 `isSubmapOf` m
    ,                                 m `isSubmapOf` m1
    ,                                 m `isSubmapOf` m2
    ]
==>
    (m == intersection m1 m2)

The following property holds for all possible keys k:

get k (intersection m1 m2) == gcd (get k m1) (get k m2)

This function provides the definition of gcd for the MonoidMap instance of GCDMonoid.

Examples

With Product Natural values, this function computes the greatest common divisor of each pair of matching values:

>>> m1 = fromList [("a", 2), ("b",  6), ("c", 15), ("d", 35)]
>>> m2 = fromList [("a", 6), ("b", 15), ("c", 35), ("d", 77)]
>>> m3 = fromList [("a", 2), ("b",  3), ("c",  5), ("d",  7)]

>>> intersection m1 m2 == m3
True

With Sum Natural values, this function computes the minimum of each pair of matching values:

>>> m1 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
>>> m2 = fromList [("a", 3), ("b", 2), ("c", 1), ("d", 0)]
>>> m3 = fromList [("a", 0), ("b", 1), ("c", 1), ("d", 0)]

>>> intersection m1 m2 == m3
True

With Set Natural values, this function computes the set intersection of each pair of matching values:

f xs = fromList (fromList <$> xs)

>>> m1 = f [("a", [0,1,2]), ("b", [0,1,2  ]), ("c", [0,1,2    ])]
>>> m2 = f [("a", [0,1,2]), ("b", [  1,2,3]), ("c", [    2,3,4])]
>>> m3 = f [("a", [0,1,2]), ("b", [  1,2  ]), ("c", [    2    ])]

>>> intersection m1 m2 == m3
True

intersectionWith

Arguments

:: (Ord k, MonoidNull v3)

=> (v1 -> v2 -> v3)

Function with which to combine values for matching keys.

-> MonoidMap k v1

-> MonoidMap k v2

-> MonoidMap k v3

Computes the intersection of a pair of maps using the given function to combine values for matching keys.

Satisfies the following property for all possible keys k:

get k (intersectionWith f m1 m2) ==
    if k `member`
        intersection
            (nonNullKeys m1)
            (nonNullKeys m2)
    then f (get k m1) (get k m2)
    else mempty

Conditional totality

If the given combining function f always produces mempty when either or both of its arguments are mempty:

(f v      mempty == mempty) &&
(f mempty v      == mempty)

Then the following property holds for all possible keys k:

get k (intersectionWith f m1 m2) == f (get k m1) (get k m2)

Examples

With the min function applied to Sum Natural values:

>>> m1 = fromList [("a", 4), ("b", 3), ("c", 2), ("d", 1)          ]
>>> m2 = fromList [          ("b", 1), ("c", 2), ("d", 3), ("e", 4)]
>>> m3 = fromList [          ("b", 1), ("c", 2), ("d", 1)          ]

>>> intersectionWith min m1 m2 == m3
True

intersectionWithA

Arguments

:: (Applicative f, Ord k, MonoidNull v3)

=> (v1 -> v2 -> f v3)

Function with which to combine values for matching keys.

-> MonoidMap k v1

-> MonoidMap k v2

-> f (MonoidMap k v3)

An applicative version of intersectionWith.

Satisfies the following property:

runIdentity (intersectionWithA ((fmap . fmap) Identity f) m1 m2)
         == (intersectionWith                          f  m1 m2)

Union

union :: (Ord k, MonoidNull v, LCMMonoid v) => MonoidMap k v -> MonoidMap k v -> MonoidMap k v

Finds the union of two maps.

The union of maps m1 and m2 is the smallest single map m that includes both m1 and m2 as submaps:

m1 `isSubmapOf` union m1 m2
m2 `isSubmapOf` union m1 m2

The union is unique:

and
    [ m1 `isSubmapOf` m
    , m2 `isSubmapOf` m
    ,                 m `isSubmapOf` union m1 m2
    ]
==>
    (m == union m1 m2)

The following property holds for all possible keys k:

get k (union m1 m2) == lcm (get k m1) (get k m2)

This function provides the definition of lcm for the MonoidMap instance of LCMMonoid.

Examples

With Product Natural values, this function computes the least common multiple of each pair of matching values:

>>> m1 = fromList [("a", 2), ("b",  6), ("c",  15), ("d",  35)]
>>> m2 = fromList [("a", 6), ("b", 15), ("c",  35), ("d",  77)]
>>> m3 = fromList [("a", 6), ("b", 30), ("c", 105), ("d", 385)]

>>> union m1 m2 == m3
True

With Sum Natural values, this function computes the maximum of each pair of matching values:

>>> m1 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
>>> m2 = fromList [("a", 3), ("b", 2), ("c", 1), ("d", 0)]
>>> m3 = fromList [("a", 3), ("b", 2), ("c", 2), ("d", 3)]

>>> union m1 m2 == m3
True

With Set Natural values, this function computes the set union of each pair of matching values:

f xs = fromList (fromList <$> xs)

>>> m1 = f [("a", [0,1,2]), ("b", [0,1,2  ]), ("c", [0,1,2    ])]
>>> m2 = f [("a", [0,1,2]), ("b", [  1,2,3]), ("c", [    2,3,4])]
>>> m3 = f [("a", [0,1,2]), ("b", [0,1,2,3]), ("c", [0,1,2,3,4])]

>>> union m1 m2 == m3
True

unionWith

Arguments

:: (Ord k, Monoid v1, Monoid v2, MonoidNull v3)

=> (v1 -> v2 -> v3)

Function with which to combine values for matching keys.

-> MonoidMap k v1

-> MonoidMap k v2

-> MonoidMap k v3

Computes the union of a pair of maps using the given function to combine values for matching keys.

Satisfies the following property for all possible keys k:

get k (unionWith f m1 m2) ==
    if k `member`
        union
            (nonNullKeys m1)
            (nonNullKeys m2)
    then f (get k m1) (get k m2)
    else mempty

Conditional totality

If the given combining function f always produces mempty when both of its arguments are mempty:

f mempty mempty == mempty

Then the following property holds for all possible keys k:

get k (unionWith f m1 m2) == f (get k m1) (get k m2)

Examples

With the max function applied to Sum Natural values:

>>> m1 = fromList [("a", 4), ("b", 3), ("c", 2), ("d", 1)          ]
>>> m2 = fromList [          ("b", 1), ("c", 2), ("d", 3), ("e", 4)]
>>> m3 = fromList [("a", 4), ("b", 3), ("c", 2), ("d", 3), ("e", 4)]

>>> unionWith max m1 m2 == m3
True

unionWithA

Arguments

:: (Applicative f, Ord k, Monoid v1, Monoid v2, MonoidNull v3)

=> (v1 -> v2 -> f v3)

Function with which to combine values for matching keys.

-> MonoidMap k v1

-> MonoidMap k v2

-> f (MonoidMap k v3)

An applicative version of unionWith.

Satisfies the following property:

runIdentity (unionWithA ((fmap . fmap) Identity f) m1 m2)
         == (unionWith                          f  m1 m2)

Prefixes

isPrefixOf :: (Ord k, Monoid v, LeftReductive v) => MonoidMap k v -> MonoidMap k v -> Bool

Indicates whether or not the first map is a prefix of the second.

MonoidMap m1 is a prefix of MonoidMap m2 if (and only if) for all possible keys k, the value for k in m1 is a prefix of the value for k in m2:

m1 `isPrefixOf` m2 == (∀ k. get k m1 `isPrefixOf` get k m2)

This function provides the definition of isPrefixOf for the MonoidMap instance of LeftReductive.

Examples

With String values:

>>> m1 = fromList [(1, "a"  ), (2, "p"  ), (3, "x"  )]
>>> m2 = fromList [(1, "abc"), (2, "pqr"), (3, "xyz")]
>>> m1 `isPrefixOf` m2
True

>>> m1 = fromList [            (2, "p"  )            ]
>>> m2 = fromList [(1, "abc"), (2, "pqr"), (3, "xyz")]
>>> m1 `isPrefixOf` m2
True

>>> m1 = fromList [(1, "abc"), (2, "p"  ), (3, "x"  )]
>>> m2 = fromList [(1, "a"  ), (2, "pqr"), (3, "xyz")]
>>> m1 `isPrefixOf` m2
False

With Sum Natural values:

>>> m1 = fromList [("a", 1), ("b", 1), ("c", 1)]
>>> m2 = fromList [("a", 2), ("b", 4), ("c", 8)]
>>> m1 `isPrefixOf` m2
True

>>> m1 = fromList [          ("b", 1)          ]
>>> m2 = fromList [("a", 2), ("b", 4), ("c", 8)]
>>> m1 `isPrefixOf` m2
True

>>> m1 = fromList [("a", 2), ("b", 1), ("c", 1)]
>>> m2 = fromList [("a", 1), ("b", 4), ("c", 8)]
>>> m1 `isPrefixOf` m2
False

stripPrefix :: (Ord k, MonoidNull v, LeftReductive v) => MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)

Strips a prefix from a MonoidMap.

If map m1 is a prefix of map m2, then stripPrefix m1 m2 will produce a reduced map where prefix m1 is stripped from m2.

Properties

The stripPrefix function, when applied to maps m1 and m2, produces a result if (and only if) m1 is a prefix of m2:

isJust (stripPrefix m1 m2) == m1 `isPrefixOf` m2

The value for any key k in the result is identical to the result of stripping the value for k in map m1 from the value for k in map m2:

all
   (\r -> Just (get k r) == stripPrefix (get k m1) (get k m2))
   (stripPrefix m1 m2)

If we append prefix m1 to the left-hand side of the result, we can always recover the original map m2:

all
   (\r -> m1 <> r == m2)
   (stripPrefix m1 m2)

This function provides the definition of stripPrefix for the MonoidMap instance of LeftReductive.

Examples

With String values:

>>> m1 = fromList [(1, ""   ), (2, "i"  ), (3, "pq" ), (4, "xyz")]
>>> m2 = fromList [(1, "abc"), (2, "ijk"), (3, "pqr"), (4, "xyz")]
>>> m3 = fromList [(1, "abc"), (2,  "jk"), (3,   "r"), (4,    "")]

>>> stripPrefix m1 m2 == Just m3
True

>>> stripPrefix m2 m1 == Nothing
True

With Sum Natural values:

>>> m1 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
>>> m2 = fromList [("a", 3), ("b", 3), ("c", 3), ("d", 3)]
>>> m3 = fromList [("a", 3), ("b", 2), ("c", 1), ("d", 0)]

>>> stripPrefix m1 m2 == Just m3
True

>>> stripPrefix m2 m1 == Nothing
True

commonPrefix :: (Ord k, MonoidNull v, LeftGCDMonoid v) => MonoidMap k v -> MonoidMap k v -> MonoidMap k v

Finds the greatest common prefix of two maps.

Satisfies the following property for all possible keys k:

get k (commonPrefix m1 m2)
    == commonPrefix (get k m1) (get k m2)

This function provides the definition of commonPrefix for the MonoidMap instance of LeftGCDMonoid.

Examples

With String values:

>>> m1 = fromList [(1, "+++"), (2, "b++"), (3, "cc+"), (4, "ddd")]
>>> m2 = fromList [(1, "---"), (2, "b--"), (3, "cc-"), (4, "ddd")]
>>> m3 = fromList [(1, ""   ), (2, "b"  ), (3, "cc" ), (4, "ddd")]

>>> commonPrefix m1 m2 == m3
True

With Sum Natural values:

>>> m1 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
>>> m2 = fromList [("a", 2), ("b", 2), ("c", 2), ("d", 2)]
>>> m3 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 2)]

>>> commonPrefix m1 m2 == m3
True

stripCommonPrefix :: (Ord k, MonoidNull v, LeftGCDMonoid v) => MonoidMap k v -> MonoidMap k v -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)

Strips the greatest common prefix from a pair of maps.

Given two maps m1 and m2, stripCommonPrefix produces a tuple (p, r1, r2), where:

• p is the greatest common prefix of m1 and m2
• r1 is the remainder of stripping prefix p from m1
• r2 is the remainder of stripping prefix p from m2

The resulting prefix p can be appended to the left-hand side of either remainder r1 or r2 to reproduce either of the original maps m1 or m2 respectively:

stripCommonPrefix m1 m2
   & \(p, r1, _) -> p <> r1 == m1
stripCommonPrefix m1 m2
   & \(p, _, r2) -> p <> r2 == m2

Prefix p is identical to the result of applying commonPrefix to m1 and m2:

stripCommonPrefix m1 m2
   & \(p, _, _) -> p == commonPrefix m1 m2

Remainders r1 and r2 are identical to the results of applying stripPrefix to p and m1 or to p and m2 respectively:

stripCommonPrefix m1 m2
   & \(p, r1, _) -> Just r1 == stripPrefix p m1
stripCommonPrefix m1 m2
   & \(p, _, r2) -> Just r2 == stripPrefix p m2

This function provides the definition of stripCommonPrefix for the MonoidMap instance of LeftGCDMonoid.

Examples

With String values:

>>> m1 = fromList [(1, "+++"), (2, "a++"), (3, "aa+"), (4, "aaa")]
>>> m2 = fromList [(1, "---"), (2, "a--"), (3, "aa-"), (4, "aaa")]

>>> p  = fromList [(1, ""   ), (2, "a"  ), (3, "aa" ), (4, "aaa")]
>>> r1 = fromList [(1, "+++"), (2,  "++"), (3,   "+"), (4,    "")]
>>> r2 = fromList [(1, "---"), (2,  "--"), (3,   "-"), (4,    "")]

>>> stripCommonPrefix m1 m2 == (p, r1, r2)
True

With Sum Natural values:

>>> m1 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3), ("e", 4)]
>>> m2 = fromList [("a", 4), ("b", 3), ("c", 2), ("d", 1), ("e", 0)]

>>> p  = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 1), ("e", 0)]
>>> r1 = fromList [("a", 0), ("b", 0), ("c", 0), ("d", 2), ("e", 4)]
>>> r2 = fromList [("a", 4), ("b", 2), ("c", 0), ("d", 0), ("e", 0)]

>>> stripCommonPrefix m1 m2 == (p, r1, r2)
True

Suffixes

isSuffixOf :: (Ord k, Monoid v, RightReductive v) => MonoidMap k v -> MonoidMap k v -> Bool

Indicates whether or not the first map is a suffix of the second.

MonoidMap m1 is a suffix of MonoidMap m2 if (and only if) for all possible keys k, the value for k in m1 is a suffix of the value for k in m2:

m1 `isSuffixOf` m2 == (∀ k. get k m1 `isSuffixOf` get k m2)

This function provides the definition of isSuffixOf for the MonoidMap instance of RightReductive.

Examples

With String values:

>>> m1 = fromList [(1,   "c"), (2,   "r"), (3,   "z")]
>>> m2 = fromList [(1, "abc"), (2, "pqr"), (3, "xyz")]
>>> m1 `isSuffixOf` m2
True

>>> m1 = fromList [            (2,   "r")            ]
>>> m2 = fromList [(1, "abc"), (2, "pqr"), (3, "xyz")]
>>> m1 `isSuffixOf` m2
True

>>> m1 = fromList [(1, "abc"), (2,   "r"), (3,   "z")]
>>> m2 = fromList [(1,   "c"), (2, "pqr"), (3, "xyz")]
>>> m1 `isSuffixOf` m2
False

With Sum Natural values:

>>> m1 = fromList [("a", 1), ("b", 1), ("c", 1)]
>>> m2 = fromList [("a", 2), ("b", 4), ("c", 8)]
>>> m1 `isSuffixOf` m2
True

>>> m1 = fromList [          ("b", 1)          ]
>>> m2 = fromList [("a", 2), ("b", 4), ("c", 8)]
>>> m1 `isSuffixOf` m2
True

>>> m1 = fromList [("a", 2), ("b", 1), ("c", 1)]
>>> m2 = fromList [("a", 1), ("b", 4), ("c", 8)]
>>> m1 `isSuffixOf` m2
False

stripSuffix :: (Ord k, MonoidNull v, RightReductive v) => MonoidMap k v -> MonoidMap k v -> Maybe (MonoidMap k v)

Strips a suffix from a MonoidMap.

If map m1 is a suffix of map m2, then stripSuffix m1 m2 will produce a reduced map where suffix m1 is stripped from m2.

Properties

The stripSuffix function, when applied to maps m1 and m2, produces a result if (and only if) m1 is a suffix of m2:

isJust (stripSuffix m1 m2) == m1 `isSuffixOf` m2

The value for any key k in the result is identical to the result of stripping the value for k in map m1 from the value for k in map m2:

all
   (\r -> Just (get k r) == stripSuffix (get k m1) (get k m2))
   (stripSuffix m1 m2)

If we append suffix m1 to the right-hand side of the result, we can always recover the original map m2:

all
   (\r -> r <> m1 == m2)
   (stripSuffix m1 m2)

This function provides the definition of stripSuffix for the MonoidMap instance of RightReductive.

Examples

With String values:

>>> m1 = fromList [(1,    ""), (2,   "k"), (3,  "qr"), (4, "xyz")]
>>> m2 = fromList [(1, "abc"), (2, "ijk"), (3, "pqr"), (4, "xyz")]
>>> m3 = fromList [(1, "abc"), (2, "ij" ), (3, "p"  ), (4, ""   )]

>>> stripSuffix m1 m2 == Just m3
True

>>> stripSuffix m2 m1 == Nothing
True

With Sum Natural values:

>>> m1 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
>>> m2 = fromList [("a", 3), ("b", 3), ("c", 3), ("d", 3)]
>>> m3 = fromList [("a", 3), ("b", 2), ("c", 1), ("d", 0)]

>>> stripSuffix m1 m2 == Just m3
True

>>> stripSuffix m2 m1 == Nothing
True

commonSuffix :: (Ord k, MonoidNull v, RightGCDMonoid v) => MonoidMap k v -> MonoidMap k v -> MonoidMap k v

Finds the greatest common suffix of two maps.

Satisfies the following property for all possible keys k:

get k (commonSuffix m1 m2)
    == commonSuffix (get k m1) (get k m2)

This function provides the definition of commonSuffix for the MonoidMap instance of RightGCDMonoid.

Examples

With String values:

>>> m1 = fromList [(1, "+++"), (2, "++b"), (3, "+cc"), (4, "ddd")]
>>> m2 = fromList [(1, "---"), (2, "--b"), (3, "-cc"), (4, "ddd")]
>>> m3 = fromList [(1,    ""), (2,   "b"), (3,  "cc"), (4, "ddd")]

>>> commonSuffix m1 m2 == m3
True

With Sum Natural values:

>>> m1 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3)]
>>> m2 = fromList [("a", 2), ("b", 2), ("c", 2), ("d", 2)]
>>> m3 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 2)]

>>> commonSuffix m1 m2 == m3
True

stripCommonSuffix :: (Ord k, MonoidNull v, RightGCDMonoid v) => MonoidMap k v -> MonoidMap k v -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)

Strips the greatest common suffix from a pair of maps.

Given two maps m1 and m2, stripCommonSuffix produces a tuple (r1, r2, s), where:

• s is the greatest common suffix of m1 and m2
• r1 is the remainder of stripping suffix s from m1
• r2 is the remainder of stripping suffix s from m2

The resulting suffix s can be appended to the right-hand side of either remainder r1 or r2 to reproduce either of the original maps m1 or m2 respectively:

stripCommonSuffix m1 m2
   & \(r1, _, s) -> r1 <> s == m1
stripCommonSuffix m1 m2
   & \(_, r2, s) -> r2 <> s == m2

Suffix s is identical to the result of applying commonSuffix to m1 and m2:

stripCommonSuffix m1 m2
   & \(_, _, s) -> s == commonSuffix m1 m2

Remainders r1 and r2 are identical to the results of applying stripSuffix to s and m1 or to s and m2 respectively:

stripCommonSuffix m1 m2
   & \(r1, _, s) -> Just r1 == stripSuffix s m1
stripCommonSuffix m1 m2
   & \(_, r2, s) -> Just r2 == stripSuffix s m2

This function provides the definition of stripCommonSuffix for the MonoidMap instance of RightGCDMonoid.

Examples

With String values:

>>> m1 = fromList [(1, "+++"), (2, "++a"), (3, "+aa"), (4, "aaa")]
>>> m2 = fromList [(1, "---"), (2, "--a"), (3, "-aa"), (4, "aaa")]

>>> r1 = fromList [(1, "+++"), (2, "++" ), (3, "+"  ), (4, ""   )]
>>> r2 = fromList [(1, "---"), (2, "--" ), (3, "-"  ), (4, ""   )]
>>> s  = fromList [(1,    ""), (2,   "a"), (3,  "aa"), (4, "aaa")]

>>> stripCommonSuffix m1 m2 == (r1, r2, s)
True

With Sum Natural values:

>>> m1 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3), ("e", 4)]
>>> m2 = fromList [("a", 4), ("b", 3), ("c", 2), ("d", 1), ("e", 0)]

>>> r1 = fromList [("a", 0), ("b", 0), ("c", 0), ("d", 2), ("e", 4)]
>>> r2 = fromList [("a", 4), ("b", 2), ("c", 0), ("d", 0), ("e", 0)]
>>> s  = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 1), ("e", 0)]

>>> stripCommonSuffix m1 m2 == (r1, r2, s)
True

Overlap

overlap :: (Ord k, MonoidNull v, OverlappingGCDMonoid v) => MonoidMap k v -> MonoidMap k v -> MonoidMap k v

Finds the greatest overlap of two maps.

The greatest overlap o of maps m1 and m2 is the unique greatest map that is both a suffix of m1 and a prefix of m2:

m1 == r1 <> o   
m2 ==       o <> r2

Where:

• r1 is the remainder obtained by stripping suffix overlap o from m1.

  (see stripSuffixOverlap)

• r2 is the remainder obtained by stripping prefix overlap o from m2.

  (see stripPrefixOverlap)

This function satisfies the following property:

get k (overlap m1 m2) == overlap (get k m1) (get k m2)

This function provides the definition of overlap for the MonoidMap instance of OverlappingGCDMonoid.

Examples

With String values:

>>> m1 = fromList [(1,"abc"   ), (2,"abcd"  ), (3,"abcde "), (4,"abcdef")]
>>> m2 = fromList [(1,   "def"), (2,  "cdef"), (3," bcdef"), (4,"abcdef")]
>>> m3 = fromList [(1,   ""   ), (2,  "cd"  ), (3," bcde" ), (4,"abcdef")]

>>> overlap m1 m2 == m3
True

With Sum Natural values:

>>> m1 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3), ("e", 4)]
>>> m2 = fromList [("a", 4), ("b", 3), ("c", 2), ("d", 1), ("e", 0)]
>>> m3 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 1), ("e", 0)]

>>> overlap m1 m2 == m3
True

stripPrefixOverlap :: (Ord k, MonoidNull v, OverlappingGCDMonoid v) => MonoidMap k v -> MonoidMap k v -> MonoidMap k v

Strips from the second map its greatest prefix overlap with suffixes of the first map.

Evaluating stripPrefixOverlap m1 m2 produces the remainder r2:

m1 == r1 <> o   
m2 ==       o <> r2

Where o is the greatest overlap of maps m1 and m2: the unique greatest map that is both a suffix of m1 and a prefix of m2.

This function satisfies the following property:

get k (stripPrefixOverlap m1 m2)
    == stripPrefixOverlap (get k m1) (get k m2)

This function provides the definition of stripPrefixOverlap for the MonoidMap instance of OverlappingGCDMonoid.

Examples

With String values:

>>> m1 = fromList [(1,"abc"   ), (2,"abcd"  ), (3,"abcde" ), (4,"abcdef")]
>>> m2 = fromList [(1,   "def"), (2,  "cdef"), (3, "bcdef"), (4,"abcdef")]
>>> m3 = fromList [(1,   "def"), (2,    "ef"), (3,     "f"), (4,      "")]

>>> stripPrefixOverlap m1 m2 == m3
True

With Sum Natural values:

>>> m1 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3), ("e", 4)]
>>> m2 = fromList [("a", 4), ("b", 3), ("c", 2), ("d", 1), ("e", 0)]
>>> m3 = fromList [("a", 4), ("b", 2), ("c", 0), ("d", 0), ("e", 0)]

>>> stripPrefixOverlap m1 m2 == m3
True

stripSuffixOverlap :: (Ord k, MonoidNull v, OverlappingGCDMonoid v) => MonoidMap k v -> MonoidMap k v -> MonoidMap k v

Strips from the second map its greatest suffix overlap with prefixes of the first map.

Evaluating stripSuffixOverlap m2 m1 produces the remainder r1:

m1 == r1 <> o   
m2 ==       o <> r2

Where o is the greatest overlap of maps m1 and m2: the unique greatest map that is both a suffix of m1 and a prefix of m2.

This function satisfies the following property:

get k (stripSuffixOverlap m2 m1)
    == stripSuffixOverlap (get k m2) (get k m1)

This function provides the definition of stripSuffixOverlap for the MonoidMap instance of OverlappingGCDMonoid.

Examples

With String values:

>>> m1 = fromList [(1,"abc"   ), (2,"abcd"  ), (3,"abcde" ), (4,"abcdef")]
>>> m2 = fromList [(1,   "def"), (2,  "cdef"), (3, "bcdef"), (4,"abcdef")]
>>> m3 = fromList [(1,"abc"   ), (2,"ab"    ), (3,"a"     ), (4,""      )]

>>> stripSuffixOverlap m2 m1 == m3
True

With Sum Natural values:

>>> m1 = fromList [("a", 0), ("b", 1), ("c", 2), ("d", 3), ("e", 4)]
>>> m2 = fromList [("a", 4), ("b", 3), ("c", 2), ("d", 1), ("e", 0)]
>>> m3 = fromList [("a", 0), ("b", 0), ("c", 0), ("d", 2), ("e", 4)]

>>> stripSuffixOverlap m2 m1 == m3
True

stripOverlap :: (Ord k, MonoidNull v, OverlappingGCDMonoid v) => MonoidMap k v -> MonoidMap k v -> (MonoidMap k v, MonoidMap k v, MonoidMap k v)

Finds the greatest overlap of two maps and strips it from both maps.

Evaluating stripOverlap m1 m2 produces the tuple (r1, o, r2), where:

m1 == r1 <> o   
m2 ==       o <> r2

Where:

• o is the greatest overlap of maps m1 and m2: the unique greatest map that is both a suffix of m1 and a prefix of m2.

  (see overlap)

• r1 is the remainder obtained by stripping suffix overlap o from m1.

  (see stripSuffixOverlap)

• r2 is the remainder obtained by stripping prefix overlap o from m2.

  (see stripPrefixOverlap)

This function satisfies the following property:

stripOverlap m1 m2 ==
   ( stripSuffixOverlap m2 m1
   , overlap m1 m2
   , stripPrefixOverlap m1 m2
   )

This function provides the definition of stripOverlap for the MonoidMap instance of OverlappingGCDMonoid.