274 Intermediate

Binary ↔ Decimal Fold

StringsFoldsNumeric ConversionRecursion

Tutorial Video

Text description (accessibility)

This video demonstrates the "Binary ↔ Decimal Fold" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Strings, Folds, Numeric Conversion, Recursion. Convert a binary string (e.g. Key difference from OCaml: 1. **Error handling:** OCaml raises an exception (`failwith`); Rust returns `Result<u64, String>` — no panics at the library boundary.

Tutorial

The Problem

Convert a binary string (e.g. "1010") to its decimal value using a left fold, and convert a decimal integer back to a binary string using recursion or iteration.

🎯 Learning Outcomes

• How OCaml's String.fold_left maps directly to Rust's Iterator::try_fold

• Using try_fold to accumulate results that may fail (error propagation in folds)

• Translating an OCaml accumulator-based recursion into idiomatic Rust

• Returning Result<T, E> instead of failwith for error handling

🦀 The Rust Way

Rust's chars().try_fold() is the direct equivalent of String.fold_left with error support — it short-circuits on Err just as failwith aborts in OCaml. The recursive decimal_to_binary mirrors the OCaml go helper using an inner function. An iterative version collects bits into a Vec then reverses, which is more cache-friendly.

Code Example

pub fn binary_to_decimal(s: &str) -> Result<u64, String> {
    s.chars().try_fold(0u64, |acc, c| match c {
        '0' => Ok(acc * 2),
        '1' => Ok(acc * 2 + 1),
        _ => Err(format!("invalid binary digit: {c}")),
    })
}

let binary_to_decimal s =
  String.fold_left (fun acc c ->
    match c with
    | '0' -> acc * 2
    | '1' -> acc * 2 + 1
    | _ -> failwith "invalid binary digit"
  ) 0 s

let decimal_to_binary n =
  if n = 0 then "0"
  else
    let rec go n acc =
      if n = 0 then acc
      else go (n / 2) (string_of_int (n mod 2) ^ acc)
    in go n ""

Key Differences

Error handling: OCaml raises an exception (failwith); Rust returns Result<u64, String> — no panics at the library boundary.

Fold with fallibility: OCaml fold_left has no built-in short-circuit; Rust try_fold stops on Err immediately.

String building: OCaml uses ^ (string concatenation) in recursion; Rust uses format! or Vec<u8> + collect.

Integer types: OCaml uses polymorphic int; Rust uses explicit u64, preventing negative inputs by type.

OCaml Approach

OCaml uses String.fold_left to accumulate the decimal value character by character, doubling the accumulator and adding 1 for '1' digits. decimal_to_binary uses a tail-recursive helper go that prepends remainder bits to a string accumulator.

Full Source

#![allow(clippy::all)]
/// Solution 1: Idiomatic Rust — fold over chars, propagate errors
pub fn binary_to_decimal(s: &str) -> Result<u64, String> {
    s.chars().try_fold(0u64, |acc, c| match c {
        '0' => Ok(acc * 2),
        '1' => Ok(acc * 2 + 1),
        _ => Err(format!("invalid binary digit: {c}")),
    })
}

/// Solution 2: Recursive — mirrors the OCaml `go` helper
pub fn decimal_to_binary(n: u64) -> String {
    if n == 0 {
        return "0".to_string();
    }
    fn go(n: u64, acc: String) -> String {
        if n == 0 {
            acc
        } else {
            go(n / 2, format!("{}{}", n % 2, acc))
        }
    }
    go(n, String::new())
}

/// Solution 3: Idiomatic — build binary string with iterators (no recursion)
pub fn decimal_to_binary_iter(n: u64) -> String {
    if n == 0 {
        return "0".to_string();
    }
    let mut bits = Vec::new();
    let mut x = n;
    while x > 0 {
        bits.push((x % 2) as u8);
        x /= 2;
    }
    bits.iter().rev().map(|b| b.to_string()).collect()
}

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

    #[test]
    fn test_binary_to_decimal_basic() {
        assert_eq!(binary_to_decimal("1010"), Ok(10));
        assert_eq!(binary_to_decimal("11111"), Ok(31));
    }

    #[test]
    fn test_binary_to_decimal_zero() {
        assert_eq!(binary_to_decimal("0"), Ok(0));
        assert_eq!(binary_to_decimal("0000"), Ok(0));
    }

    #[test]
    fn test_binary_to_decimal_invalid() {
        assert!(binary_to_decimal("1012").is_err());
        assert!(binary_to_decimal("10a0").is_err());
    }

    #[test]
    fn test_decimal_to_binary_basic() {
        assert_eq!(decimal_to_binary(10), "1010");
        assert_eq!(decimal_to_binary(31), "11111");
    }

    #[test]
    fn test_decimal_to_binary_zero() {
        assert_eq!(decimal_to_binary(0), "0");
    }

    #[test]
    fn test_decimal_to_binary_iter_matches_recursive() {
        for n in [0u64, 1, 2, 10, 31, 42, 255, 1024] {
            assert_eq!(decimal_to_binary(n), decimal_to_binary_iter(n));
        }
    }

    #[test]
    fn test_roundtrip() {
        for s in ["1010", "11111", "101010"] {
            let d = binary_to_decimal(s).unwrap();
            assert_eq!(decimal_to_binary(d), s);
        }
    }
}

