In this article, we discuss how to use F# computation expressions to provide syntax for
monoidal computations. Formally, a monoid is formed by an associative binary operation
and a unit element. In computation expressions, the binary operation is represented by
the `Combine`

operation. Importantly, it has a different type and purpose than for
monads. The unit element is defined as the `Zero`

member.

The monoidal structure can be defined for a number of computations. Most well known are lists (which are covered in composed computations) and the Maybe data type (which we do not cover in this paper). In this section, we look at a simpler example - natural numbers with multiplication as the binary operation and 1 as the unit element.

The basic computation builder for `mul { .. }`

computation expressions can be defined
as follows:

type M = M of int type MulBuilder() = /// Zero element of the monoid member x.Zero() = M 1 /// Binary operation of the monoid member x.Combine(M a, M b) = M (a * b) /// Used to create elements of the monoid member x.Yield(v) = M v /// Enables the 'yield!' syntax member x.YieldFrom(M v) = M v /// Perform all effects immediately member x.Delay(f) = f() let mul = MulBuilder()

Aside from `Zero`

and `Combine`

, we also define `Yield`

, which wraps a number into the
`M`

type that represents the monoid and `YieldFrom`

that is required to enable `yield!`

.
We also define `Delay`

, because it is required by the translation - in the current implementation,
it just runs the given function immediately to perform the effects (but we get back to this
topic in the next section).

Using the computation builder defined above, we can write a function `factorial`

that
multiplies numbers from the given number to a provided upper bound (this is a more
complete example than the one in the paper):

/// When called with 'factorial 0 x' calculates 'x!' let rec factorial n bound = mul { yield n if n <= bound then yield! factorial (n + 1) bound } // Calculate the factorial of 10 factorial 0 10

The translation of the above function looks as follows:

let rec factorial n bound = mul.Delay(fun () -> mul.Combine ( mul.Yield(n), mul.Delay(fun () -> if n <= bound then mul.YieldFrom(factorial (n + 1) bound) else mul.Zero() )))

Every monoid is required to obey two laws. The binary operation has to be associative
(meaning that *a (b c) = (a b) c*) and the unit element has to behave as unit
(meaning that

/// The associativity monoid law let associativity n1 n2 n3 = let m1 = m { yield! n1 yield! n2 yield! n3 } let m2 = m { yield! m { yield! n1 yield! n2 } yield! n3 } m1 |> shouldEqual m2 /// The unit monoid laws let unit n1 n2 = let m1 = m { yield! n1 if false then yield! n2 } let m2 = m { if false then yield! n2 yield! n1 } let m3 = m { yield! n1 } m1 |> shouldEqual m3 m2 |> shouldEqual m3

In the previous example, the computation is eager. The `mul { .. }`

computation evaluates
all elements that are generated using `yield`

and multiplies all of them. This also means
that `Delay`

does not need to actually *delay* the effects, because they will be evaluated
anyway. However, we could use other properties of multiplication - since *0 * x = 0*, the
`Combine`

member could check if the first argument is 0 and stop evaluating the rest of the
computation. When using this alternative, the second argument of `Combine`

needs to be
a delayed computation - the following example uses the type `D = 1 -> M`

:

type LazyMulBuilder() = /// Zero element of the monoid member x.Zero() = M 1 /// Binary operation of the monoid member x.Combine(M a, f) = if a = 0 then M 0 else let (M b) = f() in M (a * b) /// Used to create elements of the monoid member x.Yield(v) = M v /// Enables the 'yield!' syntax member x.YieldFrom(M v) = M v /// Return the delayed computation member x.Delay(f) = f /// Evaluate a delayed computation member x.Run(f) = f() let lmul = LazyMulBuilder()

The lazy `lmul`

computation builder can be used to write the following code that multiplies
an infinite sequence of randomly generated numbers in range 0 .. 10. The generator will eventually
return 0 and then the computaiton stops:

/// Random number generator let random = System.Random() /// Multiply infinite sequence of random numbers let rec inf () = lmul { yield random.Next(10) yield! inf () }

If we wrote the same function using the `mul`

computation builder described earlier, than the
computation would loop forever and would never terminate.

Similarly to monadic computations, it is possible to extend a monoidal computation expression with
standard F# control flow constructs including loops (`for`

and `while`

) and exception handlers.
The following code sample extends the `LazyMulBuilder`

