199 Expert

Scott Encoding

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Scott Encoding" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. Scott encoding is an alternative to Church encoding that represents data as pattern matches — a function that takes one continuation per constructor. Key difference from OCaml: 1. **Pattern match access**: Scott encoding gives O(1) `head`/`tail` (pattern match access); Church encoding gives O(1) fold but O(n) pattern match equivalent.

Tutorial

The Problem

Scott encoding is an alternative to Church encoding that represents data as pattern matches — a function that takes one continuation per constructor. Where Church encoding ties data to iteration, Scott encoding ties data to pattern matching. Scott-encoded natural numbers and lists support O(1) head and tail (Church lists need O(n) to access the tail), making Scott encoding more practical for functional data structures. It is the basis for how some functional compilers represent data types at runtime.

🎯 Learning Outcomes

• Understand Scott encoding as "data as its own eliminator"

• Compare Scott encoding to Church encoding: pattern match vs. iteration

• See how match in functional languages maps to Scott's continuation-passing pattern

• Learn why Scott encoding is preferable to Church encoding for pattern-matching-heavy code

Code Example

#![allow(clippy::all)]
// Stub — awaiting conversion from OCaml source.

(* Scott encoding: represent each constructor as a function that
   takes one continuation per constructor (i.e., a fold/eliminator).
   Unlike Church encoding, enables O(1) pattern matching. *)

(* Scott-encoded Option: none k_none k_some = k_none
                         some x k_none k_some = k_some x *)
let none   k_none _k_some     = k_none ()
let some x _k_none k_some     = k_some x

let is_none o = o (fun () -> true)  (fun _ -> false)
let is_some o = o (fun () -> false) (fun _ -> true)
let get_or def o = o (fun () -> def) (fun x -> x)
let map_opt f o = o (fun () -> none) (fun x -> some (f x))

(* Scott-encoded List *)
let snil  k_nil _k_cons       = k_nil ()
let scons x xs _k_nil k_cons  = k_cons x xs

let head_or def lst = lst (fun () -> def) (fun x _ -> x)
let tail_opt lst    = lst (fun () -> none) (fun _ xs -> some xs)

let rec to_list l =
  l (fun () -> []) (fun x xs -> x :: to_list xs)

let () =
  (* Option *)
  let n = none and s = some 42 in
  Printf.printf "is_none none  = %b\n" (is_none n);
  Printf.printf "is_some some  = %b\n" (is_some s);
  Printf.printf "get_or 0 some = %d\n" (get_or 0 s);

  let doubled = map_opt (fun x -> x * 2) s in
  Printf.printf "map *2 some42 = %d\n" (get_or 0 doubled);

  (* List *)
  let lst = scons 1 (scons 2 (scons 3 snil)) in
  Printf.printf "head = %d\n"  (head_or 0 lst);
  Printf.printf "list = [%s]\n" (to_list lst |> List.map string_of_int |> String.concat ";")

Key Differences

Pattern match access: Scott encoding gives O(1) head/tail (pattern match access); Church encoding gives O(1) fold but O(n) pattern match equivalent.

Practical use: Scott encoding is how GHC's Core represents algebraic data types internally — each constructor is a "case expression" applicand.

Type verbosity: Scott encoding in Rust requires deeply nested Box<dyn Fn> types; OCaml infers all types automatically.

Elimination principle: Church encoding embeds the iteration scheme (fold); Scott encoding embeds the pattern match (case expression) — mathematically dual approaches.

OCaml Approach

OCaml's variant types are the standard encoding; Scott encoding is the lambda calculus explanation of how they work:

(* Scott natural number: one continuation per constructor *)
let zero zero_c _succ_c = zero_c
let succ n _zero_c succ_c = succ_c n
let predecessor n = n (fun () -> zero) (fun prev -> prev)

In OCaml, this is purely educational — actual code uses type nat = Zero | Succ of nat with pattern matching.

Full Source

#![allow(clippy::all)]
// Stub — awaiting conversion from OCaml source.

(* Scott encoding: represent each constructor as a function that
   takes one continuation per constructor (i.e., a fold/eliminator).
   Unlike Church encoding, enables O(1) pattern matching. *)

(* Scott-encoded Option: none k_none k_some = k_none
                         some x k_none k_some = k_some x *)
let none   k_none _k_some     = k_none ()
let some x _k_none k_some     = k_some x

let is_none o = o (fun () -> true)  (fun _ -> false)
let is_some o = o (fun () -> false) (fun _ -> true)
let get_or def o = o (fun () -> def) (fun x -> x)
let map_opt f o = o (fun () -> none) (fun x -> some (f x))

(* Scott-encoded List *)
let snil  k_nil _k_cons       = k_nil ()
let scons x xs _k_nil k_cons  = k_cons x xs

let head_or def lst = lst (fun () -> def) (fun x _ -> x)
let tail_opt lst    = lst (fun () -> none) (fun _ xs -> some xs)

let rec to_list l =
  l (fun () -> []) (fun x xs -> x :: to_list xs)

let () =
  (* Option *)
  let n = none and s = some 42 in
  Printf.printf "is_none none  = %b\n" (is_none n);
  Printf.printf "is_some some  = %b\n" (is_some s);
  Printf.printf "get_or 0 some = %d\n" (get_or 0 s);

  let doubled = map_opt (fun x -> x * 2) s in
  Printf.printf "map *2 some42 = %d\n" (get_or 0 doubled);

  (* List *)
  let lst = scons 1 (scons 2 (scons 3 snil)) in
  Printf.printf "head = %d\n"  (head_or 0 lst);
  Printf.printf "list = [%s]\n" (to_list lst |> List.map string_of_int |> String.concat ";")

Deep Comparison

OCaml vs Rust: Scott Encoding

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

Implement Scott-encoded lists with nil, cons, head, and tail operations.

Verify that predecessor(succ(succ(zero))) produces succ(zero) using scott_to_int.

Implement add_scott for Scott naturals — it will be more complex than Church's add because you need to recurse differently.

Open Source Repos

functional-rust

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

Rust