Data.Monoid.LCM

This module defines the LCMMonoid subclass of the Monoid class.

The LCMMonoid subclass adds the lcm operation, which takes two monoidal arguments and finds their least common multiple, or (more generally) the least monoid from which either argument can be subtracted with the </> operation.

For LCM monoids that are distributive, this module also provides the DistributiveLCMMonoid subclass of LCMMonoid.

All classes in this module are for Abelian, i.e., Commutative monoids.

Documentation

class GCDMonoid m => LCMMonoid m where

Class of Abelian monoids that allow the least common multiple to be found for any two given values.

Operations must satisfy the following laws:

Reductivity

isJust (lcm a b </> a)

isJust (lcm a b </> b)

Uniqueness

all isJust
    [       c </> a
    ,       c </> b
    , lcm a b </> c
    ]
==>
    (lcm a b == c)

Idempotence

lcm a a == a

Identity

lcm mempty a == a

lcm a mempty == a

Commutativity

lcm a b == lcm b a

Associativity

lcm (lcm a b) c == lcm a (lcm b c)

Absorption

lcm a (gcd a b) == a

gcd a (lcm a b) == a

Methods

lcm :: m -> m -> m

Instances

LCMMonoid IntSet

Defined in Data.Monoid.LCM

Methods

lcm :: IntSet -> IntSet -> IntSet

LCMMonoid ()

Defined in Data.Monoid.LCM

Methods

lcm :: () -> () -> ()

LCMMonoid a => LCMMonoid (Dual a)

Defined in Data.Monoid.LCM

Methods

lcm :: Dual a -> Dual a -> Dual a

LCMMonoid (Product Natural)

Defined in Data.Monoid.LCM

Methods

lcm :: Product Natural -> Product Natural -> Product Natural

LCMMonoid (Sum Natural)

Defined in Data.Monoid.LCM

Methods

lcm :: Sum Natural -> Sum Natural -> Sum Natural

Ord a => LCMMonoid (Set a)

Defined in Data.Monoid.LCM

Methods

lcm :: Set a -> Set a -> Set a

(LCMMonoid a, LCMMonoid b) => LCMMonoid (a, b)

Defined in Data.Monoid.LCM

Methods

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

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

Defined in Data.Monoid.LCM

Methods

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

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

Defined in Data.Monoid.LCM

Methods

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

class (DistributiveGCDMonoid m, LCMMonoid m) => DistributiveLCMMonoid m

Class of commutative LCM monoids with distributivity.

In addition to the general LCMMonoid laws, instances of this class must also satisfy the following laws:

The lcm operation itself must be both left-distributive and right-distributive:

lcm (a <> b) (a <> c) == a <> lcm b c

lcm (a <> c) (b <> c) == lcm a b <> c

The lcm and gcd operations must distribute over one another:

lcm a (gcd b c) == gcd (lcm a b) (lcm a c)

gcd a (lcm b c) == lcm (gcd a b) (gcd a c)

Instances

DistributiveLCMMonoid IntSet

Defined in Data.Monoid.LCM

DistributiveLCMMonoid ()

Defined in Data.Monoid.LCM

DistributiveLCMMonoid a => DistributiveLCMMonoid (Dual a)

Defined in Data.Monoid.LCM

DistributiveLCMMonoid (Product Natural)

Defined in Data.Monoid.LCM

DistributiveLCMMonoid (Sum Natural)

Defined in Data.Monoid.LCM

Ord a => DistributiveLCMMonoid (Set a)

Defined in Data.Monoid.LCM