597 Expert

Scott encoding rust

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Scott encoding rust" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. This example explores advanced type theory concepts applied to Rust. Key difference from OCaml: 1. **HKT gap**: Haskell and partly OCaml have higher

Tutorial

The Problem

This example explores advanced type theory concepts applied to Rust. Church encoding, Scott encoding, finally tagless, free monads, and effect systems are all techniques from the typed lambda calculus and category theory research community. They demonstrate how to encode data and control as pure functions, how to build extensible DSLs without committing to a representation, and how to model effects as values rather than side effects. These patterns originate in Haskell and OCaml research and require adapting to Rust's ownership model.

🎯 Learning Outcomes

• The theoretical foundation of this encoding/pattern from type theory

• How it maps to Rust's type system using traits, generics, and higher-kinded type emulation

• The practical limitations and verbosity compared to Haskell/OCaml implementations

• When this pattern provides genuine value vs when simpler alternatives suffice

• Real systems that use these ideas: compilers, effect libraries, DSL frameworks

Code Example

fn scott_match_option<A, T>(
    opt: Option<A>,
    on_none: impl Fn() -> T,
    on_some: impl Fn(A) -> T,
) -> T {
    match opt { None => on_none(), Some(a) => on_some(a) }
}

(* Scott encoding in OCaml *)
(* Scott Bool: same as Church Bool *)
(* Scott List: cons h t nil_case cons_case = cons_case h t *)

(* Scott Maybe *)
let scott_none none_case _some_case = none_case
let scott_some v _none_case some_case = some_case v

(* Usage: match on encoded Maybe *)
let scott_match_maybe m on_none on_some = m on_none on_some

let () =
  let none = scott_none in
  let some42 = scott_some 42 in
  Printf.printf "none: %d\n" (scott_match_maybe none 0 (fun v -> v));
  Printf.printf "some 42: %d\n" (scott_match_maybe some42 0 (fun v -> v));

  (* Scott List *)
  let scott_nil  nil_f _cons_f = nil_f () in
  let scott_cons h t nil_f cons_f = cons_f h t in

  let lst = scott_cons 1 (scott_cons 2 (scott_cons 3 scott_nil)) in

  let rec to_list encoded =
    encoded (fun () -> []) (fun h t -> h :: to_list t) in
  Printf.printf "list: %s\n"
    (String.concat "," (List.map string_of_int (to_list lst)))

Key Differences

HKT gap: Haskell and partly OCaml have higher-kinded types; Rust uses GATs and trait tricks as approximations — significantly more verbose.

Type inference: OCaml's HM inference handles these patterns cleanly; Rust often requires explicit type annotations throughout.

Practical value: In Haskell, these patterns are common in production code; in Rust, simpler alternatives (enums + match) usually suffice.

Research to practice: These patterns showcase Rust's expressiveness limits and inspire ongoing language design work (GATs, async traits, HKT proposals).

OCaml Approach

OCaml is the natural home for these patterns — they originate in the ML/Haskell research community:

(* OCaml's polymorphism and first-class modules make these patterns
   more elegant than in Rust. Higher-kinded types are emulated in OCaml
   using functors and first-class modules rather than GATs. *)

Full Source

#![allow(clippy::all)]
//! # Scott Encoding
//!
//! Alternative to Church encoding using pattern matching style.

/// Scott-encoded natural numbers.
pub enum ScottNat<T> {
    Zero(Box<dyn Fn() -> T>),
    Succ(Box<dyn Fn(ScottNat<T>) -> T>),
}

/// Scott-encoded boolean.
pub fn scott_true<T>(on_true: T, _on_false: T) -> T {
    on_true
}

pub fn scott_false<T>(_on_true: T, on_false: T) -> T {
    on_false
}

/// Scott-encoded Option.
pub enum ScottOption<A, T> {
    None(Box<dyn Fn() -> T>),
    Some(Box<dyn Fn(A) -> T>),
}

/// Simple Scott-like pattern matching simulation.
pub fn scott_match_bool<T>(b: bool, on_true: impl Fn() -> T, on_false: impl Fn() -> T) -> T {
    if b {
        on_true()
    } else {
        on_false()
    }
}

/// Scott-like Option matching.
pub fn scott_match_option<A, T>(
    opt: Option<A>,
    on_none: impl Fn() -> T,
    on_some: impl Fn(A) -> T,
) -> T {
    match opt {
        None => on_none(),
        Some(a) => on_some(a),
    }
}

