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