TP

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.

Note: This blog post is a re-publication of a tutorial from the TryJoinads.org web page. If you read the article there, you can run the examples interactively and experiment with them: view the article on TryJoinads.

## 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.

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.

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: Blog.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: Blog.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: Blog.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 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: Blog.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: Blog.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: Blog.zero

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

Full name: Blog.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: Blog.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: Blog.parse
val map : ('a -> 'b) -> Parser<'a> -> Parser<'b>

Full name: Blog.map

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

Full name: Blog.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: Blog.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: Blog.notChar

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

Full name: Blog.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: Blog.many

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

Full name: Blog.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: Blog.skipBrackets

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

Full name: Blog.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 IsSynchronized : bool
member Length : int
member Rank : int
member SetValue : obj * int -> unit
member SetValue : obj * int [] -> unit
member SyncRoot : obj
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: Blog.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: Blog.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: Blog.skipAllBrackets
val body : Parser<char>
val c : char
type: char
inherits: ValueType
val replicate : int -> Parser<'a> -> Parser<'a list>

Full name: Blog.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: Blog.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: Blog.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: Blog.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

Published: Wednesday, 21 March 2012, 4:27 PM
Author: Tomas Petricek
Typos: Send me a pull request!