Parsers in F#

parsers.fs

open System

// "A parser for things is a function from strings to list of pairs of things and strings"
type 'a Parser = string -> ('a * string) list

// What the rhyme means is that a parser for a type (e.g. integers) turns an input string
// (e.g. "11/05/2019") into a list of matches together with the remaining unconsumed input
// (e.g. [(11, "/05/2019")]). In this formultion running a parser over an input strings means
// apply the parser function to the input.

// Let's write a parser

// This function creates, for any given string, a parser that accepts only that string
let aString (s : string) : string Parser =
  // a parser is a function so we return a function ...
  fun input ->
    // ... that looks at the input and ...
    match input with
    // If the input starts with the given string s, it return a single match together with
    // the unconsume input
    | input when input.StartsWith(s) -> [(s, input.[s.Length..])]
    // ... returns no matches in all other cases
    | _                              -> []

// Now the magic begins when we start combining parsers

// One thing we would like to do is to be able to say, match this character or this other
// character. Or, more generally, run a parser and 1) if it returns matches return them
// 2) if if it fails (i.e. it returns no results) then run the other one

let orElse (aParser1 : 'a Parser) (aParser2 : 'a Parser) : 'a Parser =
  fun input ->
    match aParser1 input with
    | [] -> aParser2 input
    | someResult -> someResult

// Now we can express the concept of "one of these parsers"

let oneOf (listOfParsers : 'a Parser list) : 'a Parser =
  listOfParsers |> List.reduce orElse

// For example now we can express a parser for letters as
let letter =
  // for each letter of the alphabet create a parser, then parse one of them
  oneOf (List.map (string >> aString) [ 'a' .. 'z'])

// We can do the same for a digit
let digit =
  // take the digit, turns them into string and then into parsers, and parse one of them
  oneOf (List.map (string >> aString) [ 0 .. 9 ])

// We still don't know how to say "run this parser and then this other parser".
// Here the right combinator. It runs the first parser on the input, then, for each result,
// it computes a new parser from the result and it runs it on the unconsumed input, collecting
// a list of all the results.

let andThen (aParser : 'a Parser) (f: 'a -> 'b Parser) : 'b Parser =
  fun input ->
    input
    |> aParser
    |> List.collect (fun (a, rest) -> f a rest)

// using operators for andThen and orElse makes everything nicer

let (>>=) = andThen 
let (<|>) = orElse

// This other parser seems a bit useless but it's fundamental to finish up the parsing DSL.
// For any value v of any type, it retuns a parser that ignores the input and just returns v.

let simply (thing : 'a) : 'a Parser =
  fun input ->
    [(thing, input)]

// other combinators

let rec some (aParser : 'a Parser) : 'a list Parser = 
  aParser      >>= fun first ->
  many aParser >>= fun rest ->
  simply (first :: rest)
and many (aParser : 'a Parser) : 'a list Parser =
  some aParser <|> simply []

let notSoGoodDigits : string list Parser = some digit

// This is "not so good" because it does indeed match numbers but it returns them
// as a list of string, rather than a number. Of course we can that into a number but how
// do we do it in this context? Let's think about it, if I have a parser for a type a and
// I can convert a value of type a into a value of type b, effectively I can make a parser
// for type b, that is by running the first parser and than converting the result(s).

let parserMap (f : 'a -> 'b) (aParser : 'a Parser) : 'b Parser =
  fun input ->
    input
    |> aParser
    |> List.map (fun (a, rest) -> (f a, rest))

let digits : int Parser =
  notSoGoodDigits
  |> parserMap (String.concat "" >> int)

type MyDate =
  { day : int
    month : int
    year : int }

[<EntryPoint>]
let main argv =

    // Parse a dd/MM/yyyy date
    let myParser =
      digits      >>= fun day   ->
      aString "/" >>= fun _     ->
      digits      >>= fun month ->
      aString "/" >>= fun _     ->
      digits      >>= fun year  ->
      simply {day = day; month = month; year = year}
    
    let input = "11/05/2019"

    for (result, rest) in myParser input do
      printf "Result: %A, rest: %s" result rest

    0 // return an integer exit code