Parsing JSON the fun way: monadic parsers, records and type providers (Part 1)


Image it is late in the night, you have some JSON data on your hands that needs to be parsed, and all you have is the F# compiler… how would you go about parsing it? I was in that situation the other night and was faced with two options: rely on the well tested .NET libraries or venture myself into magical woods of monadic parsing. I ended up going with the fun option!

The boring parsing approach…

The “boring” way of parsing JSON is, as expected, the simplest approach: you just need to define a Record that will hold the parsed data, decorate it with DataContract/DataMember attributes, and use the DataContractJsonSerializer class from the System.Runtime.Serialization.Json namespace to deserialize your JSON string into an F# Record. For example, enter the following snippet in F# Interactive and you will get a nice “Person” object from the JSON string.

 1: #r "System.Runtime.Serialization.dll"
 2: open System
 3: open System.IO
 4: open System.Runtime.Serialization
 5: open System.Text
 6: 
 7: [<DataContract>]
 8: type Person = {
 9:     [<field: DataMember(Name = "Name")>]
10:     Name : string
11:     [<field: DataMember(Name = "Phone")>]
12:     Phone : int
13: }
14: 
15: let jsonString = "{
16:  \"Name\": \"Fernando\",
17:  \"Phone\": 123456789
18:  }"
19: 
20: let js = Json.DataContractJsonSerializer(typeof<Person>)
21: let buffer = jsonString |> Encoding.UTF8.GetBytes
22: let person = js.ReadObject(new MemoryStream(buffer)) :?> Person
23: 
24: printfn "Name: %s, Phone number: %d" person.Name person.Phone
F# Web Snippets
namespace System
namespace System.IO
namespace System.Runtime
namespace System.Runtime.Serialization
namespace System.Text
type DataContractAttribute =
  class
    inherit System.Attribute
    new : unit -> System.Runtime.Serialization.DataContractAttribute
    member IsReference : bool with get, set
    member Name : string with get, set
    member Namespace : string with get, set
  end

Full name: System.Runtime.Serialization.DataContractAttribute

  type: DataContractAttribute
  implements: Runtime.InteropServices._Attribute
  inherits: Attribute

type Person =
  {Name: string;
   Phone: int;}

Full name: Untitled.Person

  type: Person
  implements: IEquatable<Person>
  implements: Collections.IStructuralEquatable
  implements: IComparable<Person>
  implements: IComparable
  implements: Collections.IStructuralComparable

type DataMemberAttribute =
  class
    inherit System.Attribute
    new : unit -> System.Runtime.Serialization.DataMemberAttribute
    member EmitDefaultValue : bool with get, set
    member IsRequired : bool with get, set
    member Name : string with get, set
    member Order : int with get, set
  end

Full name: System.Runtime.Serialization.DataMemberAttribute

  type: DataMemberAttribute
  implements: Runtime.InteropServices._Attribute
  inherits: Attribute

Person.Name: string
Multiple items
val string : ‘T -> string

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

——————–

type string = String

Full name: Microsoft.FSharp.Core.string

  type: string
  implements: IComparable
  implements: ICloneable
  implements: IConvertible
  implements: IComparable<string>
  implements: seq<char>
  implements: Collections.IEnumerable
  implements: IEquatable<string>

Person.Phone: int
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>
  implements: IComparable
  implements: IConvertible
  implements: IFormattable
  implements: IComparable<int<‘Measure>>
  implements: IEquatable<int<‘Measure>>
  inherits: ValueType

——————–

type int = int32

Full name: Microsoft.FSharp.Core.int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val jsonString : string

Full name: Untitled.jsonString

  type: string
  implements: IComparable
  implements: ICloneable
  implements: IConvertible
  implements: IComparable<string>
  implements: seq<char>
  implements: Collections.IEnumerable
  implements: IEquatable<string>

val js : Json.DataContractJsonSerializer

Full name: Untitled.js

  type: Json.DataContractJsonSerializer
  inherits: XmlObjectSerializer

namespace System.Runtime.Serialization.Json
type DataContractJsonSerializer =
  class
    inherit System.Runtime.Serialization.XmlObjectSerializer
    new : System.Type -> System.Runtime.Serialization.Json.DataContractJsonSerializer
    new : System.Type * string -> System.Runtime.Serialization.Json.DataContractJsonSerializer
    new : System.Type * System.Xml.XmlDictionaryString -> System.Runtime.Serialization.Json.DataContractJsonSerializer
    new : System.Type * System.Collections.Generic.IEnumerable<System.Type> -> System.Runtime.Serialization.Json.DataContractJsonSerializer
    new : System.Type * string * System.Collections.Generic.IEnumerable<System.Type> -> System.Runtime.Serialization.Json.DataContractJsonSerializer
    new : System.Type * System.Xml.XmlDictionaryString * System.Collections.Generic.IEnumerable<System.Type> -> System.Runtime.Serialization.Json.DataContractJsonSerializer
    new : System.Type * System.Collections.Generic.IEnumerable<System.Type> * int * bool * System.Runtime.Serialization.IDataContractSurrogate * bool -> System.Runtime.Serialization.Json.DataContractJsonSerializer
    new : System.Type * string * System.Collections.Generic.IEnumerable<System.Type> * int * bool * System.Runtime.Serialization.IDataContractSurrogate * bool -> System.Runtime.Serialization.Json.DataContractJsonSerializer
    new : System.Type * System.Xml.XmlDictionaryString * System.Collections.Generic.IEnumerable<System.Type> * int * bool * System.Runtime.Serialization.IDataContractSurrogate * bool -> System.Runtime.Serialization.Json.DataContractJsonSerializer
    member DataContractSurrogate : System.Runtime.Serialization.IDataContractSurrogate
    member IgnoreExtensionDataObject : bool
    member IsStartObject : System.Xml.XmlReader -> bool
    member IsStartObject : System.Xml.XmlDictionaryReader -> bool
    member KnownTypes : System.Collections.ObjectModel.ReadOnlyCollection<System.Type>
    member MaxItemsInObjectGraph : int
    member ReadObject : System.IO.Stream -> obj
    member ReadObject : System.Xml.XmlReader -> obj
    member ReadObject : System.Xml.XmlDictionaryReader -> obj
    member ReadObject : System.Xml.XmlReader * bool -> obj
    member ReadObject : System.Xml.XmlDictionaryReader * bool -> obj
    member WriteEndObject : System.Xml.XmlWriter -> unit
    member WriteEndObject : System.Xml.XmlDictionaryWriter -> unit
    member WriteObject : System.IO.Stream * obj -> unit
    member WriteObject : System.Xml.XmlWriter * obj -> unit
    member WriteObject : System.Xml.XmlDictionaryWriter * obj -> unit
    member WriteObjectContent : System.Xml.XmlWriter * obj -> unit
    member WriteObjectContent : System.Xml.XmlDictionaryWriter * obj -> unit
    member WriteStartObject : System.Xml.XmlWriter * obj -> unit
    member WriteStartObject : System.Xml.XmlDictionaryWriter * obj -> unit
  end