let binary_to_decimal s =
  String.fold_left (fun acc c ->
    match c with
    | '0' -> acc * 2
    | '1' -> acc * 2 + 1
    | _ -> failwith "invalid binary digit"
  ) 0 s

let decimal_to_binary n =
  if n = 0 then "0"
  else
    let rec go n acc =
      if n = 0 then acc
      else go (n / 2) (string_of_int (n mod 2) ^ acc)
    in go n ""

let () =
  assert (binary_to_decimal "1010" = 10);
  assert (binary_to_decimal "11111" = 31);
  assert (decimal_to_binary 10 = "1010");
  assert (decimal_to_binary 0 = "0");
  List.iter (fun s ->
    let d = binary_to_decimal s in
    assert (decimal_to_binary d = s)
  ) ["1010"; "11111"; "101010"];
  print_endline "ok"

✓ Tests Rust test suite

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

    #[test]
    fn test_binary_to_decimal_basic() {
        assert_eq!(binary_to_decimal("1010"), Ok(10));
        assert_eq!(binary_to_decimal("11111"), Ok(31));
    }

    #[test]
    fn test_binary_to_decimal_zero() {
        assert_eq!(binary_to_decimal("0"), Ok(0));
        assert_eq!(binary_to_decimal("0000"), Ok(0));
    }

    #[test]
    fn test_binary_to_decimal_invalid() {
        assert!(binary_to_decimal("1012").is_err());
        assert!(binary_to_decimal("10a0").is_err());
    }

    #[test]
    fn test_decimal_to_binary_basic() {
        assert_eq!(decimal_to_binary(10), "1010");
        assert_eq!(decimal_to_binary(31), "11111");
    }

    #[test]
    fn test_decimal_to_binary_zero() {
        assert_eq!(decimal_to_binary(0), "0");
    }

    #[test]
    fn test_decimal_to_binary_iter_matches_recursive() {
        for n in [0u64, 1, 2, 10, 31, 42, 255, 1024] {
            assert_eq!(decimal_to_binary(n), decimal_to_binary_iter(n));
        }
    }

    #[test]
    fn test_roundtrip() {
        for s in ["1010", "11111", "101010"] {
            let d = binary_to_decimal(s).unwrap();
            assert_eq!(decimal_to_binary(d), s);
        }
    }
}

Deep Comparison

OCaml vs Rust: Binary ↔ Decimal Fold

Side-by-Side Code

OCaml

let binary_to_decimal s =
  String.fold_left (fun acc c ->
    match c with
    | '0' -> acc * 2
    | '1' -> acc * 2 + 1
    | _ -> failwith "invalid binary digit"
  ) 0 s

