The previous sections demonstrated how to define F# computation expression for monoidal and monadic computations. In this section, we look at computations that combine multiple aspects. We look at computations that form additive monads (also called `MonadPlus` in Haskell), which means that they provide both monadic and monoidal operations.

An additive monad is a monad (with bind and return) that also implements a binary operation combine (that can be used for combining two computations) and has a unit element. Two examples of additive monads are parsers (where binary operation represents non-deterministic choice) and lists or other collections (where binary operation is the concatenation).

## Computation builder for parsers

The following snippet defines simple parser combinators and implements the basic operations that are required in order to define a computation builder. The parser is represented as a function that takes a list of characters and returns an sequence of possible results. Every element contains the parsed result and an unconsumed buffer. Note that the `zero` operation is the unit with respect to `combine`.

```type Parser<'T> = P of (list<char> -> seq<'T * list<char>>)

/// Run the parser and return the first result (or None)
let run (P f) = List.ofSeq >> f >> Seq.map fst >> Seq.tryPick Some

module Parsers =
/// Parser that succeeds without consuming any input
let unit v = P (fun buffer -> seq [v, buffer])

/// Runs the first parser and then a parser
/// generated by the provided function
let bind f (P p1) = P (fun buffer ->
seq { for (v, buffer) in p1 buffer do
let (P p2) = f v
yield! p2 buffer })

/// Represents a parser that always fails
let zero () = P (fun buffer -> Seq.empty)

/// Non-deterministic choice - combine all possible results
let combine (P p1) (P p2) = P (fun buffer ->
Seq.concat [ p1 buffer; p2 buffer ])```

Using the above operations, we can define a computation builder for working with additive monads. The computation `Parser<'T>` can capture untracked effects (in the function) and so we also provide an explicit `Delay` member (similarly to the monadic examples). Although the computation builder looks similar to the one for monads, it behaves quite differently, because `zero` and `combine` are unique operations that are not defined in terms of `bind` and `return`:

```/// Computation builder for working with parsers
type ParserBuilder() =
member x.Return(v) = Parsers.unit v
member x.ReturnFrom(m) = m
member x.Bind(v, f) = Parsers.bind f v
member x.Zero() = Parsers.zero()
member x.Combine(p1, p2) = Parsers.combine p1 p2
member x.Delay(f) = P (fun buffer ->
let (P op) = f () in op buffer)

/// A unique instance of the computation builder
let parse = ParserBuilder()```

### Programming with parsers

Using the above definition, we can write a number of interesting parsers as a computation. The following two examples (from the paper) represent parsers that repeat the specified parser `p` one or more times and zero or more times respectively:

```/// Parse one or more occurrences of 'p'
let rec oneOrMore p = parse {
let! x = p
let! xs = zeroOrMore p
return x::xs }

/// Parse zero or more occurrences of 'p'
and zeroOrMore p = parse {
return! oneOrMore p
return [] }```

As discussed in the paper, the `oneOrMore` computation uses the monadic interface. It sequentially composes parser `p` follwed by `zeroOrMore p`, which means that it always needs to parse `p` first (at least once). The parser `zeroOrMore` uses the monoidal interface - it combines the results of `oneOrMore p` (which parses `p` at least once) with a parser that succeeds immediately, returning an emtpy list. In the translation, the first function uses `Bind` and `Return`, while the second one uses `Combine`:

```let rec oneOrMore p =
parse.Delay(fun () ->
parse.Bind(p, fun x ->
parse.Bind(zeroOrMore p, fun xs ->
parse.Return(x::xs))))

and zeroOrMore p =
parse.Delay(fun () ->
parse.Combine
( parse.ReturnFrom(oneOrMore p),
parse.Delay(fun () -> parse.Return([])) ))```

To run the sample parsers defined earlier, we need to add a number of primitive parsers. In the following snippet, `sat` parses a single character if it matches a given predicate and `letter` with `number` parse individual letter or numeric symbol, respectively:

```/// Primitive parser that parses a char if it matches a predicate
let sat f = (...)
// Parsers that recognize single letter and number
let letter = sat System.Char.IsLetter
let number = sat System.Char.IsNumber

// Examples: Parse one or more & zero or more numbers
run (oneOrMore number) "hi"
run (oneOrMore number) "123"
run (zeroOrMore number) "hi"
run (zeroOrMore number) "123"```

