Additive monads

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))) ))

Additive monad laws

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

/// The associativity monad law 
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

/// Left zero law of additive monads
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.