Implementing joinads for parsers

In functional programming, parser combinators are a powerful way of writing parsers. A parser is a function that, given some input, returns possible parsed values and the rest of the input. Parsers can be written using combinators for composition, for example run two parsers in sequence or perform one parser any number of times.

Parsers can also implement the monad structure. In some cases, this makes the parser less efficient, but it is an elegant way of composing parsers and we can also benefit from the syntactic support for monads. In this article, we implement a simple parser combinators for F# and we look what additional expressive power we can get from the joinad structure and match! construct. This article is largely based on a previous article "Fun with Parallel Monad Comprehensions", which can be found on the publications page.

Implmenting simple parsers

In the F# implementation, we define parser as a single-case discriminated union that contains a parsing function. When given a list of characters, the function returns a sequence with possible parsings of the input. The parsing consists of an obtained value 'T, together with int and a list of unconsumed characters:

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

The int value in the result represents the number of characters consumed by the parser. It is not usually included in the definition, but we'll use it in the definition of joinad operations. As a next step, we define a simple parser and a function to run the parser:

open System

let item = Parser (function
  | [] -> seq []
  | x::xs -> seq [(x, 1, xs)])

let run (Parser p) input = 
  seq { for (result, _, tail) in p (List.ofSeq input) do
          if tail = [] then yield result }

The item parser returns the first character from the input. When it succeeds, it consumes a single character, so it returns 1 as the second element of the tuple. The run function converts the input to a list (i.e. from a string) and then runs the parser. The condition tail = [] specifies that only results that were parsed without any remaining characters should be returned.

Providing the monad structure

Parsers are monads and so we can implement an F# computaion expression builder for constructing them. In additional, parsers can also be combined and have a zero value (parser that fails). In F#, this means we can also define Zero and Combine methods:

/// Parser that always succeeds without consuming any input
let unit v = Parser (fun input -> seq [(v, 0, input)])

