monoid-subclasses-1.2.6: Subclasses of Monoid

Safe Haskell | Trustworthy
Language | Haskell2010

Data.Monoid.Monus

Description

This module defines the `OverlappingGCDMonoid` => `Monus` subclass of the `Monoid` class.

Since: 1.0

Synopsis

- class (Commutative m, Monoid m, OverlappingGCDMonoid m) => Monus m where
  - (<\>) :: m -> m -> m
- class (Monoid m, LeftReductive m, RightReductive m) => OverlappingGCDMonoid m where
  - stripPrefixOverlap :: m -> m -> m
  - stripSuffixOverlap :: m -> m -> m
  - overlap :: m -> m -> m
  - stripOverlap :: m -> m -> (m, m, m)

# Documentation

class (Commutative m, Monoid m, OverlappingGCDMonoid m) => Monus m where Source #

Class of Abelian monoids with monus.

The monus operation `<\>` is a synonym for both `stripPrefixOverlap` and `stripSuffixOverlap`, which must be equivalent as `<>` is both associative and commutative:

    (<\>) = flip stripPrefixOverlap
    (<\>) = flip stripSuffixOverlap

In addition, the monus operation `<\>` must satisfy the following laws:

    a <\> a == mempty

    mempty <\> a == mempty

    a <> (b <\> a) == b <> (a <\> b)

    (a <\> b) <\> c == a <\> (b <> c)

Since: 1.0

Methods

(<\>) :: m -> m -> m infix 5 Source #

#### Instances

Instances details

Monus IntSet Source # | O(m+n)
Instance details Defined in Data.Monoid.Monus Methods (<\>) :: IntSet -> IntSet -> IntSet Source #
Monus () Source # | O(1)
Instance details Defined in Data.Monoid.Monus Methods (<\>) :: () -> () -> () Source #
Ord a => Monus (Set a) Source # | O(m*log(nm + 1)), m <= n/
Instance details Defined in Data.Monoid.Monus Methods (<\>) :: Set a -> Set a -> Set a Source #
Monus a => Monus (Identity a) Source # |
Instance details Defined in Data.Monoid.Monus Methods (<\>) :: Identity a -> Identity a -> Identity a Source #
Monus a => Monus (Dual a) Source # |
Instance details Defined in Data.Monoid.Monus Methods (<\>) :: Dual a -> Dual a -> Dual a Source #
Monus (Product Natural) Source # | O(1)
Instance details Defined in Data.Monoid.Monus Methods (<\>) :: Product Natural -> Product Natural -> Product Natural Source #
Monus (Sum Natural) Source # | O(1)
Instance details Defined in Data.Monoid.Monus Methods (<\>) :: Sum Natural -> Sum Natural -> Sum Natural Source #
(Monus a, MonoidNull a) => Monus (Maybe a) Source # |
Instance details Defined in Data.Monoid.Monus Methods (<\>) :: Maybe a -> Maybe a -> Maybe a Source #
(Monus a, Monus b) => Monus (a, b) Source # |
Instance details Defined in Data.Monoid.Monus Methods (<\>) :: (a, b) -> (a, b) -> (a, b) Source #
Monus a => Monus (Const a b) Source # |
Instance details Defined in Data.Monoid.Monus Methods (<\>) :: Const a b -> Const a b -> Const a b Source #
(Monus a, Monus b, Monus c) => Monus (a, b, c) Source # |
Instance details Defined in Data.Monoid.Monus Methods (<\>) :: (a, b, c) -> (a, b, c) -> (a, b, c) Source #
(Monus a, Monus b, Monus c, Monus d) => Monus (a, b, c, d) Source # |
Instance details Defined in Data.Monoid.Monus Methods (<\>) :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d) Source #

class (Monoid m, LeftReductive m, RightReductive m) => OverlappingGCDMonoid m where Source #

Class of monoids for which the greatest overlap can be found between any two values, such that

    a == a' <> overlap a b
    b == overlap a b <> b'

The methods must satisfy the following laws:

    stripOverlap a b == (stripSuffixOverlap b a, overlap a b, stripPrefixOverlap a b)
    stripSuffixOverlap b a <> overlap a b == a
    overlap a b <> stripPrefixOverlap a b == b

The result of `overlap a b` must be the largest prefix of `b` and suffix of `a`, in the sense that it contains any other value `x` that satifies the property `(x `isPrefixOf` b) && (x `isSuffixOf` a)`:

    ∀x. (x `isPrefixOf` b && x `isSuffixOf` a) => (x `isPrefixOf` overlap a b && x `isSuffixOf` overlap a b)

