Data.Monoid.Monus

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

Since: 1.0

Documentation

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

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

Since: 1.0

Methods

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

Instances

Monus ()

O(1)

Defined in Data.Monoid.Monus

Methods

(<\>) :: () -> () -> ()

Monus IntSet

O(m+n)

Defined in Data.Monoid.Monus

Methods

(<\>) :: IntSet -> IntSet -> IntSet

(Monus a, MonoidNull a) => Monus (Maybe a)

Defined in Data.Monoid.Monus

Methods

(<\>) :: Maybe a -> Maybe a -> Maybe a

Monus a => Monus (Dual a)

Defined in Data.Monoid.Monus

Methods

(<\>) :: Dual a -> Dual a -> Dual a

Monus (Sum Natural)

O(1)

Defined in Data.Monoid.Monus

Methods

(<\>) :: Sum Natural -> Sum Natural -> Sum Natural

Monus (Product Natural)

O(1)

Defined in Data.Monoid.Monus

Methods

(<\>) :: Product Natural -> Product Natural -> Product Natural

Ord a => Monus (Set a)

O(m*log(nm + 1)), m <= n/

Defined in Data.Monoid.Monus

Methods

(<\>) :: Set a -> Set a -> Set a

(Monus a, Monus b) => Monus (a, b)

Defined in Data.Monoid.Monus

Methods

(<\>) :: (a, b) -> (a, b) -> (a, b)

(Monus a, Monus b, Monus c) => Monus (a, b, c)

Defined in Data.Monoid.Monus

Methods

(<\>) :: (a, b, c) -> (a, b, c) -> (a, b, c)

(Monus a, Monus b, Monus c, Monus d) => Monus (a, b, c, d)

Defined in Data.Monoid.Monus

Methods

(<\>) :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d)

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

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 is contained in any other value x that satifies the property (x isPrefixOf b) && (x isSuffixOf a):

(x `isPrefixOf` overlap a b) && (x `isSuffixOf` overlap a b)

and it must be unique so it's not contained in any other value y that satisfies the same property (y isPrefixOf b) && (y isSuffixOf a):

not ((y `isPrefixOf` overlap a b) && (y `isSuffixOf` overlap a b) && y /= overlap a b)

Since: 1.0

Minimal complete definition

stripOverlap

Methods

stripPrefixOverlap :: m -> m -> m

stripSuffixOverlap :: m -> m -> m

overlap :: m -> m -> m

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

Instances

OverlappingGCDMonoid ()

O(1)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: () -> () -> ()

stripSuffixOverlap :: () -> () -> ()

overlap :: () -> () -> ()

stripOverlap :: () -> () -> ((), (), ())

OverlappingGCDMonoid ByteString

O(m*n)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: ByteString -> ByteString -> ByteString

stripSuffixOverlap :: ByteString -> ByteString -> ByteString

overlap :: ByteString -> ByteString -> ByteString

stripOverlap :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)

OverlappingGCDMonoid ByteString

O(min(m,n)^2)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: ByteString -> ByteString -> ByteString

stripSuffixOverlap :: ByteString -> ByteString -> ByteString

overlap :: ByteString -> ByteString -> ByteString

stripOverlap :: ByteString -> ByteString -> (ByteString, ByteString, ByteString)

OverlappingGCDMonoid IntSet

O(m+n)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: IntSet -> IntSet -> IntSet

stripSuffixOverlap :: IntSet -> IntSet -> IntSet

overlap :: IntSet -> IntSet -> IntSet

stripOverlap :: IntSet -> IntSet -> (IntSet, IntSet, IntSet)

OverlappingGCDMonoid Text

O(m*n)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Text -> Text -> Text

stripSuffixOverlap :: Text -> Text -> Text

overlap :: Text -> Text -> Text

stripOverlap :: Text -> Text -> (Text, Text, Text)

OverlappingGCDMonoid Text

O(min(m,n)^2)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Text -> Text -> Text

stripSuffixOverlap :: Text -> Text -> Text

overlap :: Text -> Text -> Text

stripOverlap :: Text -> Text -> (Text, Text, Text)

Eq a => OverlappingGCDMonoid [a]

O(m*n)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: [a] -> [a] -> [a]

stripSuffixOverlap :: [a] -> [a] -> [a]

overlap :: [a] -> [a] -> [a]

stripOverlap :: [a] -> [a] -> ([a], [a], [a])

(OverlappingGCDMonoid a, MonoidNull a) => OverlappingGCDMonoid (Maybe a)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Maybe a -> Maybe a -> Maybe a