/// Apply the first parser and then continue using 'f'
let bind f (Parser p1) = Parser (fun input ->
  seq { for (a, n1, input') in p1 input do
          let (Parser p2) = f a
          for (result, n2, tail) in p2 input' do
            yield result, n1 + n2, tail })

/// Parser that alwyas fails without consuming any input
let zero = Parser (fun _ -> seq [])

/// Combine the results of two parsers
let plus (Parser p1) (Parser p2) = Parser (fun input ->
  Seq.concat [ p1 input; p2 input ])

/// Computation expression builder for creating parsers
type ParseBuilder() = (...)
let parse = ParseBuilder()

The unit operation returns a single result containing the specified value that doesn't consume any input. The implementation of bind uses sequence comprehensions to run the parsers in sequence. It returs the result of the second parser and consumes the sum of characters consumed by the first and the second parser. The zero operation creates a parser that always fails, and plus represents a nondeterministic choice between two parsers.

The computation builder also defines ReturnFrom member (to allow the return! syntax). It provides Delay and Run members - these will be used later by the joinad definitions, but they change how Combine behaves. In particular, one way to define Delay is to simply return the function (of type unit -> Parser<'T>) that it gets as an argument. As a result, the second argument of Combine will also be a function and so it needs to be evaluated before calling plus. The Run member is used on a value obtained from Delay, so it simply runs the function.

Using the parser computation builder, we can write a couple of basic parser combinators:

/// Apply function 'f' to the parsed value
let map f p = parse {
  let! v = p
  return f v }

/// Succeeds only when a character matches given predicate
let sat pred = parse {
  let! ch = item
  if pred ch then return ch }

/// Parse a specific character
let char ch = sat ((=) ch)
/// Parse a character other than the specified one
let notChar ch = sat ((<>) ch)

/// Parse one or more repetitions of parser 'p'
let rec some p = parse {
  let! x = p
  let! xs = many p
  return x::xs }

/// Parse zero or more repetitions of parser 'p'
and many p = parse {
  return! some p
  return! unit [] }

The definition of map uses only Bind and Return. The definition of sat also uses Zero (it is inserted automatically in place of the else branch). The some combinator calls two parsers in sequence and then returns, so it also does not need any primitives beyond Bind and Return. Finally, the many combinator uses Combine to represent choice between the two parsers.

Parsing brackets

As our initial example, we use the previous parser combinators and the parse computation builder to write a parser that recognizes bracketed text. For example, given a text "(((hello)))" we would like to get just the string "hello". The following listing shows an initial attempt:

/// Parse any number of 'op' chars, followed by the
/// body and then the same number of 'cl' chars.
let rec brackets op cl body = parse {
  let! _ = char op
  let! inner = 
    parse { return! brackets op cl body
            return! body }
  let! _ = char cl
  return inner }

/// Returns the body of a bracketed string
let skipBrackets = brackets '(' ')' (many item)

/// Helper function that converts char list to string
let charsToString l = System.String(Array.ofSeq l)

// Run this line to see the results
run (map charsToString skipBrackets) "(((hello)))"

If you run the last line of the listing, you get a list containing "hello", but also "(hello)" and "((hello))". This is because the many item parser can also consume brackets. To correct that, we need to write a parser that accepts any character except opening and closing brace. As we will see shortly, this can be elegantly solved using joinads and the merge operation. The next section adds the required structure and finishes the example.

Adding the joinad structure

In order to support the match! syntax, we need to add operation Merge of type M<'T1> * M<'T2> -> M<'T1 * T2> and an operation Choose of type M<'T> * M<'T> -> M<'T>. The first operation is sometimes also called parallel composition, so what could that mean for parsers? One possible implementation is to run two parsers specified as arguments at the same input and return both of their results. The snippet below shows the source code.

The second operation represents a choice between two parsers. In order to obey laws about joinad operations (to keep the familiar behaviour of pattern matching), the operation cannot be implemented using plus. When called with p and map f p as arguments, it should behave as the parser specified as the first argument. This can be done by returning the result of a first parser that does not fail (i.e. returns a non-empty sequence):

/// Apply both parsers on the same input 'in parallel'
let merge (Parser p1) (Parser p2) = Parser (fun input ->
  seq { for (a, n1, tail1) in p1 input do
          for (b, n2, tail2) in p2 input do
            if n1 = n2 then yield (a, b), n1, tail1 })

/// Run both parsers and return the results of the first
/// one that does not return empty sequence.
let choose (Parser p1) (Parser p2) = Parser (fun input ->
  match p1 input, p2 input with
  | res, _  when not (Seq.isEmpty res) -> res
  | _, res -> res )

/// Add operations to the F# computation builder
type ParseBuilder with ...

The parser created by merge independently parses the input string using both of the parsers. It uses sequence comprehensions to find all combinations of results such that the number of characters consumed by the two parsers was the same. For each matching combination, the parser returns a tuple with the two parsing results. Requiring that the two parsers consume the same number of characters is not an arbitrary decision. It means that the remaining unconsumed strings tail1 and tail2 are the same and so we can return either of them.

Parsing brackets, again

Let's get back to the example with parsing brackets. The following snippet uses match! to create a parser that consumes all brackets. The trick is to write a parser body that represent any character which is not opening or closing bracket:

let skipAllBrackets = 
  let body = parse {
    match! notChar '(', notChar ')' with
    | c, _ -> return c }
  brackets '(' ')' (many body)

run (map charsToString skipAllBrackets) "(((hello)))"

When you run the last line of the sample, you can see that only "hello" is returned as the result. The parser body is constructed using the match! notation. It takes two notChar parsers as the arguments and runs them both on the same input. They boty read a single character and succeed when the character is not the specified symbol. This means that body succeds only if the character is not '(' and ')'. Both parsers return the same character, so we return the first one as the result and ignore the second (the _ pattern means that the parser must succeed, but we then ignore the value).

Validating phone numbers

Another example where the match! syntax for parsers is useful is validation of inputs. For example, a valid Cambridge phone number consists of 10 symbols, contains only digits, and starts with 1223. Using a couple of additional helper functions, we can directly encode these three rules using match!:

/// Run the parser 'p' specified number of times
let rec replicate n p = (...)
/// Parse string 'str' and then accept any further text
let rec startsWith str = (...)

/// Returns the input if it is valid Cambridge phone number
let cambridgePhone = parse {
  match! many (sat Char.IsDigit), replicate 10 item, startsWith "1223" with
  | n, _, _ -> return n }

// Run this line to test a number
run cambridgePhone "1223999999"
run cambridgePhone "1865999999"

Each condition on the number is encoded as a single parser. The first one ensures that all characters of the input are digits. The second parser checks that the input consits of 10 symbols and the last parser ensures that the input starts with the prefix "1223". The single clause of the match! construct is translated to applications of the Merge operation, which runs all three parsers on the same input and returns the parsed values only when all three succeed - meaning that the input satisifies all three conditions.

If you run the parser on the two sample inputs, the first line should succeed (the number is valid Cambridge phone number), but the second one fails. The prefix "1865" is used in the Oxford area!

To support Oxford in our sample, we can utilize the Choose operation. The operation is used when match! consists of multiple clauses. When we add additional clauses, the result of the first parser that succeeds is returned. The following snippet shows an example:

/// Recognize phone number based on the prefix
let phone = parse {
  match! many (sat Char.IsDigit), replicate 10 item, 
         startsWith "1223", startsWith "1865" with
  | n, _, _, ? -> return "Cambridge: " + string n
  | n, _, ?, _ -> return "Oxford: " + string n 
  | n, _, ?, ? -> return "Other: " + string n }

// Run the parser on sample inputs
run phone "1223999999"
run phone "1865999999"
run phone "1111999999"

The match! construct now takes four arguments. The first two are parsers that ensure that the input consists of just digits and has 10 characters, respectively. The next two parsers check for prefixes "1223" and "1865". The last two parsers will never both match on the same input, so a clause that would try to obtain a value from both of them would never succeed. However, we can write other useful clauses.

All of the three clauses in the above sample require the first two parsers to succeed. If the third parser also succeeds, the first clause matches and the number is identified as a Cambridge number. The second line is similar and recognizes Oxford numbers. Finally, the last line ignores both of the startsWith parsers.

One expected property of pattern matching is that only a single clause will be executed. Joinad definitions that obey the laws also have this property. For parsers, the choose operation gives the required behaviour - when a number is identified as Cambridge or Oxford number, the parser does not return Other as a possible result, even though the parser would also succed. This is because choose returns only results of a single parser (unlike plus which combines all successful results).

Summary

This article shows that joinads and the match! construct have uses outside of the concurrent and programming domains. In particular, it is possible to implement joinad operations for parsers. The Merge operation creates a parser that runs two parsers on the same input and the Choose operation creates a parser that returns results of exactly one of the specified parsers (meaning a choice without backtracking). The Merge operation is particularly interesting, because it gives a way to write intersection of languages recognized by two parsers.

Multiple items
union case Parser.Parser: (char list -> seq<'T * int * char list>) -> Parser<'T>

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

Full name: TryJoinads.Parser<_>
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
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
namespace System
val item : Parser<char>

Full name: TryJoinads.item
Multiple items
val seq : seq<'T> -> seq<'T>

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

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

Full name: Microsoft.FSharp.Collections.seq<_>
  type: seq<'T>
  inherits: Collections.IEnumerable
val x : char
  type: char
  inherits: ValueType
val xs : char list
  type: char list
val run : Parser<'a> -> seq<char> -> seq<'a>

Full name: TryJoinads.run
val p : (char list -> seq<'a * int * char list>)
val input : seq<char>
  type: seq<char>
  inherits: Collections.IEnumerable
val result : 'a
val tail : char list
  type: char list
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of 'T * 'T list
  with
    interface Collections.IEnumerable
    interface Collections.Generic.IEnumerable<'T>
    member Head : '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
Multiple items
val unit : 'a -> Parser<'a>

Full name: TryJoinads.unit


 Parser that always succeeds without consuming any input


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

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

Full name: TryJoinads.bind


 Apply the first parser and then continue using 'f'
val f : ('a -> Parser<'b>)
val p1 : (char list -> seq<'a * int * char list>)
val a : 'a
val n1 : int
  type: int
  inherits: ValueType
val input' : char list
  type: char list
val p2 : (char list -> seq<'b * int * char list>)
val result : 'b
val n2 : int
  type: int
  inherits: ValueType
val zero : Parser<'a>

Full name: TryJoinads.zero


 Parser that alwyas fails without consuming any input
val plus : Parser<'a> -> Parser<'a> -> Parser<'a>

Full name: TryJoinads.plus


 Combine the results of two parsers
val p2 : (char list -> seq<'a * int * char list>)
module Seq

from Microsoft.FSharp.Collections
val concat : seq<#seq<'T>> -> seq<'T>

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

Full name: TryJoinads.ParseBuilder


 Computation expression builder for creating parsers
member x.Bind(v, f) = bind f v
  member x.Return(v) = unit v
  member x.ReturnFrom(v) = v

  member x.Combine(a, f) = plus a (f())
  member x.Zero() = zero

  member x.Delay(f) = f
  member x.Run(f) = f()
val parse : ParseBuilder

Full name: TryJoinads.parse
val map : ('a -> 'b) -> Parser<'a> -> Parser<'b>

Full name: TryJoinads.map


 Apply function 'f' to the parsed value
val f : ('a -> 'b)
val p : Parser<'a>
val sat : (char -> bool) -> Parser<char>

Full name: TryJoinads.sat


 Succeeds only when a character matches given predicate
val pred : (char -> bool)
val ch : char
  type: char
  inherits: ValueType
Multiple items
val char : char -> Parser<char>

Full name: TryJoinads.char


 Parse a specific character


--------------------
type char = Char

Full name: Microsoft.FSharp.Core.char
  type: char
  inherits: ValueType
val notChar : char -> Parser<char>

Full name: TryJoinads.notChar


 Parse a character other than the specified one
val some : Parser<'a> -> Parser<'a list>

Full name: TryJoinads.some


 Parse one or more repetitions of parser 'p'
val x : 'a
val xs : 'a list
  type: 'a list
val many : Parser<'a> -> Parser<'a list>

Full name: TryJoinads.many


 Parse zero or more repetitions of parser 'p'
val brackets : char -> char -> Parser<'a> -> Parser<'a>

Full name: TryJoinads.brackets


 Parse any number of 'op' chars, followed by the
 body and then the same number of 'cl' chars.
val op : char
  type: char
  inherits: ValueType
val cl : char
  type: char
  inherits: ValueType
val body : Parser<'a>
val inner : 'a
val skipBrackets : Parser<char list>

Full name: TryJoinads.skipBrackets


 Returns the body of a bracketed string
val charsToString : seq<char> -> String

Full name: TryJoinads.charsToString


 Helper function that converts char list to string
val l : seq<char>
  type: seq<char>
  inherits: Collections.IEnumerable
type String =
  class
    new : char -> string
    new : System.SByte -> string
    new : char [] * int * int -> string
    new : char [] -> string
    new : char * int -> string
    member Chars : int -> char
    member CompareTo : obj -> int
    member CompareTo : string -> int
    member Contains : string -> bool
    member CopyTo : int * char [] * int * int -> unit
    member EndsWith : string -> bool
    member EndsWith : string * System.StringComparison -> bool
    member Equals : obj -> bool
    member Equals : string -> bool
    member Equals : string * System.StringComparison -> bool
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> System.TypeCode
    member IndexOf : char -> int
    member IndexOf : string -> int
    member IndexOf : char * int -> int
    member IndexOf : string * int -> int
    member IndexOf : string * System.StringComparison -> int
    member IndexOf : char * int * int -> int
    member IndexOf : string * int * int -> int
    member IndexOf : string * int * System.StringComparison -> int
    member IndexOf : string * int * int * System.StringComparison -> int
    member IndexOfAny : char [] -> int
    member IndexOfAny : char [] * int -> int
    member IndexOfAny : char [] * int * int -> int
    member Insert : int * string -> string
    member LastIndexOf : char -> int
    member LastIndexOf : string -> int
    member LastIndexOf : char * int -> int
    member LastIndexOf : string * int -> int
    member LastIndexOf : string * System.StringComparison -> int
    member LastIndexOf : char * int * int -> int
    member LastIndexOf : string * int * int -> int
    member LastIndexOf : string * int * System.StringComparison -> int
    member LastIndexOf : string * int * int * System.StringComparison -> int
    member LastIndexOfAny : char [] -> int
    member LastIndexOfAny : char [] * int -> int
    member LastIndexOfAny : char [] * int * int -> int
    member Length : int
    member PadLeft : int -> string
    member PadLeft : int * char -> string
    member PadRight : int -> string
    member PadRight : int * char -> string
    member Remove : int -> string
    member Remove : int * int -> string
    member Replace : char * char -> string
    member Replace : string * string -> string
    member Split : char [] -> string []
    member Split : char [] * System.StringSplitOptions -> string []
    member Split : string [] * System.StringSplitOptions -> string []
    member StartsWith : string -> bool
    member StartsWith : string * System.StringComparison -> bool
    member Substring : int -> string
    member Substring : int * int -> string
    member ToCharArray : unit -> char []
    member ToLower : unit -> string
    member ToLower : System.Globalization.CultureInfo -> string
    member ToLowerInvariant : unit -> string
    member ToString : unit -> string
    member ToString : System.IFormatProvider -> string
    member ToUpper : unit -> string
    member ToUpper : System.Globalization.CultureInfo -> string
    member ToUpperInvariant : unit -> string
    member Trim : unit -> string
    member Trim : char [] -> string
    member TrimEnd : char [] -> string
    member TrimStart : char [] -> string
    static val Empty : string
    static member Compare : string * string -> int
    static member Compare : string * string * System.StringComparison -> int
    static member Compare : string * string * System.Globalization.CultureInfo * System.Globalization.CompareOptions -> int
    static member Compare : string * int * string * int * int -> int
    static member Compare : string * int * string * int * int * System.StringComparison -> int
    static member Compare : string * int * string * int * int * System.Globalization.CultureInfo * System.Globalization.CompareOptions -> int
    static member CompareOrdinal : string * string -> int
    static member CompareOrdinal : string * int * string * int * int -> int
    static member Concat : obj -> string
    static member Concat : obj [] -> string
    static member Concat<'T> : System.Collections.Generic.IEnumerable<'T> -> string
    static member Concat : System.Collections.Generic.IEnumerable<string> -> string
    static member Concat : string [] -> string
    static member Concat : obj * obj -> string
    static member Concat : string * string -> string
    static member Concat : obj * obj * obj -> string
    static member Concat : string * string * string -> string
    static member Concat : string * string * string * string -> string
    static member Copy : string -> string
    static member Equals : string * string -> bool
    static member Equals : string * string * System.StringComparison -> bool
    static member Format : string * obj -> string
    static member Format : string * obj [] -> string
    static member Format : string * obj * obj -> string
    static member Format : System.IFormatProvider * string * obj [] -> string
    static member Format : string * obj * obj * obj -> string
    static member Intern : string -> string
    static member IsInterned : string -> string
    static member IsNullOrEmpty : string -> bool
    static member IsNullOrWhiteSpace : string -> bool
    static member Join : string * string [] -> string
    static member Join : string * obj [] -> string
    static member Join<'T> : string * System.Collections.Generic.IEnumerable<'T> -> string
    static member Join : string * System.Collections.Generic.IEnumerable<string> -> string
    static member Join : string * string [] * int * int -> string
  end

Full name: System.String
  type: String
type Array =
  class
    member Clone : unit -> obj
    member CopyTo : System.Array * int -> unit
    member GetEnumerator : unit -> System.Collections.IEnumerator
    member GetLength : int -> int
    member GetLowerBound : int -> int
    member GetUpperBound : int -> int
    member GetValue : int [] -> obj
    member GetValue : int -> obj
    member Initialize : unit -> unit
    member IsFixedSize : bool
    member IsReadOnly : bool
    member IsSynchronized : bool
    member Length : int
    member Rank : int
    member SetValue : obj * int -> unit
    member SetValue : obj * int [] -> unit
    member SyncRoot : obj
    static member AsReadOnly<'T> : 'T [] -> System.Collections.ObjectModel.ReadOnlyCollection<'T>
    static member BinarySearch : System.Array * obj -> int
    static member BinarySearch<'T> : 'T [] * 'T -> int
    static member BinarySearch<'T> : 'T [] * 'T * System.Collections.Generic.IComparer<'T> -> int
    static member BinarySearch<'T> : 'T [] * int * int * 'T -> int
    static member BinarySearch : System.Array * int * int * obj * System.Collections.IComparer -> int
    static member BinarySearch<'T> : 'T [] * int * int * 'T * System.Collections.Generic.IComparer<'T> -> int
    static member Clear : System.Array * int * int -> unit
    static member ConstrainedCopy : System.Array * int * System.Array * int * int -> unit
    static member Copy : System.Array * System.Array * int -> unit
    static member Copy : System.Array * int * System.Array * int * int -> unit
    static member CreateInstance : System.Type * int -> System.Array
    static member CreateInstance : System.Type * int [] -> System.Array
    static member ForEach<'T> : 'T [] * System.Action<'T> -> unit
    static member IndexOf<'T> : 'T [] * 'T -> int
    static member IndexOf<'T> : 'T [] * 'T * int -> int
    static member IndexOf : System.Array * obj * int * int -> int
    static member IndexOf<'T> : 'T [] * 'T * int * int -> int
    static member LastIndexOf<'T> : 'T [] * 'T -> int
    static member LastIndexOf<'T> : 'T [] * 'T * int -> int
    static member LastIndexOf : System.Array * obj * int * int -> int
    static member LastIndexOf<'T> : 'T [] * 'T * int * int -> int
    static member Resize<'T> : 'T [] * int -> unit
    static member Reverse : System.Array -> unit
    static member Reverse : System.Array * int * int -> unit
    static member Sort : System.Array -> unit
    static member Sort<'T> : 'T [] -> unit
    static member Sort : System.Array * System.Collections.IComparer -> unit
    static member Sort<'TKey,'TValue> : 'TKey [] * 'TValue [] -> unit
    static member Sort<'T> : 'T [] * System.Collections.Generic.IComparer<'T> -> unit
    static member Sort<'T> : 'T [] * System.Comparison<'T> -> unit
    static member Sort : System.Array * System.Array * System.Collections.IComparer -> unit
    static member Sort<'T> : 'T [] * int * int -> unit
    static member Sort<'TKey,'TValue> : 'TKey [] * 'TValue [] * System.Collections.Generic.IComparer<'TKey> -> unit
    static member Sort : System.Array * int * int * System.Collections.IComparer -> unit
    static member Sort<'TKey,'TValue> : 'TKey [] * 'TValue [] * int * int -> unit
    static member Sort<'T> : 'T [] * int * int * System.Collections.Generic.IComparer<'T> -> unit
    static member Sort : System.Array * System.Array * int * int * System.Collections.IComparer -> unit
    static member Sort<'TKey,'TValue> : 'TKey [] * 'TValue [] * int * int * System.Collections.Generic.IComparer<'TKey> -> unit
  end

Full name: System.Array
  type: Array
val ofSeq : seq<'T> -> 'T []

Full name: Microsoft.FSharp.Collections.Array.ofSeq
val merge : Parser<'a> -> Parser<'b> -> Parser<'a * 'b>

Full name: TryJoinads.merge


 Apply both parsers on the same input 'in parallel'
val tail1 : char list
  type: char list
val b : 'b
val tail2 : char list
  type: char list
val choose : Parser<'a> -> Parser<'a> -> Parser<'a>

Full name: TryJoinads.choose


 Run both parsers and return the results of the first
 one that does not return empty sequence.
val res : seq<'a * int * char list>
  type: seq<'a * int * char list>
  inherits: Collections.IEnumerable
val not : bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not
val isEmpty : seq<'T> -> bool

Full name: Microsoft.FSharp.Collections.Seq.isEmpty
member x.Merge(a, b) = merge a b
  member x.Choose(a, b) = choose a b
val skipAllBrackets : Parser<char list>

Full name: TryJoinads.skipAllBrackets
val body : Parser<char>
val c : char
  type: char
  inherits: ValueType
val replicate : int -> Parser<'a> -> Parser<'a list>

Full name: TryJoinads.replicate


 Run the parser 'p' specified number of times
val n : int
  type: int
  inherits: ValueType
parse {
  let! x = p
  if n = 1 then
    return [x]
  else
    let! xs = replicate (n - 1) p
    return x::xs }
val startsWith : string -> Parser<char list>

Full name: TryJoinads.startsWith


 Parse string 'str' and then accept any further text
val str : string
  type: string
parse {
  if str = "" then
    return! many item
  else
    let! _ = char str.[0]
    return! startsWith (str.Substring(1)) }
val cambridgePhone : Parser<char list>

Full name: TryJoinads.cambridgePhone


 Returns the input if it is valid Cambridge phone number
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: Char
  inherits: ValueType
Char.IsDigit(c: char) : bool
Char.IsDigit(s: string, index: int) : bool
val n : char list
  type: char list
val phone : Parser<string>

Full name: TryJoinads.phone


 Recognize phone number based on the prefix
Multiple items
val string : 'T -> string

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

--------------------
type string = String

Full name: Microsoft.FSharp.Core.string
  type: string