and it must be unique so there's no other value `y` that satisfies the same properties for every such `x`:

    ∀y. ((∀x. (x `isPrefixOf` b && x `isSuffixOf` a) => x `isPrefixOf` y && x `isSuffixOf` y) => y == overlap a b)

In addition, the `overlap` operation must satisfy the following properties:

Idempotence

    overlap a a == a

Identity

    overlap mempty a == mempty

    overlap a mempty == mempty

Since: 1.0

Minimal complete definition

stripOverlap

Methods

stripPrefixOverlap :: m -> m -> m Source #

stripSuffixOverlap :: m -> m -> m Source #

overlap :: m -> m -> m Source #

stripOverlap :: m -> m -> (m, m, m) Source #

#### Instances

Instances details

OverlappingGCDMonoid ByteString Source # | O(min(m,n)^2)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: ByteString -> ByteString -> ByteString Source # stripSuffixOverlap :: ByteString -> ByteString -> ByteString Source # overlap :: ByteString -> ByteString -> ByteString Source # stripOverlap :: ByteString -> ByteString -> (ByteString, ByteString, ByteString) Source #
OverlappingGCDMonoid ByteString Source # | O(m*n)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: ByteString -> ByteString -> ByteString Source # stripSuffixOverlap :: ByteString -> ByteString -> ByteString Source # overlap :: ByteString -> ByteString -> ByteString Source # stripOverlap :: ByteString -> ByteString -> (ByteString, ByteString, ByteString) Source #
OverlappingGCDMonoid IntSet Source # | O(m+n)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: IntSet -> IntSet -> IntSet Source # stripSuffixOverlap :: IntSet -> IntSet -> IntSet Source # overlap :: IntSet -> IntSet -> IntSet Source # stripOverlap :: IntSet -> IntSet -> (IntSet, IntSet, IntSet) Source #
OverlappingGCDMonoid Text Source # | O(min(m,n)^2)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Text -> Text -> Text Source # stripSuffixOverlap :: Text -> Text -> Text Source # overlap :: Text -> Text -> Text Source # stripOverlap :: Text -> Text -> (Text, Text, Text) Source #
OverlappingGCDMonoid Text Source # | O(m*n)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Text -> Text -> Text Source # stripSuffixOverlap :: Text -> Text -> Text Source # overlap :: Text -> Text -> Text Source # stripOverlap :: Text -> Text -> (Text, Text, Text) Source #
OverlappingGCDMonoid () Source # | O(1)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: () -> () -> () Source # stripSuffixOverlap :: () -> () -> () Source # overlap :: () -> () -> () Source # stripOverlap :: () -> () -> ((), (), ()) Source #
Eq a => OverlappingGCDMonoid (IntMap a) Source # | O(m+n)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: IntMap a -> IntMap a -> IntMap a Source # stripSuffixOverlap :: IntMap a -> IntMap a -> IntMap a Source # overlap :: IntMap a -> IntMap a -> IntMap a Source # stripOverlap :: IntMap a -> IntMap a -> (IntMap a, IntMap a, IntMap a) Source #
Eq a => OverlappingGCDMonoid (Seq a) Source # | O(min(m,n)^2)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Seq a -> Seq a -> Seq a Source # stripSuffixOverlap :: Seq a -> Seq a -> Seq a Source # overlap :: Seq a -> Seq a -> Seq a Source # stripOverlap :: Seq a -> Seq a -> (Seq a, Seq a, Seq a) Source #
Ord a => OverlappingGCDMonoid (Set a) Source # | O(m*log(nm + 1)), m <= n/
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Set a -> Set a -> Set a Source # stripSuffixOverlap :: Set a -> Set a -> Set a Source # overlap :: Set a -> Set a -> Set a Source # stripOverlap :: Set a -> Set a -> (Set a, Set a, Set a) Source #
OverlappingGCDMonoid a => OverlappingGCDMonoid (Identity a) Source # |
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Identity a -> Identity a -> Identity a Source # stripSuffixOverlap :: Identity a -> Identity a -> Identity a Source # overlap :: Identity a -> Identity a -> Identity a Source # stripOverlap :: Identity a -> Identity a -> (Identity a, Identity a, Identity a) Source #
OverlappingGCDMonoid a => OverlappingGCDMonoid (Dual a) Source # |
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Dual a -> Dual a -> Dual a Source # stripSuffixOverlap :: Dual a -> Dual a -> Dual a Source # overlap :: Dual a -> Dual a -> Dual a Source # stripOverlap :: Dual a -> Dual a -> (Dual a, Dual a, Dual a) Source #
OverlappingGCDMonoid (Product Natural) Source # | O(1)