stripSuffixOverlap :: Maybe a -> Maybe a -> Maybe a

overlap :: Maybe a -> Maybe a -> Maybe a

stripOverlap :: Maybe a -> Maybe a -> (Maybe a, Maybe a, Maybe a)

OverlappingGCDMonoid a => OverlappingGCDMonoid (Dual a)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Dual a -> Dual a -> Dual a

stripSuffixOverlap :: Dual a -> Dual a -> Dual a

overlap :: Dual a -> Dual a -> Dual a

stripOverlap :: Dual a -> Dual a -> (Dual a, Dual a, Dual a)

OverlappingGCDMonoid (Sum Natural)

O(1)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Sum Natural -> Sum Natural -> Sum Natural

stripSuffixOverlap :: Sum Natural -> Sum Natural -> Sum Natural

overlap :: Sum Natural -> Sum Natural -> Sum Natural

stripOverlap :: Sum Natural -> Sum Natural -> (Sum Natural, Sum Natural, Sum Natural)

OverlappingGCDMonoid (Product Natural)

O(1)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Product Natural -> Product Natural -> Product Natural

stripSuffixOverlap :: Product Natural -> Product Natural -> Product Natural

overlap :: Product Natural -> Product Natural -> Product Natural

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

Eq a => OverlappingGCDMonoid (IntMap a)

O(m+n)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: IntMap a -> IntMap a -> IntMap a

stripSuffixOverlap :: IntMap a -> IntMap a -> IntMap a

overlap :: IntMap a -> IntMap a -> IntMap a

stripOverlap :: IntMap a -> IntMap a -> (IntMap a, IntMap a, IntMap a)

Eq a => OverlappingGCDMonoid (Seq a)

O(min(m,n)^2)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Seq a -> Seq a -> Seq a

stripSuffixOverlap :: Seq a -> Seq a -> Seq a

overlap :: Seq a -> Seq a -> Seq a

stripOverlap :: Seq a -> Seq a -> (Seq a, Seq a, Seq a)

Ord a => OverlappingGCDMonoid (Set a)

O(m*log(nm + 1)), m <= n/

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Set a -> Set a -> Set a

stripSuffixOverlap :: Set a -> Set a -> Set a

overlap :: Set a -> Set a -> Set a

stripOverlap :: Set a -> Set a -> (Set a, Set a, Set a)

Eq a => OverlappingGCDMonoid (Vector a)

O(min(m,n)^2)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Vector a -> Vector a -> Vector a

stripSuffixOverlap :: Vector a -> Vector a -> Vector a

overlap :: Vector a -> Vector a -> Vector a

stripOverlap :: Vector a -> Vector a -> (Vector a, Vector a, Vector a)

(OverlappingGCDMonoid a, OverlappingGCDMonoid b) => OverlappingGCDMonoid (a, b)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: (a, b) -> (a, b) -> (a, b)

stripSuffixOverlap :: (a, b) -> (a, b) -> (a, b)

overlap :: (a, b) -> (a, b) -> (a, b)

stripOverlap :: (a, b) -> (a, b) -> ((a, b), (a, b), (a, b))

(Ord k, Eq v) => OverlappingGCDMonoid (Map k v)

O(m+n)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: Map k v -> Map k v -> Map k v

stripSuffixOverlap :: Map k v -> Map k v -> Map k v

overlap :: Map k v -> Map k v -> Map k v

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

(OverlappingGCDMonoid a, OverlappingGCDMonoid b, OverlappingGCDMonoid c) => OverlappingGCDMonoid (a, b, c)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: (a, b, c) -> (a, b, c) -> (a, b, c)

stripSuffixOverlap :: (a, b, c) -> (a, b, c) -> (a, b, c)

overlap :: (a, b, c) -> (a, b, c) -> (a, b, c)

stripOverlap :: (a, b, c) -> (a, b, c) -> ((a, b, c), (a, b, c), (a, b, c))

(OverlappingGCDMonoid a, OverlappingGCDMonoid b, OverlappingGCDMonoid c, OverlappingGCDMonoid d) => OverlappingGCDMonoid (a, b, c, d)

Defined in Data.Monoid.Monus

Methods

stripPrefixOverlap :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d)

stripSuffixOverlap :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d)

overlap :: (a, b, c, d) -> (a, b, c, d) -> (a, b, c, d)

stripOverlap :: (a, b, c, d) -> (a, b, c, d) -> ((a, b, c, d), (a, b, c, d), (a, b, c, d))