159 Advanced

Map Parser

Functional Programming

Tutorial

The Problem

Parsers produce raw strings and characters, but applications need structured data — integers, enums, structs. The map combinator transforms a parser's output without changing what it consumes. It is the Functor operation for parsers: if you have a Parser<A> and a function A -> B, map produces a Parser<B>. This functional transformation step keeps parsing (what to consume) separate from interpretation (what it means), a core principle of combinator-based parsing.

🎯 Learning Outcomes

• Understand map as the fundamental output-transformation combinator (Functor)

• Learn how map separates parsing from interpretation

• See how character/string parsers are lifted into typed domain objects via map

• Practice chaining map with other combinators to build typed parsers

Code Example

fn map<'a, A: 'a, B: 'a, F>(parser: Parser<'a, A>, f: F) -> Parser<'a, B>
where F: Fn(A) -> B + 'a {
    Box::new(move |input: &'a str| {
        let (value, rest) = parser(input)?;
        Ok((f(value), rest))
    })
}

let map (f : 'a -> 'b) (p : 'a parser) : 'b parser = fun input ->
  match p input with
  | Ok (v, rest) -> Ok (f v, rest)
  | Error e -> Error e

Key Differences

Infix operator: OCaml's >>| (or <$>) applies map with operator precedence; Rust uses method chaining or named map(p, f) functions.

Lift: OCaml's lift2 f p q = pair(p, q).map(|(a, b)| f(a, b)) in Rust; OCaml's syntax is more concise for multi-parser transformations.

Error preservation: Both pass through the inner parser's error on failure — map's function f is never called on failure.

Composability: map is the foundational combinator — all structured parsers are built from primitives via map and sequencing.

OCaml Approach

OCaml's angstrom provides map : ('a -> 'b) -> 'a t -> 'b t and the infix >>|:

let uint_parser = many1 digit >>| (fun cs -> int_of_string (String.of_list cs))

OCaml's |> and >>| operators compose naturally. The lift family (lift2, lift3) applies functions of multiple arguments to multiple parsers simultaneously, avoiding explicit pair + map combinations.

Full Source

#![allow(clippy::all)]
// Example 159: Map Parser
// map: transform parser output functorially

type ParseResult<'a, T> = Result<(T, &'a str), String>;
type Parser<'a, T> = Box<dyn Fn(&'a str) -> ParseResult<'a, T> + 'a>;

fn satisfy<'a, F>(pred: F, desc: &str) -> Parser<'a, char>
where
    F: Fn(char) -> bool + 'a,
{
    let desc = desc.to_string();
    Box::new(move |input: &'a str| match input.chars().next() {
        Some(c) if pred(c) => Ok((c, &input[c.len_utf8()..])),
        _ => Err(format!("Expected {}", desc)),
    })
}

fn many1<'a, T: 'a>(parser: Parser<'a, T>) -> Parser<'a, Vec<T>> {
    Box::new(move |input: &'a str| {
        let (first, mut rem) = parser(input)?;
        let mut results = vec![first];
        while let Ok((v, rest)) = parser(rem) {
            results.push(v);
            rem = rest;
        }
        Ok((results, rem))
    })
}

fn tag<'a>(expected: &str) -> Parser<'a, &'a str> {
    let exp = expected.to_string();
    Box::new(move |input: &'a str| {
        if input.starts_with(&exp) {
            Ok((&input[..exp.len()], &input[exp.len()..]))
        } else {
            Err(format!("Expected \"{}\"", exp))
        }
    })
}

// ============================================================
// Approach 1: map — transform parsed value
// ============================================================

fn map<'a, A: 'a, B: 'a, F>(parser: Parser<'a, A>, f: F) -> Parser<'a, B>
where
    F: Fn(A) -> B + 'a,
{
    Box::new(move |input: &'a str| {
        let (value, rest) = parser(input)?;
        Ok((f(value), rest))
    })
}

// ============================================================
// Approach 2: map2 — combine two parser results
// ============================================================

fn map2<'a, A: 'a, B: 'a, C: 'a, F>(p1: Parser<'a, A>, p2: Parser<'a, B>, f: F) -> Parser<'a, C>
where
    F: Fn(A, B) -> C + 'a,
{
    Box::new(move |input: &'a str| {
        let (v1, rest) = p1(input)?;
        let (v2, rem) = p2(rest)?;
        Ok((f(v1, v2), rem))
    })
}

// ============================================================
// Approach 3: map_const — ignore result, return fixed value
// ============================================================

fn map_const<'a, A: 'a, B: Clone + 'a>(parser: Parser<'a, A>, value: B) -> Parser<'a, B> {
    Box::new(move |input: &'a str| {
        let (_, rest) = parser(input)?;
        Ok((value.clone(), rest))
    })
}