Full name: System.Runtime.Serialization.Json.DataContractJsonSerializer

  type: Json.DataContractJsonSerializer
  inherits: XmlObjectSerializer

val typeof<‘T> : Type

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

val buffer : byte []

Full name: Untitled.buffer

  type: byte []
  implements: ICloneable
  implements: Collections.IList
  implements: Collections.ICollection
  implements: Collections.IStructuralComparable
  implements: Collections.IStructuralEquatable
  implements: Collections.Generic.IList<byte>
  implements: Collections.Generic.ICollection<byte>
  implements: seq<byte>
  implements: Collections.IEnumerable
  inherits: Array

type Encoding =
  class
    member BodyName : string
    member Clone : unit -> obj
    member CodePage : int
    member DecoderFallback : System.Text.DecoderFallback with get, set
    member EncoderFallback : System.Text.EncoderFallback with get, set
    member EncodingName : string
    member Equals : obj -> bool
    member GetByteCount : char [] -> int
    member GetByteCount : string -> int
    member GetByteCount : char * int -> int
    member GetByteCount : char [] * int * int -> int
    member GetBytes : char [] -> System.Byte []
    member GetBytes : string -> System.Byte []
    member GetBytes : char [] * int * int -> System.Byte []
    member GetBytes : char * int * System.Byte * int -> int
    member GetBytes : char [] * int * int * System.Byte [] * int -> int
    member GetBytes : string * int * int * System.Byte [] * int -> int
    member GetCharCount : System.Byte [] -> int
    member GetCharCount : System.Byte * int -> int
    member GetCharCount : System.Byte [] * int * int -> int
    member GetChars : System.Byte [] -> char []
    member GetChars : System.Byte [] * int * int -> char []
    member GetChars : System.Byte * int * char * int -> int
    member GetChars : System.Byte [] * int * int * char [] * int -> int
    member GetDecoder : unit -> System.Text.Decoder
    member GetEncoder : unit -> System.Text.Encoder
    member GetHashCode : unit -> int
    member GetMaxByteCount : int -> int
    member GetMaxCharCount : int -> int
    member GetPreamble : unit -> System.Byte []
    member GetString : System.Byte [] -> string
    member GetString : System.Byte [] * int * int -> string
    member HeaderName : string
    member IsAlwaysNormalized : unit -> bool
    member IsAlwaysNormalized : System.Text.NormalizationForm -> bool
    member IsBrowserDisplay : bool
    member IsBrowserSave : bool
    member IsMailNewsDisplay : bool
    member IsMailNewsSave : bool
    member IsReadOnly : bool
    member IsSingleByte : bool
    member WebName : string
    member WindowsCodePage : int
    static member ASCII : System.Text.Encoding
    static member BigEndianUnicode : System.Text.Encoding
    static member Convert : System.Text.Encoding * System.Text.Encoding * System.Byte [] -> System.Byte []
    static member Convert : System.Text.Encoding * System.Text.Encoding * System.Byte [] * int * int -> System.Byte []
    static member Default : System.Text.Encoding
    static member GetEncoding : int -> System.Text.Encoding
    static member GetEncoding : string -> System.Text.Encoding
    static member GetEncoding : int * System.Text.EncoderFallback * System.Text.DecoderFallback -> System.Text.Encoding
    static member GetEncoding : string * System.Text.EncoderFallback * System.Text.DecoderFallback -> System.Text.Encoding
    static member GetEncodings : unit -> System.Text.EncodingInfo []
    static member UTF32 : System.Text.Encoding
    static member UTF7 : System.Text.Encoding
    static member UTF8 : System.Text.Encoding
    static member Unicode : System.Text.Encoding
  end

Full name: System.Text.Encoding

  type: Encoding
  implements: ICloneable

property Encoding.UTF8: Encoding
Multiple overloads
Encoding.GetBytes(s: string) : byte []
Encoding.GetBytes(chars: char []) : byte []
Encoding.GetBytes(chars: char [], index: int, count: int) : byte []
Encoding.GetBytes(chars: nativeptr<char>, charCount: int, bytes: nativeptr<byte>, byteCount: int) : int
Encoding.GetBytes(s: string, charIndex: int, charCount: int, bytes: byte [], byteIndex: int) : int
Encoding.GetBytes(chars: char [], charIndex: int, charCount: int, bytes: byte [], byteIndex: int) : int
val person : Person

