Refactor parsers to use more idiomatic code

2 files changed, 126 insertions, 128 deletions

diff --git a/aoc-2020-gleam/src/days/day02.gleam b/aoc-2020-gleam/src/days/day02.gleam
index a56e0e1..6cfb294 100644
--- a/aoc-2020-gleam/src/days/day02.gleam
+++ b/aoc-2020-gleam/src/days/day02.gleam
@@ -37,12 +37,12 @@ fn is_line_valid2(line: Line) -> Bool {
 
 fn parse_policy() -> p.Parser(Policy) {
   p.int()
-  |> p.then_skip(p.grapheme("-"))
-  |> p.and_then(p.int())
-  |> p.then_skip(p.grapheme(" "))
-  |> p.and_then(p.any_grapheme())
-  |> p.then_skip(p.grapheme(":"))
-  |> p.then_skip(p.grapheme(" "))
+  |> p.then_skip(p.grapheme_literal("-"))
+  |> p.then(p.int())
+  |> p.then_skip(p.grapheme_literal(" "))
+  |> p.then(p.any_grapheme())
+  |> p.then_skip(p.grapheme_literal(":"))
+  |> p.then_skip(p.grapheme_literal(" "))
   |> p.map(with: fn(x) {
     let #(#(min, max), grapheme) = x
     Policy(min, max, grapheme)
@@ -52,10 +52,10 @@ fn parse_policy() -> p.Parser(Policy) {
 fn parse_line(string: String) -> Line {
   let line_parser =
     parse_policy()
-    |> p.and_then(p.all_remaining())
+    |> p.then(p.any_string())
     |> p.map(fn(t) { Line(pair.first(t), pair.second(t)) })
 
-  assert Ok(#(policy, _)) = p.run(line_parser, on: string)
+  assert Ok(policy) = p.parse_entire(string, with: line_parser)
   policy
 }
 
diff --git a/aoc-2020-gleam/src/util/parser.gleam b/aoc-2020-gleam/src/util/parser.gleam
index 43c4e5c..c16dc60 100644
--- a/aoc-2020-gleam/src/util/parser.gleam
+++ b/aoc-2020-gleam/src/util/parser.gleam
@@ -2,181 +2,179 @@ import gleam/string
 import gleam/list
 import gleam/function
 import gleam/pair
-import ext/resultx
+import gleam/result
 import ext/intx
 
 // Heavily inspired by https://fsharpforfunandprofit.com/posts/understanding-parser-combinators/
 
-pub type ParseResult(a) =
-  Result(#(a, String), String)
+const eof: String = "end of input"
+
+fn quoted(grapheme: String) -> String {
+  "'" <> grapheme <> "'"
+}
+
+pub type ParseError {
+  InvalidInput(expected: String, found: String)
+  InvalidParser
+}
+
+type ParseResult(a) =
+  Result(#(a, String), ParseError)
 
 pub opaque type Parser(a) {
-  Parser(parser: fn(String) -> ParseResult(a))
+  Parser(function: fn(String) -> ParseResult(a))
 }
 
-pub fn run(parser: Parser(a), on input: String) -> ParseResult(a) {
-  assert Parser(function) = parser
-  function(input)
+fn run(parser: Parser(a), on input: String) -> ParseResult(a) {
+  parser.function(input)
 }
 
-pub fn any_grapheme() -> Parser(String) {
-  let inner = fn(input) {
-    case string.pop_grapheme(input) {
-      Ok(#(first, rest)) -> Ok(#(first, rest))
-      _ -> Error("Error!")
-    }
-  }
-  Parser(inner)
+pub fn parse_partial(
+  input: String,
+  with parser: Parser(a),
+) -> Result(#(a, String), ParseError) {
+  run(parser, on: input)
 }
 
-pub fn grapheme(expected: String) -> Parser(String) {
-  let inner = fn(input) {
-    case string.pop_grapheme(input) {
-      Ok(#(first, rest)) if first == expected -> Ok(#(expected, rest))
-      _ -> Error("Error!")
-    }
-  }
-  Parser(inner)
-}
-
-pub fn and_then(parser1: Parser(a), parser2: Parser(b)) -> Parser(#(a, b)) {
-  let inner = fn(input) {
-    let result1 = run(parser1, on: input)
-    case result1 {
-      Error(err) -> Error(err)
-      Ok(#(value1, remaining1)) -> {
-        let result2 = run(parser2, on: remaining1)
-        case result2 {
-          Error(err) -> Error(err)
-          Ok(#(value2, remaining2)) -> {
-            let new_value = #(value1, value2)
-            Ok(#(new_value, remaining2))
-          }
-        }
-      }
-    }
+pub fn parse_entire(
+  input: String,
+  with parser: Parser(a),
+) -> Result(a, ParseError) {
+  case parse_partial(input, with: parser) {
+    Ok(#(value, "")) -> Ok(value)
+    Ok(#(_, rest)) -> Error(InvalidInput(expected: eof, found: rest))
+    Error(error) -> Error(error)
   }
-  Parser(inner)
 }
 
-pub fn then_skip(parser1: Parser(a), parser2: Parser(b)) -> Parser(a) {
-  parser1
-  |> and_then(parser2)
-  |> map(with: pair.first)
+pub fn any_grapheme() -> Parser(String) {
+  Parser(fn(input) {
+    input
+    |> string.pop_grapheme
+    |> result.replace_error(InvalidInput(expected: "any grapheme", found: eof))
+  })
 }
 
-pub fn or_else(parser1: Parser(a), parser2: Parser(a)) -> Parser(a) {
-  let inner = fn(input) {
-    let result1 = run(parser1, on: input)
-    case result1 {
-      Ok(_result) -> result1
-      Error(_err) -> {
-        let result2 = run(parser2, on: input)
-        result2
-      }
+pub fn grapheme_literal(expected: String) -> Parser(String) {
+  Parser(fn(input) {
+    case run(any_grapheme(), on: input) {
+      Ok(#(value, _)) as ok if value == expected -> ok
+      Ok(#(value, _)) -> Error(InvalidInput(quoted(expected), found: value))
+      Error(_) -> Error(InvalidInput(quoted(expected), found: eof))
     }
-  }
-  Parser(inner)
+  })
 }
 
-pub fn choice(from parsers: List(Parser(a))) -> Parser(a) {
-  list.reduce(over: parsers, with: or_else)
-  |> resultx.force_unwrap
+pub fn then(first: Parser(a), second: Parser(b)) -> Parser(#(a, b)) {
+  Parser(fn(input) {
+    use parsed1 <- result.then(run(first, on: input))
+    let #(value1, remaining1) = parsed1
+
+    use parsed2 <- result.then(run(second, on: remaining1))
+    let #(value2, remaining2) = parsed2
+
+    Ok(#(#(value1, value2), remaining2))
+  })
+}
+
+pub fn then_skip(first: Parser(a), second: Parser(b)) -> Parser(a) {
+  first
+  |> then(second)
+  |> map(with: pair.first)
 }
 
-pub fn any_of(given graphemes: List(String)) -> Parser(String) {
-  graphemes
-  |> list.map(with: grapheme)
-  |> choice
+pub fn or(first: Parser(a), else second: Parser(a)) -> Parser(a) {
+  Parser(fn(input) {
+    first
+    |> run(on: input)
+    |> result.or(run(second, on: input))
+  })
 }
 
-pub fn lowercase() -> Parser(String) {
-  "abcdefghijklmnopqrstuvwxyz"
-  |> string.to_graphemes
-  |> any_of
+pub fn any(of parsers: List(Parser(a))) -> Parser(a) {
+  parsers
+  |> list.reduce(with: or)
+  |> result.unwrap(or: failing(InvalidParser))
 }
 
 pub fn digit() -> Parser(String) {
   "0123456789"
   |> string.to_graphemes
-  |> any_of
+  |> list.map(with: grapheme_literal)
+  |> any
+  // TODO: replace error
 }
 
 pub fn map(parser: Parser(a), with mapper: fn(a) -> b) -> Parser(b) {
-  let inner = fn(input) {
-    let result = run(parser, on: input)
-    case result {
-      Ok(#(value, remaining)) -> {
-        let new_value = mapper(value)
-        Ok(#(new_value, remaining))
-      }
-      Error(err) -> Error(err)
-    }
-  }
-  Parser(inner)
+  Parser(fn(input) {
+    use parsed <- result.then(run(parser, on: input))
+    let #(value, remaining) = parsed
+    Ok(#(mapper(value), remaining))
+  })
+}
+
+fn succeeding(value: a) -> Parser(a) {
+  Parser(fn(input) { Ok(#(value, input)) })
 }
 
-fn return(x: a) -> Parser(a) {
-  let inner = fn(input) { Ok(#(x, input)) }
-  Parser(inner)
+fn failing(error: ParseError) -> Parser(a) {
+  Parser(fn(_) { Error(error) })
 }
 
-fn apply(fp: Parser(fn(a) -> b), xp: Parser(a)) -> Parser(b) {
-  and_then(fp, xp)
-  |> map(fn(p) {
-    let #(f, x) = p
+fn apply(fn_parser: Parser(fn(a) -> b), value_parser: Parser(a)) -> Parser(b) {
+  fn_parser
+  |> then(value_parser)
+  |> map(fn(pair) {
+    let #(f, x) = pair
     f(x)
   })
 }
 
-fn lift2(f: fn(a, b) -> c) -> fn(Parser(a), Parser(b)) -> Parser(c) {
-  let inner = fn(xp, yp) {
-    let fc = function.curry2(f)
-    apply(apply(return(fc), xp), yp)
+fn lift2(func: fn(a, b) -> c) -> fn(Parser(a), Parser(b)) -> Parser(c) {
+  fn(x_parser, y_parser) {
+    func
+    |> function.curry2
+    |> succeeding
+    |> apply(x_parser)
+    |> apply(y_parser)
   }
-  inner
 }
 
 pub fn sequence(of parsers: List(Parser(a))) -> Parser(List(a)) {
-  let cons_p = lift2(list.prepend)
+  let prepend_parser = lift2(list.prepend)
   case parsers {
-    [] -> return([])
-    [head, ..tail] -> cons_p(sequence(tail), head)
+    [] -> succeeding([])
+    [head, ..tail] ->
+      tail
+      |> sequence
+      |> prepend_parser(head)
   }
 }
 
-fn parse_zero_or_more(parser: Parser(a), input: String) -> #(List(a), String) {
-  let first_result = run(parser, on: input)
-  case first_result {
-    Error(_err) -> #([], input)
-    Ok(#(first_value, input_after_first_parse)) -> {
-      let #(subsequent_values, remaining_input) =
-        parse_zero_or_more(parser, input_after_first_parse)
-      let values = [first_value, ..subsequent_values]
-      #(values, remaining_input)
+fn parse_zero_or_more(
+  input: String,
+  with parser: Parser(a),
+) -> #(List(a), String) {
+  case run(parser, on: input) {
+    Ok(#(value, rest)) -> {
+      let #(previous, rest) = parse_zero_or_more(rest, with: parser)
+      #([value, ..previous], rest)
     }
+    Error(_) -> #([], input)
   }
 }
 
 pub fn many(parser: Parser(a)) -> Parser(List(a)) {
-  let inner = fn(input) { Ok(parse_zero_or_more(parser, input)) }
-  Parser(inner)
+  Parser(fn(input) { Ok(parse_zero_or_more(input, with: parser)) })
 }
 
 pub fn many1(parser: Parser(a)) -> Parser(List(a)) {
-  let inner = fn(input) {
-    let first_result = run(parser, on: input)
-    case first_result {
-      Error(err) -> Error(err)
-      Ok(#(first_value, input_after_first_parse)) -> {
-        let #(subsequent_values, remaining_input) =
-          parse_zero_or_more(parser, input_after_first_parse)
-        let values = [first_value, ..subsequent_values]
-        Ok(#(values, remaining_input))
-      }
-    }
-  }
-  Parser(inner)
+  Parser(fn(input) {
+    use parsed <- result.then(run(parser, on: input))
+    let #(value, rest) = parsed
+    let #(previous, rest) = parse_zero_or_more(rest, with: parser)
+    Ok(#([value, ..previous], rest))
+  })
 }
 
 pub fn int() -> Parser(Int) {
@@ -185,7 +183,7 @@ pub fn int() -> Parser(Int) {
   |> map(with: function.compose(string.concat, intx.force_parse))
 }
 
-pub fn all_remaining() -> Parser(String) {
+pub fn any_string() -> Parser(String) {
   any_grapheme()
   |> many
   |> map(with: string.concat)