/// Parse natural number: one or more digits → u64
fn parse_nat<'a>() -> Parser<'a, u64> {
    map(many1(satisfy(|c| c.is_ascii_digit(), "digit")), |digits| {
        digits
            .iter()
            .fold(0u64, |acc, &d| acc * 10 + (d as u64 - '0' as u64))
    })
}

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

    #[test]
    fn test_map_uppercase() {
        let p = map(satisfy(|c| c.is_ascii_lowercase(), "lower"), |c| {
            c.to_ascii_uppercase()
        });
        assert_eq!(p("abc"), Ok(('A', "bc")));
    }

    #[test]
    fn test_map_preserves_error() {
        let p = map(satisfy(|c| c.is_ascii_digit(), "digit"), |c| c as u32);
        assert!(p("abc").is_err());
    }

    #[test]
    fn test_parse_nat() {
        let p = parse_nat();
        assert_eq!(p("42rest"), Ok((42, "rest")));
    }

    #[test]
    fn test_parse_nat_zero() {
        let p = parse_nat();
        assert_eq!(p("0"), Ok((0, "")));
    }

    #[test]
    fn test_parse_nat_fail() {
        let p = parse_nat();
        assert!(p("abc").is_err());
    }

    #[test]
    fn test_map2() {
        let p = map2(
            satisfy(|c| c.is_ascii_digit(), "digit"),
            satisfy(|c| c.is_ascii_digit(), "digit"),
            |a, b| format!("{}{}", a, b),
        );
        assert_eq!(p("12x"), Ok(("12".to_string(), "x")));
    }

    #[test]
    fn test_map_const_true() {
        let p = map_const(tag("true"), true);
        assert_eq!(p("true!"), Ok((true, "!")));
    }

    #[test]
    fn test_map_const_false() {
        let p = map_const(tag("false"), false);
        assert_eq!(p("false"), Ok((false, "")));
    }

    #[test]
    fn test_map_chain() {
        // map(map(p, f), g) == map(p, |x| g(f(x)))
        let p = map(
            map(satisfy(|c| c.is_ascii_digit(), "digit"), |c| {
                c as u32 - '0' as u32
            }),
            |n| n * 2,
        );
        assert_eq!(p("5"), Ok((10, "")));
    }
}

(* Example 159: Map Parser *)
(* map: transform parser output functorially *)

type 'a parse_result = ('a * string, string) result
type 'a parser = string -> 'a parse_result

let satisfy pred desc : char parser = fun input ->
  if String.length input > 0 && pred input.[0] then
    Ok (input.[0], String.sub input 1 (String.length input - 1))
  else Error (Printf.sprintf "Expected %s" desc)