Full name: Untitled.person

  type: Person
  implements: IEquatable<Person>
  implements: Collections.IStructuralEquatable
  implements: IComparable<Person>
  implements: IComparable
  implements: Collections.IStructuralComparable

Multiple overloads
XmlObjectSerializer.ReadObject(reader: Xml.XmlDictionaryReader) : obj
XmlObjectSerializer.ReadObject(reader: Xml.XmlReader) : obj
XmlObjectSerializer.ReadObject(stream: Stream) : obj
XmlObjectSerializer.ReadObject(reader: Xml.XmlDictionaryReader, verifyObjectName: bool) : obj
XmlObjectSerializer.ReadObject(reader: Xml.XmlReader, verifyObjectName: bool) : obj
type MemoryStream =
  class
    inherit System.IO.Stream
    new : unit -> System.IO.MemoryStream
    new : int -> System.IO.MemoryStream
    new : System.Byte [] -> System.IO.MemoryStream
    new : System.Byte [] * bool -> System.IO.MemoryStream
    new : System.Byte [] * int * int -> System.IO.MemoryStream
    new : System.Byte [] * int * int * bool -> System.IO.MemoryStream
    new : System.Byte [] * int * int * bool * bool -> System.IO.MemoryStream
    member CanRead : bool
    member CanSeek : bool
    member CanWrite : bool
    member Capacity : int with get, set
    member Flush : unit -> unit
    member GetBuffer : unit -> System.Byte []
    member Length : int64
    member Position : int64 with get, set
    member Read : System.Byte [] * int * int -> int
    member ReadByte : unit -> int
    member Seek : int64 * System.IO.SeekOrigin -> int64
    member SetLength : int64 -> unit
    member ToArray : unit -> System.Byte []
    member Write : System.Byte [] * int * int -> unit
    member WriteByte : System.Byte -> unit
    member WriteTo : System.IO.Stream -> unit
  end

Full name: System.IO.MemoryStream

  type: MemoryStream
  implements: IDisposable
  inherits: Stream
  inherits: MarshalByRefObject

val printfn : Printf.TextWriterFormat<‘T> -> ‘T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn

 

Quite simple, right? And you will have to agree with me that it is a little bit boring too…

Fun with monadic parsers

What is the fun option then? The fun way of parsing some JSON data (or any data format in fact) involves building your own parser from scratch! Better yet, building it from scratch by using Monadic Parsers! Believe me, it is a lot of fun: by the time I was done writing my parser, I had completely forgotten the reason I needed it in the first place.

The process is quite “easy”: (1) learn all about monads; (2) learn yourself some Haskell so you can understand the next step; (3) read Graham Hutton/Erik Meijer paper Monadic Parsing in Haskell; (4) port the Haskell code to F#; (5) compose the JSON parser using the parser combinators; (6) figure out a way to go from the JSON abstract syntax tree to a F# record, and finally (7) use your JSON data!

Step (1) may take from a few minutes to a few years, depending on how deep you want to dive into it; I am not even going to try to cover it here. Interestingly enough, it seems that everybody is talking about Monads these days and there is a bunch of good tutorials and papers out there – read them all. Monads are called Computation Expressions in F#, and for the purposes of this blog series, this WikiBooks entry should get you started on the main concepts: sequencing of computation/function composition and the syntactic sugar the F# compiler provides us to make life easier.

You should not, but if you prefer, you can actually skip steps (2), (3) and (4), and instead look around for code samples to get you up and running quickly. We will go through similar code on this and next posts, so stick around if you feel like it… However, before we get to the parser monads, let’s wobble through some code to get a glimpse of how they work under the covers.

Disclaimer: the parser we will build here is for education purposes only. If you plan on using monadic parsers in the wild, make sure to use a real one like FParsec, which is the F# port of Haskell’s Parsec library.

A simple hardcoded parser

The best Parser Monad definition I’ve found so far comes from Dr. Seuss (who would think he was a functional developer!):

A Parser for Things
is a function from Strings
to Lists of Pairs
of Things and Strings!

We could rewrite Dr. Seuss definition as:

A Thing Parser is a function that takes a String as a parameter, and returns a list of Tuples of Things and Strings.

It turns out that Dr. Seuss uses Haskell for his functional programming, and a Haskell String is just a type synonym for a list of characters. We could use System.String in our parsers, but to stick to Erik’s paper convention, let’s use F# char lists instead. The “Thing” in the definition above is just the type variable for the parser… using the F# type system notation, the definition above becomes:

‘a Parser : char list -> (‘a * char list) list

We will be converting strings to list of chars and vice-versa a lot, so let’s create a couple of simple helper functions:

let s2cs = List.ofSeq
let cs2s cs = new System.String(Array.ofList cs)

Pretend we have this programming language that accepts only one line of code: fun <char> = <single digit integer>. One can’t really do much programming with it, but it will be useful for our parser investigation. We can define its simple abstract syntax tree (AST) as:

// fun x = 1
type FunAST = 
    | Fun of (char * int)

 

Our task will be, for example, to parse “fun x = 1” and emit Fun(‘x’, 1).

Let’s start by building the simplest parser we can think of, a character parser: given a list of characters (a string), it must return a list containing a tuple with the first character and the remaining ones; it does not get more “building a parser from scratch” than this:

let charParser (chars : char list) = 
    match chars with
    | c::cs -> [(c, cs)]
    | [] -> []

 

F# being such a great language for writing clean/succinct code, and because functional developers love to write clean/succinct code, we can rewrite the function above simply as:

let cParser = function [] -> [] | c::cs -> [c, cs]

 