The last four lines can be evalauted to demonstrate the behaviour of `oneOrMore` and `zeroOrMore`. The first one fails when given "hi", because that string does not start with any number. On the other hand, `zeroOrMore` succeeds, returning an empty list (of parsed numeric characters) as the result.

We could extend the `parse` computation a bit further, but that is beyond the scope of this online appendix. In particular, it would be possible to provide `for` and `while` loops in a standard fashion (similarly to monads) in order to write parsers that consume some parser in a loop. This would give us an elegant way to parse, for example, constant number of repetitions.

## Computation builder for sequences

Other examples of a computation that matches the additive monad pattern are lists, sequences and other collections. The built-in computation builder `seq { .. }` can be viewed as an instance of this structure, but it uses quite different syntax. This is the case, because sequences emphasize the monoidal structure (which uses the `yield` keyword) in favor of the monadic structure (using `let!` and `return`). The standard operations for the `seq<'T>` type can be defined as follows (here, we use the same naming as in the previous example):

```module Sequence =
/// Returns a singleton sequence containing just 'v'
let unit v = Seq.singleton v
/// Apply 'f' to all elements and concatenate generated sequences
let bind f s = s |> Seq.map f |> Seq.concat
/// Concatenate elements of two sequences
let combine s1 s2 = Seq.concat [ s1; s2 ]
/// Returns an empty sequence
let zero () = Seq.empty```

The computation builder uses `unit` in the definition of the `Yield` member (and it also defines `YieldFrom` instead of `ReturnFrom` to enable the `yield!` keyword). For sequences, the type of the standard control flow construct `for` overlaps with the type of `let!` (bind) and so we implement `For` using `bind` in order to make the computation builder easier to use:

```/// Computation builder for working with sequences
type SeqBuilder() =
member x.Yield(v) = Sequence.unit v
member x.YieldFrom(m) = m
member x.For(v, f) = Sequence.bind f v
member x.Zero() = Sequence.zero()
member x.Combine(p1, p2) = Sequence.combine p1 p2
member x.Delay(f) = Seq.delay f

/// A unique instance of the computation builder
let sq = SeqBuilder()```

Just like parsers, sequences can capture untracked F# effects, so the type of delayed computations is also `seq<'T>`. The `Delay` member can be implemented using a standard library function `Seq.delay`.

### Programming with sequences

The following example shows how to generate a sequence of Fibonacci numbers using the computation builder:

```let rec fibs =
sq { // Yield the first two elements
yield! seq [1; 1]
// Generate by adding previous and pre-previous numbers
for a, b in Seq.zip fibs (Seq.skip 1 fibs) do
yield a + b }

// Run this code to generate a sample sequence
fibs |> Seq.take 12 |> List.ofSeq```

The translated code combines both monadic and monoidal operations. The operation `Combine` is used to combine the first two elements of the sequence with the rest of the sequence generated by `for`. The `for` keyword corresponds to monadic bind (although exposed as the `For` member) and it performs a simple map operation over a sequence:

```let rec fibs =
sq.Delay(fun () ->
sq.Combine
( sq.YieldFrom( seq [1; 1] ),
sq.Delay(fun () ->
sq.For(Seq.zip fibs (Seq.skip 1 fibs), fun (a, b) ->
sq.Yield(a + b))) ))```

To conclude, additive monads also obey a set of laws. Although these are less widely known (and standardized) than for monads or monoids, they form an important component of the interface. They can be expressed in terms of both notations that were used above - we use the first one that is, arguably, more standard. As expected, the laws overlap with the laws that were discussed earlier about monads and monoids:

