| 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
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
overlapa a==a
Identity
overlapmemptya==mempty
overlapamempty==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 #