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

\(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

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

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

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

\(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

\(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

\(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

\(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

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

Satisfies the following property:

get k (set k v m) == 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

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

Satisfies the following property:

get k (nullify k m) == mempty

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

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

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

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

Satisfies the following property:

nonNullCount m == size (nonNullKeys m)

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

\(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

\(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

\(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

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

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

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

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

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

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

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

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

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

\(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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>> negate m1 == m2
True

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

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

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

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

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

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

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

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

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

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

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

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

An applicative version of intersectionWith.

Satisfies the following property:

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

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

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

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

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

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

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

An applicative version of unionWith.

Satisfies the following property:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.