let many0 (p : 'a parser) : 'a list parser = fun input ->
  let rec go acc rem =
    match p rem with
    | Ok (v, rest) -> go (v :: acc) rest
    | Error _ -> Ok (List.rev acc, rem)
  in go [] input

let many1 (p : 'a parser) : 'a list parser = fun input ->
  match p input with
  | Error e -> Error e
  | Ok (v, rest) ->
    match many0 p rest with
    | Ok (vs, rem) -> Ok (v :: vs, rem)
    | Error e -> Error e

(* Approach 1: map — transform the parsed value *)
let map (f : 'a -> 'b) (p : 'a parser) : 'b parser = fun input ->
  match p input with
  | Ok (v, rest) -> Ok (f v, rest)
  | Error e -> Error e

(* Approach 2: map2 — combine two parser results *)
let map2 (f : 'a -> 'b -> 'c) (p1 : 'a parser) (p2 : 'b parser) : 'c parser = fun input ->
  match p1 input with
  | Error e -> Error e
  | Ok (v1, rest) ->
    match p2 rest with
    | Error e -> Error e
    | Ok (v2, rem) -> Ok (f v1 v2, rem)

(* Approach 3: map with const — ignore result, return fixed value *)
let map_const (value : 'b) (p : 'a parser) : 'b parser = fun input ->
  match p input with
  | Ok (_, rest) -> Ok (value, rest)
  | Error e -> Error e

(* Practical: parse digits and convert to int *)
let is_digit = satisfy (fun c -> c >= '0' && c <= '9') "digit"

let parse_nat : int parser =
  map (fun chars ->
    List.fold_left (fun acc c -> acc * 10 + (Char.code c - Char.code '0')) 0 chars
  ) (many1 is_digit)

(* Tests *)
let () =
  (* map: char to uppercase *)
  let upper_letter = map Char.uppercase_ascii
    (satisfy (fun c -> c >= 'a' && c <= 'z') "lowercase") in
  assert (upper_letter "abc" = Ok ('A', "bc"));

  (* parse_nat: digits to int *)
  assert (parse_nat "42rest" = Ok (42, "rest"));
  assert (parse_nat "0" = Ok (0, ""));
  assert (Result.is_error (parse_nat "abc"));

  (* map2 *)
  let digit = satisfy (fun c -> c >= '0' && c <= '9') "digit" in
  let pair_str = map2 (fun a b -> Printf.sprintf "%c%c" a b) digit digit in
  assert (pair_str "12x" = Ok ("12", "x"));

  (* map_const *)
  let tag s : string parser = fun input ->
    let len = String.length s in
    if String.length input >= len && String.sub input 0 len = s then
      Ok (s, String.sub input len (String.length input - len))
    else Error (Printf.sprintf "Expected \"%s\"" s) in
  let true_parser = map_const true (tag "true") in
  assert (true_parser "true!" = Ok (true, "!"));

  print_endline "✓ All tests passed"

✓ Tests Rust test suite

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

    #[test]
    fn test_map_uppercase() {
        let p = map(satisfy(|c| c.is_ascii_lowercase(), "lower"), |c| {
            c.to_ascii_uppercase()
        });
        assert_eq!(p("abc"), Ok(('A', "bc")));
    }

    #[test]
    fn test_map_preserves_error() {
        let p = map(satisfy(|c| c.is_ascii_digit(), "digit"), |c| c as u32);
        assert!(p("abc").is_err());
    }

    #[test]
    fn test_parse_nat() {
        let p = parse_nat();
        assert_eq!(p("42rest"), Ok((42, "rest")));
    }

    #[test]
    fn test_parse_nat_zero() {
        let p = parse_nat();
        assert_eq!(p("0"), Ok((0, "")));
    }

    #[test]
    fn test_parse_nat_fail() {
        let p = parse_nat();
        assert!(p("abc").is_err());
    }

    #[test]
    fn test_map2() {
        let p = map2(
            satisfy(|c| c.is_ascii_digit(), "digit"),
            satisfy(|c| c.is_ascii_digit(), "digit"),
            |a, b| format!("{}{}", a, b),
        );
        assert_eq!(p("12x"), Ok(("12".to_string(), "x")));
    }

    #[test]
    fn test_map_const_true() {
        let p = map_const(tag("true"), true);
        assert_eq!(p("true!"), Ok((true, "!")));
    }

    #[test]
    fn test_map_const_false() {
        let p = map_const(tag("false"), false);
        assert_eq!(p("false"), Ok((false, "")));
    }

    #[test]
    fn test_map_chain() {
        // map(map(p, f), g) == map(p, |x| g(f(x)))
        let p = map(
            map(satisfy(|c| c.is_ascii_digit(), "digit"), |c| {
                c as u32 - '0' as u32
            }),
            |n| n * 2,
        );
        assert_eq!(p("5"), Ok((10, "")));
    }
}

Deep Comparison

Comparison: Example 159 — Map Parser

map

OCaml:

let map (f : 'a -> 'b) (p : 'a parser) : 'b parser = fun input ->
  match p input with
  | Ok (v, rest) -> Ok (f v, rest)
  | Error e -> Error e

Rust:

fn map<'a, A: 'a, B: 'a, F>(parser: Parser<'a, A>, f: F) -> Parser<'a, B>
where F: Fn(A) -> B + 'a {
    Box::new(move |input: &'a str| {
        let (value, rest) = parser(input)?;
        Ok((f(value), rest))
    })
}

Practical: parse_nat

OCaml:

let parse_nat : int parser =
  map (fun chars ->
    List.fold_left (fun acc c -> acc * 10 + (Char.code c - Char.code '0')) 0 chars
  ) (many1 is_digit)

Rust:

fn parse_nat<'a>() -> Parser<'a, u64> {
    map(
        many1(satisfy(|c| c.is_ascii_digit(), "digit")),
        |digits| digits.iter().fold(0u64, |acc, &d| acc * 10 + (d as u64 - '0' as u64)),
    )
}

map_const

OCaml:

let map_const (value : 'b) (p : 'a parser) : 'b parser = fun input ->
  match p input with
  | Ok (_, rest) -> Ok (value, rest)
  | Error e -> Error e

Rust:

fn map_const<'a, A: 'a, B: Clone + 'a>(parser: Parser<'a, A>, value: B) -> Parser<'a, B> {
    Box::new(move |input: &'a str| {
        let (_, rest) = parser(input)?;
        Ok((value.clone(), rest))
    })
}

Exercises

Write digit_value() -> Parser<u32> that parses a single ASCII digit and returns its numeric value using map.

Build a color_parser() -> Parser<Color> where Color is an enum {Red, Green, Blue} and inputs are "red", "green", "blue".

Implement map_err<T>(p: Parser<T>, f: impl Fn(String) -> String) -> Parser<T> that transforms error messages.

Open Source Repos

functional-rust

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

Rust