/// Scott-like Result matching.
pub fn scott_match_result<A, E, T>(
    res: Result<A, E>,
    on_ok: impl Fn(A) -> T,
    on_err: impl Fn(E) -> T,
) -> T {
    match res {
        Ok(a) => on_ok(a),
        Err(e) => on_err(e),
    }
}

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

    #[test]
    fn test_scott_bool() {
        assert_eq!(scott_true(1, 2), 1);
        assert_eq!(scott_false(1, 2), 2);
    }

    #[test]
    fn test_scott_match_bool() {
        assert_eq!(scott_match_bool(true, || "yes", || "no"), "yes");
        assert_eq!(scott_match_bool(false, || "yes", || "no"), "no");
    }

    #[test]
    fn test_scott_match_option() {
        assert_eq!(scott_match_option(Some(42), || 0, |x| x * 2), 84);
        assert_eq!(scott_match_option(None::<i32>, || 0, |x| x * 2), 0);
    }

    #[test]
    fn test_scott_match_result() {
        let ok: Result<i32, &str> = Ok(10);
        let err: Result<i32, &str> = Err("oops");
        assert_eq!(scott_match_result(ok, |x| x, |_| -1), 10);
        assert_eq!(scott_match_result(err, |x| x, |_| -1), -1);
    }
}

(* Scott encoding in OCaml *)
(* Scott Bool: same as Church Bool *)
(* Scott List: cons h t nil_case cons_case = cons_case h t *)

(* Scott Maybe *)
let scott_none none_case _some_case = none_case
let scott_some v _none_case some_case = some_case v

(* Usage: match on encoded Maybe *)
let scott_match_maybe m on_none on_some = m on_none on_some

let () =
  let none = scott_none in
  let some42 = scott_some 42 in
  Printf.printf "none: %d\n" (scott_match_maybe none 0 (fun v -> v));
  Printf.printf "some 42: %d\n" (scott_match_maybe some42 0 (fun v -> v));

  (* Scott List *)
  let scott_nil  nil_f _cons_f = nil_f () in
  let scott_cons h t nil_f cons_f = cons_f h t in

  let lst = scott_cons 1 (scott_cons 2 (scott_cons 3 scott_nil)) in

  let rec to_list encoded =
    encoded (fun () -> []) (fun h t -> h :: to_list t) in
  Printf.printf "list: %s\n"
    (String.concat "," (List.map string_of_int (to_list lst)))

✓ Tests Rust test suite

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

    #[test]
    fn test_scott_bool() {
        assert_eq!(scott_true(1, 2), 1);
        assert_eq!(scott_false(1, 2), 2);
    }

    #[test]
    fn test_scott_match_bool() {
        assert_eq!(scott_match_bool(true, || "yes", || "no"), "yes");
        assert_eq!(scott_match_bool(false, || "yes", || "no"), "no");
    }

    #[test]
    fn test_scott_match_option() {
        assert_eq!(scott_match_option(Some(42), || 0, |x| x * 2), 84);
        assert_eq!(scott_match_option(None::<i32>, || 0, |x| x * 2), 0);
    }

    #[test]
    fn test_scott_match_result() {
        let ok: Result<i32, &str> = Ok(10);
        let err: Result<i32, &str> = Err("oops");
        assert_eq!(scott_match_result(ok, |x| x, |_| -1), 10);
        assert_eq!(scott_match_result(err, |x| x, |_| -1), -1);
    }
}

Deep Comparison

OCaml vs Rust: Scott Encoding

Scott encoding represents data by its eliminator (pattern match).

Key Idea

Instead of storing data, store what you would do with each case:

• True = λt.λf. t

• False = λt.λf. f

• Some(x) = λnone.λsome. some(x)

• None = λnone.λsome. none()

Rust Implementation

fn scott_match_option<A, T>(
    opt: Option<A>,
    on_none: impl Fn() -> T,
    on_some: impl Fn(A) -> T,
) -> T {
    match opt { None => on_none(), Some(a) => on_some(a) }
}

vs Church Encoding

Aspect	Church	Scott
Focus	Iteration	Pattern matching
Numbers	Apply f N times	Match zero/succ
Lists	Fold	Match nil/cons

Exercises

Minimal implementation: Implement the simplest possible version of this pattern for a two-case example (e.g., for Church encoding, for finally tagless).

Add an interpreter: If the pattern supports multiple interpretations (like finally tagless), add a second interpreter (e.g., a pretty-printer in addition to an evaluator).

Comparison: Implement the same functionality using a plain enum + match — compare the code size, type safety, and extensibility of both approaches.

Open Source Repos

functional-rust

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

Rust