Safe Haskell | Trustworthy |
---|---|
Language | Haskell2010 |
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
Since: 1.0
Instances
Monus () Source # | O(1) |
Defined in Data.Monoid.Monus | |
Monus IntSet Source # | O(m+n) |
(Monus a, MonoidNull a) => Monus (Maybe a) Source # | |
Monus a => Monus (Dual a) Source # | |
Monus (Sum Natural) Source # | O(1) |
Monus (Product Natural) Source # | O(1) |
Ord a => Monus (Set a) Source # | O(m*log(nm + 1)), m <= n/ |
(Monus a, Monus b) => Monus (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 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
stripPrefixOverlap :: m -> m -> m Source #
stripSuffixOverlap :: m -> m -> m Source #
overlap :: m -> m -> m Source #
stripOverlap :: m -> m -> (m, m, m) Source #