040 Intermediate GitHub

040 — Parse a Dotstring Back to a Binary Tree

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "040 — Parse a Dotstring Back to a Binary Tree" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Parsing a dotstring back to a binary tree (OCaml 99 Problems, complement to #39) is the deserialization half of the round-trip. Key difference from OCaml: 1. **Error handling**: Rust's `Result<Tree<char>, String>` makes parse errors explicit in the type system. OCaml's `failwith` raises an exception — callers must use `try...with` to catch it. A functional OCaml style would return `option` or `result`.

Tutorial

The Problem

Parsing a dotstring back to a binary tree (OCaml 99 Problems, complement to #39) is the deserialization half of the round-trip. It is also a textbook example of recursive descent parsing: each call to the parse function consumes exactly one self-delimiting unit (either a . for leaf or a character followed by two recursive calls for a node).

Recursive descent parsers are the basis for most hand-written language parsers (JSON parsers, expression evaluators, configuration file readers). The self-delimiting property of dotstrings makes this one of the simplest examples of recursive descent — no lookahead, no backtracking, no ambiguity.

🎯 Learning Outcomes

• Write a recursive descent parser that consumes characters left to right

• Use a &mut usize position cursor to track how much input has been consumed

• Handle the single-character lookahead needed to distinguish . from node values

• Implement error handling for malformed dotstrings

• Connect this parser structure to JSON/XML parsers and formal language grammars

• Write a recursive descent parser that threads &mut usize position cursor through recursive calls

• Handle parse errors with Result<Tree<char>, String> — return descriptive error messages for malformed input

Code Example

#![allow(clippy::all)]
// Parse a dotstring back to a tree (OCaml 99 Problems, complement to #39) via recursive descent.
#[derive(Debug, Clone, PartialEq)]
pub enum Tree<T> {
    Leaf,
    Node(T, Box<Tree<T>>, Box<Tree<T>>),
}

impl<T> Tree<T> {
    pub fn leaf() -> Self {
        Tree::Leaf
    }

    pub fn node(val: T, left: Tree<T>, right: Tree<T>) -> Self {
        Tree::Node(val, Box::new(left), Box::new(right))
    }
}

pub fn parse_dotstring(chars: &[char], pos: &mut usize) -> Result<Tree<char>, String> {
    if *pos >= chars.len() {
        return Err("unexpected end of input".to_string());
    }
    let c = chars[*pos];
    *pos += 1;
    if c == '.' {
        Ok(Tree::Leaf)
    } else {
        let left = parse_dotstring(chars, pos)?;
        let right = parse_dotstring(chars, pos)?;
        Ok(Tree::node(c, left, right))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_parse_valid_dotstring() {
        let chars: Vec<char> = "ab..c..".chars().collect();
        let mut pos = 0;
        let tree = parse_dotstring(&chars, &mut pos).unwrap();
        assert_eq!(
            tree,
            Tree::node('a', Tree::node('b', Tree::leaf(), Tree::leaf()), Tree::node('c', Tree::leaf(), Tree::leaf()))
        );
        assert_eq!(pos, chars.len());
    }

    #[test]
    fn test_parse_leaf_only() {
        let chars: Vec<char> = ".".chars().collect();
        let mut pos = 0;
        assert_eq!(parse_dotstring(&chars, &mut pos).unwrap(), Tree::Leaf);
    }

    #[test]
    fn test_parse_truncated_input_errors() {
        let chars: Vec<char> = "ab.".chars().collect(); // missing right subtree of 'b'
        let mut pos = 0;
        assert!(parse_dotstring(&chars, &mut pos).is_err());
    }

    #[test]
    fn test_parse_empty_input_errors() {
        let chars: Vec<char> = vec![];
        let mut pos = 0;
        assert!(parse_dotstring(&chars, &mut pos).is_err());
    }
}

(* Dotstring Parse *)
(* OCaml 99 Problems, complement to #39 *)

type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree

let node x l r = Node (x, l, r)
let leaf = Leaf

let parse_dotstring s =
  let n = String.length s in
  let rec parse pos =
    if pos >= n then failwith "unexpected end of input"
    else
      let c = s.[pos] in
      if c = '.' then (Leaf, pos + 1)
      else
        let l, p1 = parse (pos + 1) in
        let r, p2 = parse p1 in
        (Node (c, l, r), p2)
  in
  parse 0

(* Tests *)
let () =
  let tree, pos = parse_dotstring "ab..c.." in
  assert (tree = node 'a' (node 'b' leaf leaf) (node 'c' leaf leaf));
  assert (pos = String.length "ab..c..");

  let leaf_tree, _ = parse_dotstring "." in
  assert (leaf_tree = Leaf);

  (try
     let _ = parse_dotstring "ab." in
     assert false
   with Failure _ -> ());

  (try
     let _ = parse_dotstring "" in
     assert false
   with Failure _ -> ());

  print_endline "✓ OCaml tests passed"

Key Differences

Error handling: Rust's Result<Tree<char>, String> makes parse errors explicit in the type system. OCaml's failwith raises an exception — callers must use try...with to catch it. A functional OCaml style would return option or result.

Position threading: Rust: &mut usize (single shared mutable reference). OCaml: return (result, new_pos) pairs (no mutation). Both are equivalent; OCaml's style is more testable.

Composability: The OCaml functional style composes naturally — you can build more complex parsers by sequencing parse calls. Rust with &mut usize also composes but requires managing the shared mutable state.

Parser combinators: Both approaches generalize to parser combinator libraries. Rust has nom, pest, winnow. OCaml has angstrom, mparser. The dotstring parser is the simplest case of what these libraries handle.

Stateful parsing: The parser consumes characters one by one, threading a Chars iterator through recursive calls. This is a simple recursive descent parser — the same pattern used in compiler front-ends.

**&mut Chars:** Passing chars: &mut Chars allows each recursive call to advance the iterator. The next() call returns Some(char) or None when the input is exhausted.

Round-trip invariant: parse(serialize(tree)) == tree for any tree. This is a strong property to verify with property-based testing.

Functional vs imperative threading: OCaml returns (tree, remaining) tuples for functional threading of parser state. Rust uses &mut usize position. Both thread state through recursion; only the syntax differs.

OCaml Approach

OCaml's functional version returns (Tree<char>, int) pairs: let rec parse s pos = if pos >= String.length s then failwith "unexpected end" else let c = s.[pos] in if c = '.' then (Leaf, pos + 1) else let (l, p1) = parse s (pos + 1) in let (r, p2) = parse s p1 in (Node (c, l, r), p2). The position threads through all recursive calls as an explicit argument and return value.

Full Source

#![allow(clippy::all)]
// Parse a dotstring back to a tree (OCaml 99 Problems, complement to #39) via recursive descent.
#[derive(Debug, Clone, PartialEq)]
pub enum Tree<T> {
    Leaf,
    Node(T, Box<Tree<T>>, Box<Tree<T>>),
}

impl<T> Tree<T> {
    pub fn leaf() -> Self {
        Tree::Leaf
    }

    pub fn node(val: T, left: Tree<T>, right: Tree<T>) -> Self {
        Tree::Node(val, Box::new(left), Box::new(right))
    }
}

pub fn parse_dotstring(chars: &[char], pos: &mut usize) -> Result<Tree<char>, String> {
    if *pos >= chars.len() {
        return Err("unexpected end of input".to_string());
    }
    let c = chars[*pos];
    *pos += 1;
    if c == '.' {
        Ok(Tree::Leaf)
    } else {
        let left = parse_dotstring(chars, pos)?;
        let right = parse_dotstring(chars, pos)?;
        Ok(Tree::node(c, left, right))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_parse_valid_dotstring() {
        let chars: Vec<char> = "ab..c..".chars().collect();
        let mut pos = 0;
        let tree = parse_dotstring(&chars, &mut pos).unwrap();
        assert_eq!(
            tree,
            Tree::node('a', Tree::node('b', Tree::leaf(), Tree::leaf()), Tree::node('c', Tree::leaf(), Tree::leaf()))
        );
        assert_eq!(pos, chars.len());
    }

    #[test]
    fn test_parse_leaf_only() {
        let chars: Vec<char> = ".".chars().collect();
        let mut pos = 0;
        assert_eq!(parse_dotstring(&chars, &mut pos).unwrap(), Tree::Leaf);
    }

    #[test]
    fn test_parse_truncated_input_errors() {
        let chars: Vec<char> = "ab.".chars().collect(); // missing right subtree of 'b'
        let mut pos = 0;
        assert!(parse_dotstring(&chars, &mut pos).is_err());
    }

    #[test]
    fn test_parse_empty_input_errors() {
        let chars: Vec<char> = vec![];
        let mut pos = 0;
        assert!(parse_dotstring(&chars, &mut pos).is_err());
    }
}

(* Dotstring Parse *)
(* OCaml 99 Problems, complement to #39 *)

type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree

let node x l r = Node (x, l, r)
let leaf = Leaf

let parse_dotstring s =
  let n = String.length s in
  let rec parse pos =
    if pos >= n then failwith "unexpected end of input"
    else
      let c = s.[pos] in
      if c = '.' then (Leaf, pos + 1)
      else
        let l, p1 = parse (pos + 1) in
        let r, p2 = parse p1 in
        (Node (c, l, r), p2)
  in
  parse 0

(* Tests *)
let () =
  let tree, pos = parse_dotstring "ab..c.." in
  assert (tree = node 'a' (node 'b' leaf leaf) (node 'c' leaf leaf));
  assert (pos = String.length "ab..c..");

  let leaf_tree, _ = parse_dotstring "." in
  assert (leaf_tree = Leaf);

  (try
     let _ = parse_dotstring "ab." in
     assert false
   with Failure _ -> ());

  (try
     let _ = parse_dotstring "" in
     assert false
   with Failure _ -> ());

  print_endline "✓ OCaml tests passed"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_parse_valid_dotstring() {
        let chars: Vec<char> = "ab..c..".chars().collect();
        let mut pos = 0;
        let tree = parse_dotstring(&chars, &mut pos).unwrap();
        assert_eq!(
            tree,
            Tree::node('a', Tree::node('b', Tree::leaf(), Tree::leaf()), Tree::node('c', Tree::leaf(), Tree::leaf()))
        );
        assert_eq!(pos, chars.len());
    }

    #[test]
    fn test_parse_leaf_only() {
        let chars: Vec<char> = ".".chars().collect();
        let mut pos = 0;
        assert_eq!(parse_dotstring(&chars, &mut pos).unwrap(), Tree::Leaf);
    }

    #[test]
    fn test_parse_truncated_input_errors() {
        let chars: Vec<char> = "ab.".chars().collect(); // missing right subtree of 'b'
        let mut pos = 0;
        assert!(parse_dotstring(&chars, &mut pos).is_err());
    }

    #[test]
    fn test_parse_empty_input_errors() {
        let chars: Vec<char> = vec![];
        let mut pos = 0;
        assert!(parse_dotstring(&chars, &mut pos).is_err());
    }
}

Deep Comparison

OCaml vs Rust: Dotstring Parse

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Robust parser: Add full error recovery: report the position of the error and the character that caused it. Return Result<Tree<char>, ParseError> where ParseError includes position and message.

Parser combinator: Rewrite the parser using a type Parser<T> = impl Fn(&[char], usize) -> Result<(T, usize), String>. Define map, and_then, and or combinators, then compose them to build the dotstring parser.

Extended format: Extend the parser to handle multi-character node values enclosed in brackets: [abc] for a node with value "abc". Modify the grammar and the parser together.

Error recovery: Modify the parser to collect all errors encountered and report all of them, rather than stopping at the first error.

Parser generalization: Implement a generic Parser<T> type as a newtype over impl Fn(&str) -> Result<(T, &str), String> and rewrite the tree parser using combinators like map, and_then, and or.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust