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
Instances
Monus IntSet Source # | O(m+n) |
Defined in Data.Monoid.Monus | |
Monus () Source # | O(1) |
Defined in Data.Monoid.Monus | |
Ord a => Monus (Set a) Source # | O(m*log(nm + 1)), m <= n/ |
Defined in Data.Monoid.Monus | |
Monus a => Monus (Identity a) Source # | |
Defined in Data.Monoid.Monus | |
Monus a => Monus (Dual a) Source # | |
Defined in Data.Monoid.Monus | |
Monus (Product Natural) Source # | O(1) |
Defined in Data.Monoid.Monus | |
Monus (Sum Natural) Source # | O(1) |
Defined in Data.Monoid.Monus | |
(Monus a, MonoidNull a) => Monus (Maybe a) Source # | |
Defined in Data.Monoid.Monus | |
(Monus a, Monus b) => Monus (a, b) Source # | |
Defined in Data.Monoid.Monus | |
Monus a => Monus (Const a b) Source # | |
Defined in Data.Monoid.Monus | |
(Monus a, Monus b, Monus c) => Monus (a, b, c) Source # | |
Defined in Data.Monoid.Monus | |
(Monus a, Monus b, Monus c, Monus d) => Monus (a, b, c, d) Source # | |
Defined in Data.Monoid.Monus |
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
amempty
==
mempty
Since: 1.0
Minimal complete definition
Methods
stripPrefixOverlap :: m -> m -> m Source #
stripSuffixOverlap :: m -> m -> m Source #
overlap :: m -> m -> m Source #
stripOverlap :: m -> m -> (m, m, m) Source #
Instances
OverlappingGCDMonoid ByteString Source # | O(min(m,n)^2) |
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) |
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) |
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) |
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) |
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) |
Defined in Data.Monoid.Monus Methods stripPrefixOverlap :: () -> () -> () Source # stripSuffixOverlap :: () -> () -> () Source # overlap :: () -> () -> () Source # stripOverlap :: () -> () -> ((), (), ()) Source # | |
Eq a => OverlappingGCDMonoid (IntMap a) Source # | O(m+n) |
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) |
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/ |
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 # | |
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 # | |
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) |
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) |
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) |
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 # | |
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) |
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) |
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 # | |
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 # | |
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 # | |
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 # | |
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 # |