:

type LazyMulBuilder with /// The exception handling uses the delayed type directly member m.TryWith(f, handler) = try f() with e -> handler e /// The finalizer is defined similarly (but the body of the /// finalizer cannot be monoidal - just a `unit -> unit` function) member m.TryFinally(f, finalizer) = try f() finally finalizer() /// The 'while' loop evaluates the condition and then either ends /// (returning 'Zero'), or evaluates body once and then runs recursively member m.While(cond, body) = if not (cond()) then m.Zero() else m.Combine(m.Run(body), m.Delay(fun () -> m.While(cond, body))) /// The 'for' loop can be defined using 'While' and 'Using' member m.For(xs:seq<'T>, f) = let en = xs.GetEnumerator() m.TryFinally ( m.Delay(fun () -> m.While( (fun () -> en.MoveNext()), m.Delay(fun () -> f en.Current) )), fun () -> en.Dispose() )

The definition of `TryWith`

and `TryFinally`

is the same as for *monadic containers* in the
previous section. As the delayed computation type is a function `unit -> M<'T>`

,
the handling does not need to inspect the structure of the computation and can be implemented
by wrapping the function call with a handler. For monoidal computations that have a built-in
notion of delayed computations (such as lazy lists), the operations have to be implemented
differently.

Unlike for monads, we do not provide the `Using`

member (which corresponds to binding and so
it is not appropriate). This means that the `For`

member needs to use `TryFinally`

explicitly
(unlike in the previous section). However, otherwise the definition of `While`

and `For`

also
follows the one dicussed for monads. The new definitions allow us to write the following:

/// Calculate the factorial of a number let factorial x = lmul { for num in 1 .. x do yield num }

type M = | M of int

Full name: TryJoinads.M

type: M

Full name: TryJoinads.M

type: M

union case M.M: int -> M

Multiple items

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

Full name: Microsoft.FSharp.Core.Operators.int

--------------------

type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

type: int<'Measure>

inherits: System.ValueType

--------------------

type int = int32

Full name: Microsoft.FSharp.Core.int

type: int

inherits: System.ValueType

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

Full name: Microsoft.FSharp.Core.Operators.int

--------------------

type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

type: int<'Measure>

inherits: System.ValueType

--------------------

type int = int32

Full name: Microsoft.FSharp.Core.int

type: int

inherits: System.ValueType

type MulBuilder =

class

new : unit -> MulBuilder

member Combine : M * M -> M