Hover your mouse over the function declaration and you will see that it complies with Dr. Seuss definition: val cParser: ‘a list -> (‘a * ‘a list) list! So here we go, our very first parser! Running it on F# Interactive gives us:

> “Test” |> s2cs |> cParser;;
val it : (char * char list) list = [(‘T’, [‘e’; ‘s’; ‘t’])]

> “T” |> s2cs |> cParser;;
val it : (char * char list) list = [(‘T’, [])]

> “” |> s2cs |> cParser;;
val it : (char * char list) list = []

Note that, no matter which string you feed this parser, it will return a tuple with the first character and the list of remaining ones, all that inside another list; except, of course, if you feed it the empty string, in which case it returns an empty list. It is important to notice the usage of an empty list here, as it represents an error, or the “end of the parsing computation” because the parser failed to parse the input string.

Think of this result list as a “container”: if it is empty, we are done parsing due to an error; if the result list if not empty, and the second element of the tuple is empty, we have successfully parsed the input string. If the list inside the tuple is not empty, we have successfully parsed part of the input string, but we still have more text to parse.

By the way, we can use List.head to extract the content of our result list:

> “Test” |> s2cs |> cParser |> List.head;;
val it : char * char list = (‘T’, [‘e’; ‘s’; ‘t’])

Back to our one-line programming language, how would we go about parsing “fun x = 1” using our char Parser above? If all our parser provides is a char at a time, we will need to parse a char, test it with the language specification, parse another one, test it, etc., etc., something like this:

let uglyParser cs = 
    let (c1, cs1) = cParser cs |> List.head
    if c1 = 'f' then
        let (c2, cs2) = cParser cs1 |> List.head
        if c2 = 'u' then
            let (c3, cs3) = cParser cs2 |> List.head
            if c3 = 'n' then 
                let (c4, cs4) = cParser cs3 |> List.head
                if c4 = ' ' then
                    let (c5, cs5) = cParser cs4 |> List.head
                    if c5 = c5 then
                        let (c6, cs6) = cParser cs5 |> List.head
                        if c6 = ' ' then
                            let (c7, cs7) = cParser cs6 |> List.head
                            if c7 = '=' then
                                let (c8, cs8) = cParser cs7 |> List.head
                                if c8 = ' ' then 
                                    let (c9, cs9) = cParser cs8 |> List.head
                                    if  Char.IsDigit c9 then
                                        let num = System.Int32.Parse(string c9)
                                        [Fun (c5, num), cs9]
                                    else []
                                else []
                            else []
                        else []
                    else []
                else []
            else []
        else []
    else []

 

If you hover your mouse over uglyParser, you will notice that it does comply with our parser definition, and if you run it on F# Interactive you will see that it actually works just fine… however it is as ugly as ugly can be!

> “fun x = 1” |> s2cs |> uglyParser;;
val it : (FunAST * char list) list = [(Fun (‘x’, 1), [])]

> “fail x = 1” |> s2cs |> uglyParser;;val it : (FunAST * char list) list = []

It is obvious we are repeating code again and again; we apply the char parser, run a function on the result (if c1 = ‘f’ then…) and return a new parser, we apply that new parser, run another function on the result and return yet another new parser, and so one. We are basically “sequencing” parsers manually; it would be great if we could write something like this instead:

continuationFunction(aResult) = process(aResult) and return(bParser)

sequenceFunction(aParser, continuationFunction) =

let (aResult, remaining) = sequence(aParser)
let bParser = continuationFunction aResult
bParser (remaining)

Analyzing the code pseudo-code above, we can try to infer the types of those two functions, remembering our parser type definition:

‘a Parser: char list -> (‘a * char list) list

the types of our functions above become:

continuationFunction: ‘a -> ‘b Parser
continuationFunction: ‘a -> (char list -> ‘b * char list) list

sequenceFunction: ‘a Parser * (‘a -> ‘b Parser) -> ‘b Parser
sequenceFunction: (char list -> (a * char list) list) * (‘a -> (char list -> ‘b * char list) list) -> (char list -> ‘b * char list) list

Our sequence function takes an ‘a Parser, a function that knows how to go from ‘a to a ‘b Parser and returns a ‘b Parser… Let’s write some real F# code:

