Monoid

Types with an associative binary operation that has an identity.

Minimal complete definition

zero`
(+) x y/(++) x y

static member get_Zero () :'Monoid
static member (+) (x:'Monoid, y:'Monoid) :'Monoid

Other operations

Seq.sum

static member Sum (x:Seq<'Monoid>) :'Monoid

Rules

zero + x = x
x + zero = x
(x + y) + z = x + (y + z)
Seq.sum = Seq.fold (+) zero
sum = fold (+) zero (generic to all foldables)

Related Abstractions

Semigroup: A monoid is a Semigroup with an additional zero operation
Alternative / MonadPlus: Applicatives/Monads that are also Monoids. Though their monoidal definition could be different.

Concrete implementations

From .Net/F#

list<'T>
option<'T>
array<'T>
string
StringBuilder
unit
Set<'T>
Map<'T,'Monoid>
TimeSpan
Tuple<'Monoid1* ... *'MonoidN>
'Monoid1* ... *'MonoidN
Task<'T>
ValueTask<'T>
'T->'Monoid
Async<'T>
Expr<'T>
Lazy<'T>
Dictionary<'T,'Monoid>
IDictionary<'T,'Monoid>
IReadOnlyDictionary<'T,'Monoid>
ResizeArray<'T>
seq<'T>
IEnumerator<'T>

From F#+

Suggest another concrete implementation

Examples

#r @"nuget: FSharpPlus"

open FSharpPlus
open FSharpPlus.Math.Generic
open FSharpPlus.Data


/// A monoid that represents results of comparisons
type Ordering = LT|EQ|GT with
    static member        Zero = EQ
    static member        (+) (x:Ordering, y) = 
        match x, y with
        | LT, _ -> LT
        | EQ, a -> a
        | GT, _ -> GT

let inline compare' x y =
    match compare x y with
    | a when a > 0 -> GT
    | a when a < 0 -> LT
    | _            -> EQ

let resGreater = compare' 7 6

/// A monoid of all numbers from 0 to 4
type Mod5 = Mod5 of uint32 with
    static member inline get_Zero() = Mod5 0u
    static member inline (+) (Mod5 x, Mod5 y) = Mod5 ( (x + y) % 5u)
let Mod5 x = Mod5 (x % 5u)


// Results of Monoid operations
let emptyLst:list<int> = zero
let zeroUint:Mod5   = zero
let res1 = zero ++ Mod5 11u
let res2  = sum <| map Mod5 [4u; 2u; 1u]
let res3  = sum [zero; Mod5 2G; Mod5 6G]
let res8n4 = [zero; [8;4]]
let res15 = Mult 15 ++ zero
let resTrue = sum [zero; Any true]
let resFalse = sum (map All [true;false])
let resHi = zero ++ "Hi"
let resGT = zero ++  GT
let resLT = sum [zero; LT ; EQ ;GT]
let res9823 = sum (map Dual [zero;"3";"2";"8";"9"])
let resBA = Dual "A" ++ Dual "B" 
let resEl00:list<int>*float = zero
let resS3P20     = (1G, Mult 5.0) ++  (2, Mult 4G)
let res230       = (zero,zero) ++ ([2],[3.0])
let res243       = ([2;4],[3]) ++ zero
let res23        = zero ++ ([2],"3")
let resLtDualGt  =  (LT,Dual GT) ++ zero
let res230hiSum2 = (zero, zero, 2) ++ ([2], ([3.0], "hi"), zero)
let res230hiS4P3 = (zero, zero   ) ++ ([2], ([3.0], "hi", 4, Mult (6 % 2)))
let tuple5 :string*(Any*string)*(All*All*All)*int*string = zero

module Seq from Microsoft.FSharp.Collections

val sum: source: 'T seq -> 'T (requires member (+) and member Zero)

val fold<'T,'State> : folder: ('State -> 'T -> 'State) -> state: 'State -> source: 'T seq -> 'State

namespace FSharpPlus

namespace FSharpPlus.Math

module Generic from FSharpPlus.Math
<summary> Generic numbers, functions and operators. By opening this module some common operators become restricted, like (+) to 'T->'T->'T </summary>

namespace FSharpPlus.Data

union case Ordering.LT: Ordering

union case Ordering.EQ: Ordering

union case Ordering.GT: Ordering

val x: Ordering

type Ordering = | LT | EQ | GT static member (+) : x: Ordering * y: Ordering -> Ordering static member Zero: Ordering
A monoid that represents results of comparisons

val y: Ordering

val a: Ordering

val compare': x: 'a -> y: 'a -> Ordering (requires comparison)

val x: 'a (requires comparison)

val y: 'a (requires comparison)

val compare: e1: 'T -> e2: 'T -> int (requires comparison)

val a: int

val resGreater: Ordering

Multiple items
union case Mod5.Mod5: uint32 -> Mod5

--------------------
type Mod5 = | Mod5 of uint32 static member (+) : Mod5 * Mod5 -> Mod5 static member Zero: unit -> Mod5
A monoid of all numbers from 0 to 4

Multiple items
val uint32: value: 'T -> uint32 (requires member op_Explicit)

--------------------
type uint32 = System.UInt32

--------------------
type uint32<'Measure> = uint<'Measure>

val x: uint32

val y: uint32

Multiple items
val Mod5: x: uint32 -> Mod5

--------------------
type Mod5 = | Mod5 of uint32 static member (+) : Mod5 * Mod5 -> Mod5 static member Zero: unit -> Mod5
A monoid of all numbers from 0 to 4

val emptyLst: int list

type 'T list = List<'T>

Multiple items
val int: value: 'T -> int (requires member op_Explicit)

--------------------
type int = int32

--------------------
type int<'Measure> = int

val zero<'Monoid (requires member Zero)> : 'Monoid (requires member Zero)
<summary> A value that represents the 0 element of a Monoid. </summary>
<category index="4">Monoid</category>

val zeroUint: Mod5

val res1: Mod5

val res2: Mod5

val sum: x: 'Foldable<'Monoid> -> 'Monoid (requires member Fold and member ``+`` and member Zero)
<summary> Folds the sum of all monoid elements in the Foldable. </summary>
<category index="23">Additional Functions</category>

val map: f: ('T -> 'U) -> x: 'Functor<'T> -> 'Functor<'U> (requires member Map)
<summary>Lifts a function into a Functor.</summary>
<category index="1">Functor</category>

val res3: Mod5

val res8n4: int list list

val res15: Mult<int>

Multiple items
union case Mult.Mult: 'a -> Mult<'a>

--------------------
[<Struct>] type Mult<'a> = | Mult of 'a static member (+) : Mult<'n> * Mult<'n> -> Mult<'a2> (requires member ( * )) static member Zero: unit -> Mult<'a1> (requires member One)
<summary> Numeric wrapper for multiplication monoid (*, 1) </summary>

val resTrue: Any

Multiple items
union case Any.Any: bool -> Any

--------------------
[<Struct>] type Any = | Any of bool static member (+) : Any * Any -> Any static member Zero: Any
<summary> Boolean monoid under disjunction. </summary>

val resFalse: All

Multiple items
union case All.All: bool -> All

--------------------
[<Struct>] type All = | All of bool static member (+) : All * All -> All static member Zero: All
<summary> Boolean monoid under conjunction. </summary>

val resHi: string

val resGT: Ordering

val resLT: Ordering

val res9823: Dual<string>

Multiple items
union case Dual.Dual: 't -> Dual<'t>

--------------------
module Dual from FSharpPlus.Data
<summary> Basic operations on Dual </summary>

--------------------
[<Struct>] type Dual<'t> = | Dual of 't static member (+) : Dual<'T> * Dual<'T> -> Dual<'T> (requires member ``+``) static member Zero: unit -> Dual<'T> (requires member Zero)
<summary> The dual of a monoid, obtained by swapping the arguments of append. </summary>

val resBA: Dual<string>

val resEl00: int list * float

Multiple items
val float: value: 'T -> float (requires member op_Explicit)

--------------------
type float = System.Double

--------------------
type float<'Measure> = float

val resS3P20: int * Mult<float>

val res230: int list * float list

val res243: int list * int list

val res23: int list * string

val resLtDualGt: Ordering * Dual<Ordering>

val res230hiSum2: int list * (float list * string) * int

val res230hiS4P3: int list * (float list * string * int * Mult<int>)

val tuple5: string * (Any * string) * (All * All * All) * int * string

Multiple items
val string: value: 'T -> string

--------------------
type string = System.String