```/// The associativity monoid law
let monoidAssociativity n1 n2 n3 =
let m1 = m { return! n1
return! n2
return! n3 }
let m2 = m { return! m { return! n1
return! n2 }
return! n3 }
m1 |> shouldEqual m2

/// The unit monoid laws
let unit n1 n2 =
let m1 = m { return! n1
if false then return! n2 }
let m2 = m { if false then return! n2
return! n1 }
let m3 = m { return! n1 }

m1 |> shouldEqual m3
m2 |> shouldEqual m3

/// The left identity monad law
let leftIdentity x f =
let m1 = m { let! v = m { return x }
return! f v }
let m2 = m { return! f x }
m1 |> shouldEqual m2

/// The right identity monad law
let rightIdentity n =
let m1 = m { let! x = n
return x }
let m2 = m { return! n }
m1 |> shouldEqual m2

let monadAssociativity n f g =
let m1 = m { let! y = m { let! x = n
return! f x }
return! g y }
let m2 = m { let! x = n
return! m { let! y = f x
return! g x } }
let m3 = m { let! x = n
let! y = f x
return! g x }
m1 |> shouldEqual m2
m1 |> shouldEqual m3

let leftZero n1 k =
let m1 = m { let! v = m { if false then return! n1 }
return! k v }
let m2 = m { if false then return! n1 }
m1 |> shouldEqual m2```

The only law that has not been discussed previously for either monads or monoids is the last law, which captures the relationship between monadic bind and the `zero` operation. In Haskell, the law is usually expressed as `mzero >>= k = mzero`.

The listing above includes widely accepted laws only. However, additional laws such as left catch and left distribution (see MonadPlus page) could be expressed using the computation expression notation as well.

type Parser<'T> = | P of (char list -> seq<'T * char list>)

union case Parser.P: (char list -> seq<'T * char list>) -> Parser<'T>
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
type: 'T list
Multiple items
val char : 'T -> char (requires member op_Explicit)

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

--------------------
type char = System.Char

Full name: Microsoft.FSharp.Core.char
type: char
inherits: System.ValueType
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 run : Parser<'a> -> (seq<char> -> 'a option)