let sequence (aParser:(char list -> ('a * char list) list), (continutationFunc : 'a -> (char list -> ('b * char list) list))) cs = 
    match aParser cs with
    | (c', cs')::_ -> 
        let bParser = continutationFunc c'
        bParser cs'
    | [] -> []

 

What?! Yes, kind of crazy, we upped the game a little bit here and things got slightly more complex, but if you stare at it long enough it will eventually make sense (or give you some headache). The implementation is actually quite simple, we apply the aParser on the input char list (cs), if there is a parsing error, we return the empty list, otherwise we apply the continuationFunc on the thing parsed (c’), which gives us the bParser, and finally we apply the bParser on the remaining char list (ohhh….).

I know we are not using monads yet, but just to get us closer to that, I’d like to rename and rewrite the sequence function above before using it. I will call it bind and use a different notation, by removing the cs from its declaration, to emphasize that bind returns a function (the behavior continues exactly the same):

let bind (p:(char list -> ('a * char list) list), (f : 'a -> (char list -> ('b * char list) list))) = 
    fun cs -> 
        match p cs with
        | (c', cs')::_ -> (f c') cs'
        | [] -> []

 

With this new notation, it easier to see that bind is returning a parser, which is the expected behavior: if I sequence, or bind, two parsers, the result has to be another parser, right? With bind in place, let’s write a parser that parses the token “fun” out of “fun x = 1” using it:

let uglyFunParser input = 
    bind (cParser, fun c1 ->
        if c1 = 'f' then
            bind(cParser, fun c2 ->
                if c2 = 'u' then
                    bind(cParser, fun c3 ->
                        if c3 = 'n' then
                            fun cs -> [Fun, cs]
                        else fun _ -> []
                    )
                else fun _ -> []
            )
        else fun _ -> []
    ) input

 

> “fun x = 1” |> s2cs |> uglyFunParser;;
val it : ((char * int -> FunAST) * char list) list =
  [(<fun:uglyFunParser@73-20>, [‘ ‘; ‘x’; ‘ ‘; ‘=’; ‘ ‘; ‘1’])]

It works perfectly, but still quite ugly… However, we now have in place the basis of sequencing those parsing computations. It is very important that you understand what’s going on here… we are using a lot of anonymous functions instead of explicitly declaring several continuationFuncs, and each of these anonymous functions binds, or sequences, another parser.

“What’s up with all those “fun _ -> []” and “fun cs -> [Fun, cs]”? Remember that any parser we build must comply with Dr. Seuss definition, they are functions that take a char list (cs) and return an empty list (error) or a list with the tuple (thing parsed * remaining char list); and that’s exactly what we are doing, in case of error we return a function that takes one parameter (but we don’t care about it, so we throw it away with the “_” notation), and returns the empty list (“fun _ -> []”), and in case of success we return “fun cs -> [(Fun, cs)]”, i.e., a function that takes a char list and returns the tuple (parsed thing (Fun), remaining chars).

These two anonymous functions are so important that we ought to build helper functions for them, let’s call them “returnParser” for the success case, and “zeroParser” for the case of parsing errors:

let returnParser something = fun cs -> [something, cs]
let zeroParser () = fun _ -> []

 

It is also time to get rid of the if-then-else madness of our ugly function! We will start by defining a “satisfy this predicate Parser”, the idea being, given a predicate function (‘a -> bool), it returns a parser which can only parse things where the predicate returns true – it is almost a direct copy-and-paste of one section of the funUglyParser above:

let satisfyParser pred = 
    bind(cParser, fun c ->
        if pred c then returnParser c else zeroParser()
    )
    //let (c', cs') = cParser cs |> List.head
    //if pred c' then [c', cs'] else []

 

Make sure to hover your mouse over it and confirm its type complies with our parser definition. With this new parser in place, let’s create an “only parse this specific character Parser”, and call it “tcParser” (as in “this char Parser”):

let tcParser c = satisfyParser ((=) c)

 

Kind of cool, no? Testing it:

> “fun x = 1” |> s2cs |> tcParser ‘f’;;
val it : (char * char list) list =
  [(‘f’, [‘u’; ‘n’; ‘ ‘; ‘x’; ‘ ‘; ‘=’; ‘ ‘; ‘1’])]

And it works… how about sequencing this little guy to improve our funParser?

let funParser (input: char list) = 
    let internalParser = 
        bind (tcParser 'f', fun _ ->
            bind (tcParser 'u', fun _ ->
                bind (tcParser 'n', fun _ ->
                    returnParser Fun
                )
            )
        )
    internalParser input

 

The input parameter is really not helping much here, by this time we all know that parsers take char lists as input, so let’s remove it:

let funParser' = 
    bind (tcParser 'f', fun _ ->
        bind (tcParser 'u', fun _ ->
            bind (tcParser 'n', fun _ ->
                returnParser Fun
            )
        )
    )

 

> “fun x = 1” |> s2cs |> funParser’;;
val it : ((char * int -> FunAST) * char list) list =
  [(<fun:funParser’@100-3>, [‘ ‘; ‘x’; ‘ ‘; ‘=’; ‘ ‘; ‘1’])]

> “fail x = 1” |> s2cs |> funParser’;;
val it : ((char * int -> FunAST) * char list) list = []

You have to agree again that this is much cleaner than our very first uglyParser. We are not even using the zeroParser anymore, since satisfyParser takes care of that for us. But we are now facing another pattern, sequencing the application of the tcParsers. Can we do better than that? Sure thing… let’s create a “parse this specific string Parser”:

let stringParser (tok:string) =
    let rec text = function
        | [] -> returnParser []
        | t::tok' -> 
            bind(tcParser t, fun _ ->
                bind(text tok', fun _ -> returnParser (t::tok') )
            )
    text (s2cs tok)

 

> “fun x = 1” |> s2cs |> stringParser “fun”;;
val it : (char list * char list) list =
  [([‘f’; ‘u’; ‘n’], [‘ ‘; ‘x’; ‘ ‘; ‘=’; ‘ ‘; ‘1’])]
> “fail x = 1” |> s2cs |> stringParser “fun”;;
val it : (char list * char list) list = []

Given a token (tok), we iterate through its characters, sequencing parsers that will parse that specific character (t). The result will be a parser (a function) that will parse a specific string out of the input string, or fail if it can’t parse the string. How would we use it in our funParser? We just sequence it…

let funParser'' = 
    bind(stringParser "fun", fun _ -> returnParser Fun)

 

Now we are talking! How about parsing the whole line “fun x = 1”? Let’s put together a few more “parser combinators” to help on that task… Every time we parse a token, we need to remove the white space after the token, so let’s build a “cleanSpaceParser” which will sequence a parser, sequence a “spaceParser”, throwing its result away, and return the result of the first parser (see below) – using cleanSpaceParser, we can now build our final parsers for our single line language:

let singleSpaceParser = tcParser ' ' 

let cleanSpaceParser p = 
    bind(p, fun r ->
        bind(singleSpaceParser, fun _ -> returnParser r)
    )

let finalFunParser = cleanSpaceParser funParser''

let identParser = cleanSpaceParser cParser

let equalParser = cleanSpaceParser <| tcParser '='

let digitParser = 
    bind(satisfyParser System.Char.IsDigit, 
        string >> System.Int32.Parse >> returnParser
    )

 

If we now put them all together, we end up with the parser for our language:

let funLangParser = 
    bind(finalFunParser, fun funFunc ->
        bind(identParser, fun identifier ->
            bind(equalParser, fun _ ->
                bind(digitParser, fun digit ->
                    returnParser (funFunc(identifier, digit))
                )
            )
        )
    )

 

Hover your mouse again over the code above to make sure you understand what’s going on! Does it make sense?

We can use a helper function to run the parser and return the results, for example:

let runParser s = 
    match funLangParser (s2cs s) with
    | [] -> failwith "Error parsing string"
    | (result,_)::_ -> result

 

> “fun x = 1” |> runParser;;
val it : FunAST = Fun (‘x’, 1)
> “fun y = 2” |> runParser;;
val it : FunAST = Fun (‘y’, 2)
> “fail x = 1” |> runParser;;
System.Exception: Error parsing string

It works (and looks way better than our first uglyParser)! We have just built a parser from scratch, congrats!

Wrapping up 

“Wow! That was a lot of code (and craziness) to just parse a single line of code”, you might be thinking. And yes, it was indeed; but as I mentioned, we now have the building blocks to create more powerful parsers, including the JSON parser we talked about at the beginning of this post.

We started with a single character parser based on Dr. Seuss definition, and through the “power” computation sequencing/composition, we built more and more capable parsers. The bind, zeroParser and returnParser functions were crucial on making the compositions easier, and the use of lists as the parser’s output provided a way to return both parsing success as well as end of computation due to an error.

The whole concept of functions being passed around can be a bit intimidating at first, especially if you are new to the functional lifestyle; F# Interactive can be a huge help in the learning process here. F# will also make things easier for us when we move to using computation expressions; for example, our funLangParse above could have been written as something like this:

let funLangParser =
 parser {
  let! funFunc = finalFunParser
  let! identifier = identParser
  let! _ = equalParser
  let! digit = digitParser
  return funFunc(identifier, digit)
 }

That is exactly what we will do next: wrap our parsers into computation expressions and then build the JSON parser. Later we will figure out ways to create F# types based on the AST generated by our parsers.

Stay tuned!

Homework

The cleanSpaces parser only parses a single white space out of the input string. Can you rewrite it to parse any number of spaces in a way that a line like this, “fun      z     =    7” would be successfully parsed?

Parsing JSON the fun way series

Part 1: Building a parser from scratch with Dr. Seuss help (part 1)
Part 2: Tricking you into Parser Monads (it’s not going to hurt, I promise)
Part 3: The JSON Parser Monad

 

namespace System
val s2cs : (seq<‘a> -> ‘a list)

Full name: WebSnippets.s2cs

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>
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<‘T>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<‘T>
  implements: Collections.IEnumerable

val ofSeq : seq<‘T> -> ‘T list

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

val cs2s : char list -> String

Full name: WebSnippets.cs2s

val cs : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

type String =
  class
    new : char -> string
    new : char * int * int -> string
    new : System.SByte -> string
    new : System.SByte * int * int -> string
    new : System.SByte * int * int * System.Text.Encoding -> string
    new : char [] * int * int -> string
    new : char [] -> string
    new : char * int -> string
    member Chars : int -> char
    member Clone : unit -> obj
    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 EndsWith : string * bool * System.Globalization.CultureInfo -> bool
    member Equals : obj -> bool
    member Equals : string -> bool
    member Equals : string * System.StringComparison -> bool
    member GetEnumerator : unit -> System.CharEnumerator
    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 IsNormalized : unit -> bool
    member IsNormalized : System.Text.NormalizationForm -> bool
    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 Normalize : unit -> string
    member Normalize : System.Text.NormalizationForm -> string
    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 [] * int -> string []
    member Split : char [] * System.StringSplitOptions -> string []
    member Split : string [] * System.StringSplitOptions -> string []
    member Split : char [] * int * System.StringSplitOptions -> string []
    member Split : string [] * int * System.StringSplitOptions -> string []
    member StartsWith : string -> bool
    member StartsWith : string * System.StringComparison -> bool
    member StartsWith : string * bool * System.Globalization.CultureInfo -> bool
    member Substring : int -> string
    member Substring : int * int -> string
    member ToCharArray : unit -> char []
    member ToCharArray : int * int -> 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 * bool -> 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 * string * bool * System.Globalization.CultureInfo -> int
    static member Compare : string * int * string * int * int -> int
    static member Compare : string * int * string * int * int * bool -> int
    static member Compare : string * int * string * int * int * System.StringComparison -> int
    static member Compare : string * int * string * int * int * bool * System.Globalization.CultureInfo -> 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 : obj * obj * obj * obj -> 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
  implements: IComparable
  implements: ICloneable
  implements: IConvertible
  implements: IComparable<string>
  implements: seq<char>
  implements: Collections.IEnumerable
  implements: IEquatable<string>

type Array =
  class
    member Clone : unit -> obj
    member CopyTo : System.Array * int -> unit
    member CopyTo : System.Array * int64 -> unit
    member GetEnumerator : unit -> System.Collections.IEnumerator
    member GetLength : int -> int
    member GetLongLength : int -> int64
    member GetLowerBound : int -> int
    member GetUpperBound : int -> int
    member GetValue : int [] -> obj
    member GetValue : int -> obj
    member GetValue : int64 -> obj
    member GetValue : int64 [] -> obj
    member GetValue : int * int -> obj
    member GetValue : int64 * int64 -> obj
    member GetValue : int * int * int -> obj
    member GetValue : int64 * int64 * int64 -> obj
    member Initialize : unit -> unit
    member IsFixedSize : bool
    member IsReadOnly : bool
    member IsSynchronized : bool
    member Length : int
    member LongLength : int64
    member Rank : int
    member SetValue : obj * int -> unit
    member SetValue : obj * int [] -> unit
    member SetValue : obj * int64 -> unit
    member SetValue : obj * int64 [] -> unit
    member SetValue : obj * int * int -> unit
    member SetValue : obj * int64 * int64 -> unit
    member SetValue : obj * int * int * int -> unit
    member SetValue : obj * int64 * int64 * int64 -> 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 : System.Array * obj * System.Collections.IComparer -> int
    static member BinarySearch<‘T> : ‘T [] * ‘T * System.Collections.Generic.IComparer<‘T> -> int
    static member BinarySearch : System.Array * int * int * obj -> 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 ConvertAll<‘TInput,’TOutput> : ‘TInput [] * System.Converter<‘TInput,’TOutput> -> ‘TOutput []
    static member Copy : System.Array * System.Array * int -> unit
    static member Copy : System.Array * System.Array * int64 -> unit
    static member Copy : System.Array * int * System.Array * int * int -> unit
    static member Copy : System.Array * int64 * System.Array * int64 * int64 -> unit
    static member CreateInstance : System.Type * int -> System.Array
    static member CreateInstance : System.Type * int [] -> System.Array
    static member CreateInstance : System.Type * int64 [] -> System.Array
    static member CreateInstance : System.Type * int * int -> System.Array
    static member CreateInstance : System.Type * int [] * int [] -> System.Array
    static member CreateInstance : System.Type * int * int * int -> System.Array
    static member Exists<‘T> : ‘T [] * System.Predicate<‘T> -> bool
    static member Find<‘T> : ‘T [] * System.Predicate<‘T> -> ‘T
    static member FindAll<‘T> : ‘T [] * System.Predicate<‘T> -> ‘T []
    static member FindIndex<‘T> : ‘T [] * System.Predicate<‘T> -> int
    static member FindIndex<‘T> : ‘T [] * int * System.Predicate<‘T> -> int
    static member FindIndex<‘T> : ‘T [] * int * int * System.Predicate<‘T> -> int
    static member FindLast<‘T> : ‘T [] * System.Predicate<‘T> -> ‘T
    static member FindLastIndex<‘T> : ‘T [] * System.Predicate<‘T> -> int
    static member FindLastIndex<‘T> : ‘T [] * int * System.Predicate<‘T> -> int
    static member FindLastIndex<‘T> : ‘T [] * int * int * System.Predicate<‘T> -> int
    static member ForEach<‘T> : ‘T [] * System.Action<‘T> -> unit
    static member IndexOf : System.Array * obj -> int
    static member IndexOf<‘T> : ‘T [] * ‘T -> int
    static member IndexOf : System.Array * obj * int -> 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 : System.Array * obj -> int
    static member LastIndexOf<‘T> : ‘T [] * ‘T -> int
    static member LastIndexOf : System.Array * obj * int -> 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.Array -> 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 * int * int -> 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 * System.Array * int * int -> 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
    static member TrueForAll<‘T> : ‘T [] * System.Predicate<‘T> -> bool
  end

Full name: System.Array

  type: Array
  implements: ICloneable
  implements: Collections.IList
  implements: Collections.ICollection
  implements: Collections.IEnumerable
  implements: Collections.IStructuralComparable
  implements: Collections.IStructuralEquatable

val ofList : ‘T list -> ‘T []

Full name: Microsoft.FSharp.Collections.Array.ofList

type FunAST = | Fun of (char * int)

Full name: WebSnippets.FunAST

  type: FunAST
  implements: IEquatable<FunAST>
  implements: Collections.IStructuralEquatable
  implements: IComparable<FunAST>
  implements: IComparable
  implements: Collections.IStructuralComparable

union case FunAST.Fun: char * int -> FunAST
Multiple items
val char : ‘T -> char (requires member op_Explicit)

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

——————–

type char = Char

Full name: Microsoft.FSharp.Core.char

  type: char
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

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>
  implements: IComparable
  implements: IConvertible
  implements: IFormattable
  implements: IComparable<int<‘Measure>>
  implements: IEquatable<int<‘Measure>>
  inherits: ValueType

——————–

type int = int32

Full name: Microsoft.FSharp.Core.int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val charParser : char list -> (char * char list) list

Full name: WebSnippets.charParser

val chars : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

type ‘T list = List<‘T>

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

  type: ‘T list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<‘T>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<‘T>
  implements: Collections.IEnumerable

val c : char

  type: char
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

val cParser : ‘a list -> (‘a * ‘a list) list

Full name: WebSnippets.cParser

val c : ‘a
val cs : ‘a list

  type: ‘a list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<‘a>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<‘a>
  implements: Collections.IEnumerable

val uglyParser : char list -> (FunAST * char list) list

Full name: WebSnippets.uglyParser

val c1 : char

  type: char
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

val cs1 : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

val head : ‘T list -> ‘T

Full name: Microsoft.FSharp.Collections.List.head

val c2 : char

  type: char
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

val cs2 : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

val c3 : char

  type: char
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

val cs3 : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

val c4 : char

  type: char
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

val cs4 : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

val c5 : char

  type: char
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

val cs5 : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

val c6 : char

  type: char
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

val cs6 : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

val c7 : char

  type: char
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

val cs7 : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

val c8 : char

  type: char
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

val cs8 : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

val c9 : char

  type: char
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

val cs9 : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

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 ConvertFromUtf32 : int -> string
    static member ConvertToUtf32 : char * char -> int
    static member ConvertToUtf32 : string * int -> int
    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 IsHighSurrogate : char -> bool
    static member IsHighSurrogate : 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 IsLowSurrogate : char -> bool
    static member IsLowSurrogate : 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 Parse : string -> char
    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
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

Multiple overloads
Char.IsDigit(c: char) : bool
Char.IsDigit(s: string, index: int) : bool
val num : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

type Int32 =
  struct
    member CompareTo : obj -> int
    member CompareTo : int -> int
    member Equals : obj -> bool
    member Equals : int -> bool
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> System.TypeCode
    member ToString : unit -> string
    member ToString : string -> string
    member ToString : System.IFormatProvider -> string
    member ToString : string * System.IFormatProvider -> string
    static val MaxValue : int
    static val MinValue : int
    static member Parse : string -> int
    static member Parse : string * System.Globalization.NumberStyles -> int
    static member Parse : string * System.IFormatProvider -> int
    static member Parse : string * System.Globalization.NumberStyles * System.IFormatProvider -> int
    static member TryParse : string * int -> bool
    static member TryParse : string * System.Globalization.NumberStyles * System.IFormatProvider * int -> bool
  end

Full name: System.Int32

  type: Int32
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

Multiple overloads
Int32.Parse(s: string) : int
Int32.Parse(s: string, provider: IFormatProvider) : int
Int32.Parse(s: string, style: Globalization.NumberStyles) : int
Int32.Parse(s: string, style: Globalization.NumberStyles, provider: IFormatProvider) : int
Multiple items
val string : ‘T -> string

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

——————–

type string = String

Full name: Microsoft.FSharp.Core.string

  type: string
  implements: IComparable
  implements: ICloneable
  implements: IConvertible
  implements: IComparable<string>
  implements: seq<char>
  implements: Collections.IEnumerable
  implements: IEquatable<string>

val sequence : (char list -> (‘a * char list) list) * (‘a -> char list -> (‘b * char list) list) -> char list -> (‘b * char list) list

Full name: WebSnippets.sequence

val aParser : (char list -> (‘a * char list) list)
val continutationFunc : (‘a -> char list -> (‘b * char list) list)
val c’ : ‘a
val cs’ : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

val bParser : (char list -> (‘b * char list) list)
val bind : (char list -> (‘a * char list) list) * (‘a -> char list -> (‘b * char list) list) -> char list -> (‘b * char list) list

Full name: WebSnippets.bind

val p : (char list -> (‘a * char list) list)
val f : (‘a -> char list -> (‘b * char list) list)
val uglyFunParser : char list -> ((char * int -> FunAST) * char list) list

Full name: WebSnippets.uglyFunParser

val input : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

val returnParser : ‘a -> ‘b -> (‘a * ‘b) list

Full name: WebSnippets.returnParser

val something : ‘a
val cs : ‘b
val zeroParser : unit -> ‘a -> ‘b list

Full name: WebSnippets.zeroParser

val satisfyParser : (char -> bool) -> (char list -> (char * char list) list)

Full name: WebSnippets.satisfyParser

val pred : (char -> bool)
val tcParser : char -> (char list -> (char * char list) list)

Full name: WebSnippets.tcParser

val funParser : char list -> ((char * int -> FunAST) * char list) list

Full name: WebSnippets.funParser

val internalParser : (char list -> ((char * int -> FunAST) * char list) list)
val funParser’ : (char list -> ((char * int -> FunAST) * char list) list)

Full name: WebSnippets.funParser’

val stringParser : string -> (char list -> (char list * char list) list)

Full name: WebSnippets.stringParser

val tok : string

  type: string
  implements: IComparable
  implements: ICloneable
  implements: IConvertible
  implements: IComparable<string>
  implements: seq<char>
  implements: Collections.IEnumerable
  implements: IEquatable<string>

val text : (char list -> char list -> (char list * char list) list)
val t : char

  type: char
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

val tok’ : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

val funParser” : (char list -> ((char * int -> FunAST) * char list) list)

Full name: WebSnippets.funParser”

val singleSpaceParser : (char list -> (char * char list) list)

Full name: WebSnippets.singleSpaceParser

val cleanSpaceParser : (char list -> (‘a * char list) list) -> (char list -> (‘a * char list) list)

Full name: WebSnippets.cleanSpaceParser

val r : ‘a
val finalFunParser : (char list -> ((char * int -> FunAST) * char list) list)

Full name: WebSnippets.finalFunParser

val identParser : (char list -> (char * char list) list)

Full name: WebSnippets.identParser

val equalParser : (char list -> (char * char list) list)

Full name: WebSnippets.equalParser

val digitParser : (char list -> (int * char list) list)

Full name: WebSnippets.digitParser

val spaceParser : char list -> (char list * char list) list

Full name: WebSnippets.spaceParser

val emptyParser : (char list -> (char list * char list) list)
val a : char

  type: char
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

val x : char list * char list
val xs : (char list * char list) list

  type: (char list * char list) list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char list * char list>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char list * char list>
  implements: Collections.IEnumerable

val aa : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

val funLangParser : (char list -> (FunAST * char list) list)

Full name: WebSnippets.funLangParser

val funFunc : (char * int -> FunAST)
val identifier : char

  type: char
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

val digit : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val runParser : seq<char> -> FunAST

Full name: WebSnippets.runParser

val s : seq<char>

  type: seq<char>
  inherits: Collections.IEnumerable

val failwith : string -> ‘T

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

val result : FunAST

  type: FunAST
  implements: IEquatable<FunAST>
  implements: Collections.IStructuralEquatable
  implements: IComparable<FunAST>
  implements: IComparable
  implements: Collections.IStructuralComparable

Comments (2)

  1. Zandoná says:

    @ovatsus, I think this blog series is more about the journey than the destination 🙂

Skip to main content