let decimal_to_binary n =
  if n = 0 then "0"
  else
    let rec go n acc =
      if n = 0 then acc
      else go (n / 2) (string_of_int (n mod 2) ^ acc)
    in go n ""

Rust (idiomatic — try_fold)

pub fn binary_to_decimal(s: &str) -> Result<u64, String> {
    s.chars().try_fold(0u64, |acc, c| match c {
        '0' => Ok(acc * 2),
        '1' => Ok(acc * 2 + 1),
        _ => Err(format!("invalid binary digit: {c}")),
    })
}

Rust (functional/recursive decimal_to_binary)

pub fn decimal_to_binary(n: u64) -> String {
    if n == 0 {
        return "0".to_string();
    }
    fn go(n: u64, acc: String) -> String {
        if n == 0 {
            acc
        } else {
            go(n / 2, format!("{}{}", n % 2, acc))
        }
    }
    go(n, String::new())
}

Rust (iterative decimal_to_binary)

pub fn decimal_to_binary_iter(n: u64) -> String {
    if n == 0 {
        return "0".to_string();
    }
    let mut bits = Vec::new();
    let mut x = n;
    while x > 0 {
        bits.push((x % 2) as u8);
        x /= 2;
    }
    bits.iter().rev().map(|b| b.to_string()).collect()
}

Type Signatures

Concept	OCaml	Rust
binary→decimal	`val binary_to_decimal : string -> int`	`fn binary_to_decimal(s: &str) -> Result<u64, String>`
decimal→binary	`val decimal_to_binary : int -> string`	`fn decimal_to_binary(n: u64) -> String`
Error reporting	raises `Failure "invalid binary digit"`	returns `Err(String)`
Fold	`String.fold_left f init s`	`s.chars().try_fold(init, f)`
Accumulator	`int` (unbounded)	`u64` (64-bit unsigned)

Key Insights

**try_fold is fold_left with a short-circuit:** OCaml's fold_left continues regardless of intermediate state — if you want to abort on invalid input you need failwith. Rust's try_fold short-circuits the moment a closure returns Err, making error-aware folds first-class.

**No exceptions — Result at the boundary:** OCaml raises an exception that unwinds the call stack; callers must use try…with defensively. Rust returns Result<u64, String>, forcing callers to handle the error case explicitly — safer and more composable.

Inner functions for recursion: OCaml's let rec go … in go n "" pattern translates naturally to a Rust inner fn go inside the outer function. Rust inner functions are not closures — they cannot capture the enclosing scope — which matches the OCaml style exactly.

String accumulation strategy: OCaml uses ^ to prepend the new digit to the accumulator string, building the result right-to-left naturally. Rust's format!("{}{}", n % 2, acc) mirrors this. The iterative approach instead appends to a Vec and reverses — O(n) either way but avoids repeated string allocations.

Type precision: OCaml's int is platform-width and signed, meaning decimal_to_binary accepts negative numbers silently. Rust's u64 makes the domain explicit — negative inputs are a compile-time type error, not a runtime surprise.

When to Use Each Style

**Use try_fold (idiomatic Rust):** Any time you fold over an iterator and individual steps may fail. It is the standard Rust idiom for validated accumulation and composes cleanly with ?.

**Use recursive go helper:** When you want the code to read closest to the OCaml original, or when the problem is naturally expressed as a decreasing recursion with an accumulator. Good for teaching the OCaml→Rust translation.

**Use iterative decimal_to_binary_iter:** When performance matters and you want to avoid stack growth from deep recursion on large numbers. Collecting into a Vec then reversing is idiomatic Rust and avoids repeated string re-allocation.

Exercises

Generalize the fold-based conversion to support arbitrary base conversions (not just binary↔decimal): implement to_base_n and from_base_n for any base 2–36.

Implement big-integer addition by representing numbers as little-endian Vec<u8> digits and using a fold to add digit-by-digit with carry propagation.

Write a fold-based parser for simple integer literals that handles decimal, hexadecimal (0x prefix), and binary (0b prefix) notation, returning Result<u64, ParseError>.

Open Source Repos

functional-rust

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

Rust