Run the parser and return the first result (or None)
val f : (char list -> seq<'a * char list>)
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of 'T * 'T list
with
interface System.Collections.IEnumerable
interface System.Collections.Generic.IEnumerable<'T>
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list
end

Full name: Microsoft.FSharp.Collections.List<_>
type: List<'T>
val ofSeq : seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.List.ofSeq
module Seq

from Microsoft.FSharp.Collections
val map : ('T -> 'U) -> seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map
val fst : ('T1 * 'T2) -> 'T1

Full name: Microsoft.FSharp.Core.Operators.fst
val tryPick : ('T -> 'U option) -> seq<'T> -> 'U option

Full name: Microsoft.FSharp.Collections.Seq.tryPick
union case Option.Some: 'T -> Option<'T>
Multiple items
val unit : 'a -> Parser<'a>

Parser that succeeds without consuming any input

--------------------
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
type: unit
val v : 'a
val buffer : char list
type: char list
val bind : ('a -> Parser<'b>) -> Parser<'a> -> Parser<'b>

Runs the first parser and then a parser
generated by the provided function
val f : ('a -> Parser<'b>)
val p1 : (char list -> seq<'a * char list>)
val p2 : (char list -> seq<'b * char list>)
val zero : unit -> Parser<'a>

Represents a parser that always fails
val empty<'T> : seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.empty
val combine : Parser<'a> -> Parser<'a> -> Parser<'a>

Non-deterministic choice - combine all possible results
val p2 : (char list -> seq<'a * char list>)
val concat : seq<#seq<'T>> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.concat
type ParserBuilder =
class
new : unit -> ParserBuilder
member Bind : v:Parser<'d> * f:('d -> Parser<'e>) -> Parser<'e>
member Combine : p1:Parser<'b> * p2:Parser<'b> -> Parser<'b>
member Delay : f:(unit -> Parser<'a>) -> Parser<'a>
member Return : v:'g -> Parser<'g>
member ReturnFrom : m:'f -> 'f
member Zero : unit -> Parser<'c>
end

Computation builder for working with parsers
val x : ParserBuilder
member ParserBuilder.Return : v:'g -> Parser<'g>

val v : 'g
module Parsers

val unit : 'a -> Parser<'a>

Parser that succeeds without consuming any input
member ParserBuilder.ReturnFrom : m:'f -> 'f

val m : 'f
member ParserBuilder.Bind : v:Parser<'d> * f:('d -> Parser<'e>) -> Parser<'e>

val v : Parser<'d>
val f : ('d -> Parser<'e>)
member ParserBuilder.Zero : unit -> Parser<'c>

member ParserBuilder.Combine : p1:Parser<'b> * p2:Parser<'b> -> Parser<'b>

val p1 : Parser<'b>
val p2 : Parser<'b>
member ParserBuilder.Delay : f:(unit -> Parser<'a>) -> Parser<'a>

val f : (unit -> Parser<'a>)
val op : (char list -> seq<'a * char list>)
val parse : ParserBuilder

A unique instance of the computation builder
val oneOrMore : Parser<'a> -> Parser<'a list>

Parse one or more occurrences of 'p'
val p : Parser<'a>
val x : 'a
val xs : 'a list
type: 'a list
val zeroOrMore : Parser<'a> -> Parser<'a list>

Parse zero or more occurrences of 'p'
val oneOrMore : Parser<'a> -> Parser<'a list>

member ParserBuilder.Delay : f:(unit -> Parser<'a>) -> Parser<'a>
member ParserBuilder.Bind : v:Parser<'d> * f:('d -> Parser<'e>) -> Parser<'e>
val zeroOrMore : Parser<'a> -> Parser<'a list>

member ParserBuilder.Return : v:'g -> Parser<'g>
member ParserBuilder.Combine : p1:Parser<'b> * p2:Parser<'b> -> Parser<'b>
member ParserBuilder.ReturnFrom : m:'f -> 'f
val sat : (char -> bool) -> Parser<char>

Primitive parser that parses a char if it matches a predicate
val f : (char -> bool)
P (fun buffer -> seq {
match buffer with
| x::xs when f x -> yield x, xs
| _ -> () })
val letter : Parser<char>

namespace System
type Char =
struct
member CompareTo : obj -> int
member CompareTo : char -> int
member Equals : obj -> bool
member Equals : char -> bool
member GetHashCode : unit -> int
member GetTypeCode : unit -> System.TypeCode
member ToString : unit -> string
member ToString : System.IFormatProvider -> string
static val MaxValue : char
static val MinValue : char
static member GetNumericValue : char -> float
static member GetNumericValue : string * int -> float
static member GetUnicodeCategory : char -> System.Globalization.UnicodeCategory
static member GetUnicodeCategory : string * int -> System.Globalization.UnicodeCategory
static member IsControl : char -> bool
static member IsControl : string * int -> bool
static member IsDigit : char -> bool
static member IsDigit : string * int -> bool
static member IsLetter : char -> bool
static member IsLetter : string * int -> bool
static member IsLetterOrDigit : char -> bool
static member IsLetterOrDigit : string * int -> bool
static member IsLower : char -> bool
static member IsLower : string * int -> bool
static member IsNumber : char -> bool
static member IsNumber : string * int -> bool
static member IsPunctuation : char -> bool
static member IsPunctuation : string * int -> bool
static member IsSeparator : char -> bool
static member IsSeparator : string * int -> bool
static member IsSurrogate : char -> bool
static member IsSurrogate : string * int -> bool
static member IsSurrogatePair : string * int -> bool
static member IsSurrogatePair : char * char -> bool
static member IsSymbol : char -> bool
static member IsSymbol : string * int -> bool
static member IsUpper : char -> bool
static member IsUpper : string * int -> bool
static member IsWhiteSpace : char -> bool
static member IsWhiteSpace : string * int -> bool
static member ToLower : char -> char
static member ToLower : char * System.Globalization.CultureInfo -> char
static member ToLowerInvariant : char -> char
static member ToString : char -> string
static member ToUpper : char -> char
static member ToUpper : char * System.Globalization.CultureInfo -> char
static member ToUpperInvariant : char -> char
static member TryParse : string * char -> bool
end

Full name: System.Char
type: System.Char
inherits: System.ValueType
System.Char.IsLetter(c: char) : bool
System.Char.IsLetter(s: string, index: int) : bool
val number : Parser<char>

System.Char.IsNumber(c: char) : bool
System.Char.IsNumber(s: string, index: int) : bool
Multiple items
val unit : 'a -> seq<'a>

Returns a singleton sequence containing just 'v'

--------------------
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
type: unit
val singleton : 'T -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.singleton
val bind : ('a -> #seq<'c>) -> seq<'a> -> seq<'c>

Apply 'f' to all elements and concatenate generated sequences
val f : ('a -> #seq<'c>)
val s : seq<'a>
type: seq<'a>
inherits: System.Collections.IEnumerable
val combine : 'a -> 'a -> seq<'b> (requires 'a :> seq<'b>)

Concatenate elements of two sequences
val s1 : #seq<'b>
type: #seq<'b>
val s2 : #seq<'b>
type: #seq<'b>
val zero : unit -> seq<'a>

Returns an empty sequence
type SeqBuilder =
class
new : unit -> SeqBuilder
member Combine : p1:'b * p2:'b -> seq<'c> (requires 'b :> seq<'c>)
member Delay : f:(unit -> seq<'a>) -> seq<'a>
member For : v:seq<'e> * f:('e -> #seq<'g>) -> seq<'g>
member Yield : v:'i -> seq<'i>
member YieldFrom : m:'h -> 'h
member Zero : unit -> seq<'d>
end

Computation builder for working with sequences
val x : SeqBuilder
member SeqBuilder.Yield : v:'i -> seq<'i>

val v : 'i
module Sequence

val unit : 'a -> seq<'a>

Returns a singleton sequence containing just 'v'
member SeqBuilder.YieldFrom : m:'h -> 'h

val m : 'h
member SeqBuilder.For : v:seq<'e> * f:('e -> #seq<'g>) -> seq<'g>

val v : seq<'e>
type: seq<'e>
inherits: System.Collections.IEnumerable
val f : ('e -> #seq<'g>)
member SeqBuilder.Zero : unit -> seq<'d>

member SeqBuilder.Combine : p1:'b * p2:'b -> seq<'c> (requires 'b :> seq<'c>)

val p1 : #seq<'c>
type: #seq<'c>
val p2 : #seq<'c>
type: #seq<'c>
member SeqBuilder.Delay : f:(unit -> seq<'a>) -> seq<'a>

val f : (unit -> seq<'a>)
val delay : (unit -> seq<'T>) -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.delay
val sq : SeqBuilder

A unique instance of the computation builder
val fibs : seq<int>

type: seq<int>
inherits: System.Collections.IEnumerable
val a : int
type: int
inherits: System.ValueType
val b : int
type: int
inherits: System.ValueType
val zip : seq<'T1> -> seq<'T2> -> seq<'T1 * 'T2>

Full name: Microsoft.FSharp.Collections.Seq.zip
val skip : int -> seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.skip
val take : int -> seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.take
val fibs : seq<int>

type: seq<int>
inherits: System.Collections.IEnumerable
member SeqBuilder.Delay : f:(unit -> seq<'a>) -> seq<'a>
member SeqBuilder.Combine : p1:'b * p2:'b -> seq<'c> (requires 'b :> seq<'c>)
member SeqBuilder.YieldFrom : m:'h -> 'h
member SeqBuilder.For : v:seq<'e> * f:('e -> #seq<'g>) -> seq<'g>
member SeqBuilder.Yield : v:'i -> seq<'i>
val m : ParserBuilder

val shouldEqual : Parser<'a> -> Parser<'b> -> 'c

val a : (char list -> seq<'a * char list>)
val b : (char list -> seq<'b * char list>)
val failwith : string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
val monoidAssociativity : Parser<'a> -> Parser<'a> -> Parser<'a> -> 'b

The associativity monoid law
val n1 : Parser<'a>
val n2 : Parser<'a>
val n3 : Parser<'a>
val m1 : Parser<'a>
val m2 : Parser<'a>
Multiple items
val unit : Parser<'a> -> Parser<'a> -> 'b

The unit monoid laws

--------------------
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
type: unit
val m3 : Parser<'a>
val leftIdentity : 'a -> ('a -> Parser<'b>) -> 'c

val m1 : Parser<'b>
val m2 : Parser<'b>
val rightIdentity : Parser<'a> -> 'b

val n : Parser<'a>
val monadAssociativity : Parser<'a> -> ('a -> Parser<'a>) -> ('a -> Parser<'b>) -> 'c