Instance details

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Product Natural -> Product Natural -> Product Natural Source #

stripSuffixOverlap :: Product Natural -> Product Natural -> Product Natural Source #

overlap :: Product Natural -> Product Natural -> Product Natural Source #

stripOverlap :: Product Natural -> Product Natural -> (Product Natural, Product Natural, Product Natural) Source #

OverlappingGCDMonoid (Sum Natural) Source # | O(1)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Sum Natural -> Sum Natural -> Sum Natural Source # stripSuffixOverlap :: Sum Natural -> Sum Natural -> Sum Natural Source # overlap :: Sum Natural -> Sum Natural -> Sum Natural Source # stripOverlap :: Sum Natural -> Sum Natural -> (Sum Natural, Sum Natural, Sum Natural) Source #
Eq a => OverlappingGCDMonoid (Vector a) Source # | O(min(m,n)^2)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Vector a -> Vector a -> Vector a Source # stripSuffixOverlap :: Vector a -> Vector a -> Vector a Source # overlap :: Vector a -> Vector a -> Vector a Source # stripOverlap :: Vector a -> Vector a -> (Vector a, Vector a, Vector a) Source #
(OverlappingGCDMonoid a, MonoidNull a) => OverlappingGCDMonoid (Maybe a) Source # |
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Maybe a -> Maybe a -> Maybe a Source # stripSuffixOverlap :: Maybe a -> Maybe a -> Maybe a Source # overlap :: Maybe a -> Maybe a -> Maybe a Source # stripOverlap :: Maybe a -> Maybe a -> (Maybe a, Maybe a, Maybe a) Source #
Eq a => OverlappingGCDMonoid [a] Source # | O(m*n)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: [a] -> [a] -> [a] Source # stripSuffixOverlap :: [a] -> [a] -> [a] Source # overlap :: [a] -> [a] -> [a] Source # stripOverlap :: [a] -> [a] -> ([a], [a], [a]) Source #
(Ord k, Eq v) => OverlappingGCDMonoid (Map k v) Source # | O(m+n)
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Map k v -> Map k v -> Map k v Source # stripSuffixOverlap :: Map k v -> Map k v -> Map k v Source # overlap :: Map k v -> Map k v -> Map k v Source # stripOverlap :: Map k v -> Map k v -> (Map k v, Map k v, Map k v) Source #
(OverlappingGCDMonoid a, OverlappingGCDMonoid b) => OverlappingGCDMonoid (a, b) Source # |
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: (a, b) -> (a, b) -> (a, b) Source # stripSuffixOverlap :: (a, b) -> (a, b) -> (a, b) Source # overlap :: (a, b) -> (a, b) -> (a, b) Source # stripOverlap :: (a, b) -> (a, b) -> ((a, b), (a, b), (a, b)) Source #
OverlappingGCDMonoid a => OverlappingGCDMonoid (Const a b) Source # |
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: Const a b -> Const a b -> Const a b Source # stripSuffixOverlap :: Const a b -> Const a b -> Const a b Source # overlap :: Const a b -> Const a b -> Const a b Source # stripOverlap :: Const a b -> Const a b -> (Const a b, Const a b, Const a b) Source #
(OverlappingGCDMonoid a, OverlappingGCDMonoid b, OverlappingGCDMonoid c) => OverlappingGCDMonoid (a, b, c) Source # |
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: (a, b, c) -> (a, b, c) -> (a, b, c) Source # stripSuffixOverlap :: (a, b, c) -> (a, b, c) -> (a, b, c) Source # overlap :: (a, b, c) -> (a, b, c) -> (a, b, c) Source # stripOverlap :: (a, b, c) -> (a, b, c) -> ((a, b, c), (a, b, c), (a, b, c)) Source #
(OverlappingGCDMonoid a, OverlappingGCDMonoid b, OverlappingGCDMonoid c, OverlappingGCDMonoid d) => OverlappingGCDMonoid (a, b, c, d) Source # |
Instance details Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d) Source # stripSuffixOverlap :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d) Source # overlap :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d) Source # stripOverlap :: (a, b, c, d) -> (a, b, c, d) -> ((a, b, c, d), (a, b, c, d), (a, b, c, d)) Source #