member Delay : f:(unit -> 'a) -> 'a

member Yield : v:int -> M

member YieldFrom : M -> M

member Zero : unit -> M

end

Full name: TryJoinads.MulBuilder

class

new : unit -> MulBuilder

member Combine : M * M -> M

member Delay : f:(unit -> 'a) -> 'a

member Yield : v:int -> M

member YieldFrom : M -> M

member Zero : unit -> M

end

Full name: TryJoinads.MulBuilder

val x : MulBuilder

member MulBuilder.Zero : unit -> M

Full name: TryJoinads.MulBuilder.Zero

Zero element of the monoid

Full name: TryJoinads.MulBuilder.Zero

Zero element of the monoid

member MulBuilder.Combine : M * M -> M

Full name: TryJoinads.MulBuilder.Combine

Binary operation of the monoid

Full name: TryJoinads.MulBuilder.Combine

Binary operation of the monoid

val a : int

type: int

inherits: System.ValueType

type: int

inherits: System.ValueType

val b : int

type: int

inherits: System.ValueType

type: int

inherits: System.ValueType

member MulBuilder.Yield : v:int -> M

Full name: TryJoinads.MulBuilder.Yield

Used to create elements of the monoid

Full name: TryJoinads.MulBuilder.Yield

Used to create elements of the monoid

val v : int

type: int

inherits: System.ValueType

type: int

inherits: System.ValueType

member MulBuilder.YieldFrom : M -> M

Full name: TryJoinads.MulBuilder.YieldFrom

Enables the 'yield!' syntax

Full name: TryJoinads.MulBuilder.YieldFrom

Enables the 'yield!' syntax

member MulBuilder.Delay : f:(unit -> 'a) -> 'a

Full name: TryJoinads.MulBuilder.Delay

Perform all effects immediately

Full name: TryJoinads.MulBuilder.Delay

Perform all effects immediately

val f : (unit -> 'a)

val mul : MulBuilder

Full name: TryJoinads.mul

Full name: TryJoinads.mul

val factorial : int -> int -> M

Full name: TryJoinads.factorial

When called with 'factorial 0 x' calculates 'x!'

Full name: TryJoinads.factorial

When called with 'factorial 0 x' calculates 'x!'

val n : int

type: int

inherits: System.ValueType

type: int

inherits: System.ValueType

val bound : int

type: int

inherits: System.ValueType

type: int

inherits: System.ValueType

val factorial : int -> int -> M

Full name: TryJoinads.MulTranslation.factorial

Full name: TryJoinads.MulTranslation.factorial

member MulBuilder.Delay : f:(unit -> 'a) -> 'a

Perform all effects immediately

Perform all effects immediately

member MulBuilder.Combine : M * M -> M

Binary operation of the monoid

Binary operation of the monoid

member MulBuilder.Yield : v:int -> M

Used to create elements of the monoid

Used to create elements of the monoid

member MulBuilder.YieldFrom : M -> M

Enables the 'yield!' syntax

Enables the 'yield!' syntax

member MulBuilder.Zero : unit -> M

Zero element of the monoid

Zero element of the monoid

val m : MulBuilder

Full name: TryJoinads.m

Full name: TryJoinads.m

val shouldEqual : 'a -> 'a -> unit (requires equality)

Full name: TryJoinads.shouldEqual

Full name: TryJoinads.shouldEqual

val a : 'a (requires equality)

val b : 'a (requires equality)

val not : bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not

Full name: Microsoft.FSharp.Core.Operators.not

val failwith : string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith

Full name: Microsoft.FSharp.Core.Operators.failwith

val associativity : M -> M -> M -> unit

Full name: TryJoinads.associativity

The associativity monoid law

Full name: TryJoinads.associativity

The associativity monoid law

val n1 : M

type: M

type: M

val n2 : M

type: M

type: M

val n3 : M

type: M

type: M

val m1 : M

type: M

type: M

val m2 : M

type: M

type: M

Multiple items

val unit : M -> M -> unit

Full name: TryJoinads.unit

The unit monoid laws

--------------------

type unit = Unit

Full name: Microsoft.FSharp.Core.unit

type: unit

val unit : M -> M -> unit

Full name: TryJoinads.unit

The unit monoid laws

--------------------

type unit = Unit

Full name: Microsoft.FSharp.Core.unit

type: unit

val m3 : M

type: M

type: M

type LazyMulBuilder =

class

new : unit -> LazyMulBuilder

member Combine : M * f:(unit -> M) -> M

member Delay : f:'b -> 'b

member For : xs:seq<'T> * f:('T -> M) -> M

member Run : f:(unit -> 'a) -> 'a

member TryFinally : f:(unit -> 'a) * finalizer:(unit -> unit) -> 'a

member TryWith : f:(unit -> 'a) * handler:(exn -> 'a) -> 'a

member While : cond:(unit -> bool) * body:(unit -> M) -> M

member Yield : v:int -> M

member YieldFrom : M -> M

member Zero : unit -> M

end

Full name: TryJoinads.LazyMulBuilder

class

new : unit -> LazyMulBuilder

member Combine : M * f:(unit -> M) -> M

member Delay : f:'b -> 'b

member For : xs:seq<'T> * f:('T -> M) -> M

member Run : f:(unit -> 'a) -> 'a

member TryFinally : f:(unit -> 'a) * finalizer:(unit -> unit) -> 'a

member TryWith : f:(unit -> 'a) * handler:(exn -> 'a) -> 'a

member While : cond:(unit -> bool) * body:(unit -> M) -> M

member Yield : v:int -> M

member YieldFrom : M -> M

member Zero : unit -> M

end

Full name: TryJoinads.LazyMulBuilder

val x : LazyMulBuilder

member LazyMulBuilder.Zero : unit -> M

Full name: TryJoinads.LazyMulBuilder.Zero

Zero element of the monoid

Full name: TryJoinads.LazyMulBuilder.Zero

Zero element of the monoid

member LazyMulBuilder.Combine : M * f:(unit -> M) -> M

Full name: TryJoinads.LazyMulBuilder.Combine

Binary operation of the monoid

Full name: TryJoinads.LazyMulBuilder.Combine

Binary operation of the monoid

val f : (unit -> M)

member LazyMulBuilder.Yield : v:int -> M

Full name: TryJoinads.LazyMulBuilder.Yield

Used to create elements of the monoid

Full name: TryJoinads.LazyMulBuilder.Yield

Used to create elements of the monoid

member LazyMulBuilder.YieldFrom : M -> M

Full name: TryJoinads.LazyMulBuilder.YieldFrom

Enables the 'yield!' syntax

Full name: TryJoinads.LazyMulBuilder.YieldFrom

Enables the 'yield!' syntax

member LazyMulBuilder.Delay : f:'b -> 'b

Full name: TryJoinads.LazyMulBuilder.Delay

Return the delayed computation

Full name: TryJoinads.LazyMulBuilder.Delay

Return the delayed computation

val f : 'b

member LazyMulBuilder.Run : f:(unit -> 'a) -> 'a

Full name: TryJoinads.LazyMulBuilder.Run

Evaluate a delayed computation

Full name: TryJoinads.LazyMulBuilder.Run

Evaluate a delayed computation

val lmul : LazyMulBuilder

Full name: TryJoinads.lmul

Full name: TryJoinads.lmul

val random : System.Random

Full name: TryJoinads.random

Random number generator

Full name: TryJoinads.random

Random number generator

namespace System

type Random =

class

new : unit -> System.Random

new : int -> System.Random

member Next : unit -> int

member Next : int -> int

member Next : int * int -> int

member NextBytes : System.Byte [] -> unit

member NextDouble : unit -> float

end

Full name: System.Random

class

new : unit -> System.Random

new : int -> System.Random

member Next : unit -> int

member Next : int -> int

member Next : int * int -> int

member NextBytes : System.Byte [] -> unit

member NextDouble : unit -> float

end

Full name: System.Random

val inf : unit -> M

Full name: TryJoinads.inf

Multiply infinite sequence of random numbers

Full name: TryJoinads.inf

Multiply infinite sequence of random numbers

System.Random.Next() : int

System.Random.Next(maxValue: int) : int

System.Random.Next(minValue: int, maxValue: int) : int

System.Random.Next(maxValue: int) : int

System.Random.Next(minValue: int, maxValue: int) : int

val m : LazyMulBuilder

member LazyMulBuilder.TryWith : f:(unit -> 'a) * handler:(exn -> 'a) -> 'a

Full name: TryJoinads.LazyMulBuilder.TryWith

The exception handling uses the delayed type directly

Full name: TryJoinads.LazyMulBuilder.TryWith

The exception handling uses the delayed type directly

val handler : (exn -> 'a)

Multiple items

val e : exn

type: exn

--------------------

val e : exn

type: exn

val e : exn

type: exn

--------------------

val e : exn

type: exn

val e : exn

type: exn

type: exn

member LazyMulBuilder.TryFinally : f:(unit -> 'a) * finalizer:(unit -> unit) -> 'a

Full name: TryJoinads.LazyMulBuilder.TryFinally

The finalizer is defined similarly (but the body of the

finalizer cannot be monoidal - just a `unit -> unit` function)

Full name: TryJoinads.LazyMulBuilder.TryFinally

The finalizer is defined similarly (but the body of the

finalizer cannot be monoidal - just a `unit -> unit` function)

val finalizer : (unit -> unit)

member LazyMulBuilder.While : cond:(unit -> bool) * body:(unit -> M) -> M

Full name: TryJoinads.LazyMulBuilder.While

The 'while' loop evaluates the condition and then either ends

(returning 'Zero'), or evaluates body once and then runs recursively

Full name: TryJoinads.LazyMulBuilder.While

The 'while' loop evaluates the condition and then either ends

(returning 'Zero'), or evaluates body once and then runs recursively

val cond : (unit -> bool)

val body : (unit -> M)

member LazyMulBuilder.Zero : unit -> M

Zero element of the monoid

Zero element of the monoid

member LazyMulBuilder.Combine : M * f:(unit -> M) -> M

Binary operation of the monoid

Binary operation of the monoid

member LazyMulBuilder.Run : f:(unit -> 'a) -> 'a

Evaluate a delayed computation

Evaluate a delayed computation

member LazyMulBuilder.Delay : f:'b -> 'b

Return the delayed computation

Return the delayed computation

member LazyMulBuilder.While : cond:(unit -> bool) * body:(unit -> M) -> M

The 'while' loop evaluates the condition and then either ends

(returning 'Zero'), or evaluates body once and then runs recursively

The 'while' loop evaluates the condition and then either ends

(returning 'Zero'), or evaluates body once and then runs recursively

member LazyMulBuilder.For : xs:seq<'T> * f:('T -> M) -> M

Full name: TryJoinads.LazyMulBuilder.For

The 'for' loop can be defined using 'While' and 'Using'

Full name: TryJoinads.LazyMulBuilder.For

The 'for' loop can be defined using 'While' and 'Using'

val xs : seq<'T>

type: seq<'T>

inherits: System.Collections.IEnumerable

type: seq<'T>

inherits: System.Collections.IEnumerable

Multiple items

val seq : seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------

type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>

type: seq<'T>

inherits: System.Collections.IEnumerable

val seq : seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------

type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>

type: seq<'T>

inherits: System.Collections.IEnumerable

val f : ('T -> M)

val en : System.Collections.Generic.IEnumerator<'T>

type: System.Collections.Generic.IEnumerator<'T>

inherits: System.IDisposable

inherits: System.Collections.IEnumerator

type: System.Collections.Generic.IEnumerator<'T>

inherits: System.IDisposable

inherits: System.Collections.IEnumerator

System.Collections.Generic.IEnumerable.GetEnumerator() : System.Collections.Generic.IEnumerator<'T>

member LazyMulBuilder.TryFinally : f:(unit -> 'a) * finalizer:(unit -> unit) -> 'a

The finalizer is defined similarly (but the body of the

finalizer cannot be monoidal - just a `unit -> unit` function)

The finalizer is defined similarly (but the body of the

finalizer cannot be monoidal - just a `unit -> unit` function)

System.Collections.IEnumerator.MoveNext() : bool

property System.Collections.Generic.IEnumerator.Current: 'T

System.IDisposable.Dispose() : unit

val factorial : int -> M

Full name: TryJoinads.AnotherFactorial.factorial

Calculate the factorial of a number

Full name: TryJoinads.AnotherFactorial.factorial

Calculate the factorial of a number

val x : int

type: int

inherits: System.ValueType

type: int

inherits: System.ValueType

val num : int

type: int

inherits: System.ValueType

type: int

inherits: System.ValueType