difference-monoid-0.1.0.0

Copyright (c) Donnacha Oisín Kidney 2018 MIT mail@doisinkidney.com experimental GHC None Haskell2010

Data.Monoid.Diff

Description

This module provides the Difference Monoid, which adds subtraction to arbitrary monoids.

This has a number of uses:

• Diff (Product a) will give you a type similar to Ratio. Here, the "subtraction" operation is division. For example:

>>> (1 :-: 2) <> (3 :-: 4) :: Diff (Product Int)
Product {getProduct = 3} :-: Product {getProduct = 8}

• In a similar vein, Diff (Sum a) will add subtraction to a numeric type:

>>> runDiff (-) (diff 2 <> diff 3 <> invert (diff 4)) :: Sum Natural
Sum {getSum = 1}


This will let you work with nonnegative types, where you need some form of subtraction (for, e.g., differences, hence the name), and you only want to check for underflow once.

• Using the above example, in particular, we get a monoid for averages:

>>> import Data.Function (on)
>>> let avg = runDiff ((%) on getProduct.getSum) . foldMap (fmap Sum . diff . Product)
>>> avg [1,4,3,2,5]
3 % 1


The Monoid and Semigroup laws hold in a pretty straightforward way, provided the underlying type also follows those laws.

For the Group laws, the underlying type must be a cancellative semigroup.

A cancellative semigroup is one where

• a <> b = a <> c implies b = c
• b <> a = c <> a implies b = c

If this does not hold, than the equivalence only holds modulo the the addition of some constant

Most common semigroups are cancellative, however notable exceptions include the cross product of vectors, matrix multiplication, and sets:

fromList [1] <> fromList [1,2] = fromList [1] <> fromList [2]

This type is known formally as the Grothendieck group.

Synopsis

# The Diff Type

data Diff a Source #

The Difference Monoid.

Constructors

 !a :-: !a infixl 6

Instances

# Functions for working with Diff

diff :: Monoid a => a -> Diff a Source #

Lift a monoid into the difference monoid.

>>> diff (Sum 1)
Sum {getSum = 1} :-: Sum {getSum = 0}


retract :: Group a => Diff a -> a Source #

The inverse of diff.

retract . diff = id

foldDiff :: Group b => (a -> b) -> Diff a -> b Source #

A group homomorphism given a monoid homomorphism.

runDiff :: (a -> a -> b) -> Diff a -> b Source #

Interpret the difference using a subtraction function.

normalize :: (a -> a -> (a, a)) -> Diff a -> Diff a Source #

Given a "normalizing" function, try simplify the representation.

For instance, one such normalizing function may be to take the numeric difference of two types:

>>> let sumNorm x y = if x >= y then (x - y, 0) else (0, y - x)
>>> normalize sumNorm ((foldMap (diff.Sum) [1..10]) <> (invert (foldMap (diff.Sum) [1..5])))
Sum {getSum = 40} :-: Sum {getSum = 0}


# Re-Exports from Group

class Monoid m => Group m where #

A Group is a Monoid plus a function, invert, such that:

a <> invert a == mempty
invert a <> a == mempty

Minimal complete definition

invert

Methods

invert :: m -> m #

pow :: Integral x => m -> x -> m #

pow a n == a <> a <> ... <> a
 (n lots of a)

If n is negative, the result is inverted.

Instances

 Group () Methodsinvert :: () -> () #pow :: Integral x => () -> x -> () # # Methodsinvert :: Odd -> Odd #pow :: Integral x => Odd -> x -> Odd # Group a => Group (Dual a) Methodsinvert :: Dual a -> Dual a #pow :: Integral x => Dual a -> x -> Dual a # Num a => Group (Sum a) Methodsinvert :: Sum a -> Sum a #pow :: Integral x => Sum a -> x -> Sum a # Fractional a => Group (Product a) Methodsinvert :: Product a -> Product a #pow :: Integral x => Product a -> x -> Product a # Monoid a => Group (Diff a) # Methodsinvert :: Diff a -> Diff a #pow :: Integral x => Diff a -> x -> Diff a # Group b => Group (a -> b) Methodsinvert :: (a -> b) -> a -> b #pow :: Integral x => (a -> b) -> x -> a -> b # (Group a, Group b) => Group (a, b) Methodsinvert :: (a, b) -> (a, b) #pow :: Integral x => (a, b) -> x -> (a, b) # (Group a, Group b, Group c) => Group (a, b, c) Methodsinvert :: (a, b, c) -> (a, b, c) #pow :: Integral x => (a, b, c) -> x -> (a, b, c) # (Group a, Group b, Group c, Group d) => Group (a, b, c, d) Methodsinvert :: (a, b, c, d) -> (a, b, c, d) #pow :: Integral x => (a, b, c, d) -> x -> (a, b, c, d) # (Group a, Group b, Group c, Group d, Group e) => Group (a, b, c, d, e) Methodsinvert :: (a, b, c, d, e) -> (a, b, c, d, e) #pow :: Integral x => (a, b, c, d, e) -> x -> (a, b, c, d, e) #