Data.Semigroup

The class of semigroups (types with an associative binary operation).

Instances should satisfy the following:

Associativity

x <> (y <> z) = (x <> y) <> z

You can alternatively define sconcat instead of (<>), in which case the laws are:

Unit

sconcat (pure x) = x

Multiplication

sconcat (join xss) = sconcat (fmap sconcat xss)

This is a valid definition of stimes for a Monoid.

Unlike the default definition of stimes, it is defined for 0 and so it should be preferred where possible.

This is a valid definition of stimes for an idempotent Semigroup.

When x <> x = x, this definition should be preferred, because it works in \mathcal{O}(1) rather than \mathcal{O}(\log n).

This is a valid definition of stimes for an idempotent Monoid.

When x <> x = x, this definition should be preferred, because it works in \mathcal{O}(1) rather than \mathcal{O}(\log n)

Repeat a value n times.

mtimesDefault n a = a <> a <> ... <> a  -- using <> (n-1) times

In many cases, stimes 0 a for a Monoid will produce mempty. However, there are situations when it cannot do so. In particular, the following situation is fairly common:

data T a = ...

class Constraint1 a
class Constraint1 a => Constraint2 a

instance Constraint1 a => Semigroup (T a)
instance Constraint2 a => Monoid (T a)

Since Constraint1 is insufficient to implement mempty, stimes for T a cannot do so.

When working with such a type, or when working polymorphically with Semigroup instances, mtimesDefault should be used when the multiplier might be zero. It is implemented using stimes when the multiplier is nonzero and mempty when it is zero.

Examples

>>> mtimesDefault 0 "bark"[]

>>> mtimesDefault 3 "meow""meowmeowmeow"

The Min Monoid and Semigroup always choose the smaller element as by the Ord instance and min of the contained type.

Examples

>>> Min 42 <> Min 3Min 3

>>> sconcat $ Min 1 :| [ Min n | n <- [2 .. 100]]Min {getMin = 1}

The Max Monoid and Semigroup always choose the bigger element as by the Ord instance and max of the contained type.

Examples

>>> Max 42 <> Max 3Max 42

>>> sconcat $ Max 1 :| [ Max n | n <- [2 .. 100]]Max {getMax = 100}

Beware that Data.Semigroup.First is different from Data.Monoid.First. The former simply returns the first value, so Data.Semigroup.First Nothing <> x = Data.Semigroup.First Nothing. The latter returns the first non-Nothing, thus Data.Monoid.First Nothing <> x = x.

Examples

>>> First 0 <> First 10First 0

>>> sconcat $ First 1 :| [ First n | n <- [2 ..] ]First 1

Beware that Data.Semigroup.Last is different from Data.Monoid.Last. The former simply returns the last value, so x <> Data.Semigroup.Last Nothing = Data.Semigroup.Last Nothing. The latter returns the last non-Nothing, thus x <> Data.Monoid.Last Nothing = x.

Examples

>>> Last 0 <> Last 10Last {getLast = 10}

>>> sconcat $ Last 1 :| [ Last n | n <- [2..]]Last {getLast = * hangs forever *

Provide a Semigroup for an arbitrary Monoid.

NOTE: This is not needed anymore since Semigroup became a superclass of Monoid in base-4.11 and this newtype be deprecated at some point in the future.

The dual of a Monoid, obtained by swapping the arguments of (<>).

Dual a <> Dual b == Dual (b <> a)

Examples

>>> Dual "Hello" <> Dual "World"Dual {getDual = "WorldHello"}

>>> Dual (Dual "Hello") <> Dual (Dual "World")Dual {getDual = Dual {getDual = "HelloWorld"}}

The monoid of endomorphisms under composition.

Endo f <> Endo g == Endo (f . g)

Examples

>>> let computation = Endo ("Hello, " ++) <> Endo (++ "!")>>> appEndo computation "Haskell""Hello, Haskell!"

>>> let computation = Endo (*3) <> Endo (+1)>>> appEndo computation 16

Boolean monoid under conjunction (&&).

All x <> All y = All (x && y)

Examples

>>> All True <> mempty <> All False)All {getAll = False}

>>> mconcat (map (\x -> All (even x)) [2,4,6,7,8])All {getAll = False}

>>> All True <> memptyAll {getAll = True}

Boolean monoid under disjunction (||).

Any x <> Any y = Any (x || y)

Examples

>>> Any True <> mempty <> Any FalseAny {getAny = True}

>>> mconcat (map (\x -> Any (even x)) [2,4,6,7,8])Any {getAny = True}

>>> Any False <> memptyAny {getAny = False}

Monoid under addition.

Sum a <> Sum b = Sum (a + b)

Examples

>>> Sum 1 <> Sum 2 <> memptySum {getSum = 3}

>>> mconcat [ Sum n | n <- [3 .. 9]]Sum {getSum = 42}

Monoid under multiplication.

Product x <> Product y == Product (x * y)

Examples

>>> Product 3 <> Product 4 <> memptyProduct {getProduct = 12}

>>> mconcat [ Product n | n <- [2 .. 10]]Product {getProduct = 3628800}

This lets you use a difference list of a Semigroup as a Monoid.

Examples

let hello = diff "Hello, "

>>> appEndo hello "World!""Hello, World!"

>>> appEndo (hello <> mempty) "World!""Hello, World!"

>>> appEndo (mempty <> hello) "World!""Hello, World!"

let world = diff "World"
let excl = diff "!"

>>> appEndo (hello <> (world <> excl)) mempty"Hello, World!"

>>> appEndo ((hello <> world) <> excl) mempty"Hello, World!"

A generalization of cycle to an arbitrary Semigroup. May fail to terminate for some values in some semigroups.

Examples

>>> take 10 $ cycle1 [1, 2, 3][1,2,3,1,2,3,1,2,3,1]

>>> cycle1 (Right 1)Right 1

>>> cycle1 (Left 1)* hangs forever *

Arg isn't itself a Semigroup in its own right, but it can be placed inside Min and Max to compute an arg min or arg max.

Examples

>>> minimum [ Arg (x * x) x | x <- [-10 .. 10] ]Arg 0 0

>>> maximum [ Arg (-0.2*x^2 + 1.5*x + 1) x | x <- [-10 .. 10] ]Arg 3.8 4.0

>>> minimum [ Arg (-0.2*x^2 + 1.5*x + 1) x | x <- [-10 .. 10] ]Arg (-34.0) (-10.0)

Examples

>>> Min (Arg 0 ()) <> Min (Arg 1 ())Min {getMin = Arg 0 ()}

>>> minimum [ Arg (length name) name | name <- ["violencia", "lea", "pixie"]]Arg 3 "lea"

Examples

>>> Max (Arg 0 ()) <> Max (Arg 1 ())Max {getMax = Arg 1 ()}

>>> maximum [ Arg (length name) name | name <- ["violencia", "lea", "pixie"]]Arg 9 "violencia"