599 Expert

Free monad rust

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Free monad 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

#![allow(clippy::all)]
//! # Free Monad
//!
//! Build monadic DSLs where the structure is data, interpretation is separate.

/// Free monad over a functor F.
pub enum Free<F, A> {
    Pure(A),
    Suspend(F),
}

/// Simple DSL for key-value operations.

pub enum KvOp<Next> {
    Get(String, Box<dyn Fn(Option<String>) -> Next>),
    Put(String, String, Box<dyn Fn(()) -> Next>),
}

/// A simpler, concrete approach for demonstration.

pub enum KvDsl {
    Get(String),
    Put(String, String),
    Pure(String),
    Bind(Box<KvDsl>, String), // simplified
}

/// Interpret DSL with a HashMap.
pub fn interpret(dsl: &KvDsl, store: &mut std::collections::HashMap<String, String>) -> String {
    match dsl {
        KvDsl::Get(k) => store.get(k).cloned().unwrap_or_default(),
        KvDsl::Put(k, v) => {
            store.insert(k.clone(), v.clone());
            String::new()
        }
        KvDsl::Pure(v) => v.clone(),
        KvDsl::Bind(inner, _) => interpret(inner, store),
    }
}

/// Build a get operation.
pub fn get(key: &str) -> KvDsl {
    KvDsl::Get(key.to_string())
}

/// Build a put operation.
pub fn put(key: &str, value: &str) -> KvDsl {
    KvDsl::Put(key.to_string(), value.to_string())
}

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

    #[test]
    fn test_put_get() {
        let mut store = HashMap::new();
        interpret(&put("x", "42"), &mut store);
        let result = interpret(&get("x"), &mut store);
        assert_eq!(result, "42");
    }

    #[test]
    fn test_get_missing() {
        let mut store = HashMap::new();
        let result = interpret(&get("missing"), &mut store);
        assert_eq!(result, "");
    }
}

(* Free monad in OCaml *)
type ('f, 'a) free =
  | Pure of 'a
  | Free of ('f * (('f,'a) free))  (* simplified *)

(* Console language *)
type 'a console_f =
  | Print of string * 'a
  | ReadLine of (string -> 'a)

type 'a console = ('a console_f, 'a) free

let print_line s k = Free (Print (s, Pure ()), (fun () -> k ()))
let read_line k    = Free (ReadLine k, (fun _ -> Pure ()))

(* Simplified: just describe the program *)
type program =
  | Print of string * program
  | Read  of (string -> program)
  | Done

let rec interpret log_buf = function
  | Done       -> ()
  | Print(s,k) -> Buffer.add_string log_buf (s^"\n"); interpret log_buf k
  | Read f     -> interpret log_buf (f "simulated-input")

let () =
  let prog =
    Print("What is your name?",
    Read(fun name ->
    Print(Printf.sprintf "Hello, %s!" name,
    Done))) in
  let buf = Buffer.create 64 in
  interpret buf prog;
  print_string (Buffer.contents buf)

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)]
//! # Free Monad
//!
//! Build monadic DSLs where the structure is data, interpretation is separate.

/// Free monad over a functor F.
pub enum Free<F, A> {
    Pure(A),
    Suspend(F),
}

/// Simple DSL for key-value operations.

pub enum KvOp<Next> {
    Get(String, Box<dyn Fn(Option<String>) -> Next>),
    Put(String, String, Box<dyn Fn(()) -> Next>),
}

/// A simpler, concrete approach for demonstration.

pub enum KvDsl {
    Get(String),
    Put(String, String),
    Pure(String),
    Bind(Box<KvDsl>, String), // simplified
}

/// Interpret DSL with a HashMap.
pub fn interpret(dsl: &KvDsl, store: &mut std::collections::HashMap<String, String>) -> String {
    match dsl {
        KvDsl::Get(k) => store.get(k).cloned().unwrap_or_default(),
        KvDsl::Put(k, v) => {
            store.insert(k.clone(), v.clone());
            String::new()
        }
        KvDsl::Pure(v) => v.clone(),
        KvDsl::Bind(inner, _) => interpret(inner, store),
    }
}

/// Build a get operation.
pub fn get(key: &str) -> KvDsl {
    KvDsl::Get(key.to_string())
}

/// Build a put operation.
pub fn put(key: &str, value: &str) -> KvDsl {
    KvDsl::Put(key.to_string(), value.to_string())
}

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

    #[test]
    fn test_put_get() {
        let mut store = HashMap::new();
        interpret(&put("x", "42"), &mut store);
        let result = interpret(&get("x"), &mut store);
        assert_eq!(result, "42");
    }

    #[test]
    fn test_get_missing() {
        let mut store = HashMap::new();
        let result = interpret(&get("missing"), &mut store);
        assert_eq!(result, "");
    }
}

(* Free monad in OCaml *)
type ('f, 'a) free =
  | Pure of 'a
  | Free of ('f * (('f,'a) free))  (* simplified *)

(* Console language *)
type 'a console_f =
  | Print of string * 'a
  | ReadLine of (string -> 'a)

type 'a console = ('a console_f, 'a) free

let print_line s k = Free (Print (s, Pure ()), (fun () -> k ()))
let read_line k    = Free (ReadLine k, (fun _ -> Pure ()))

(* Simplified: just describe the program *)
type program =
  | Print of string * program
  | Read  of (string -> program)
  | Done

let rec interpret log_buf = function
  | Done       -> ()
  | Print(s,k) -> Buffer.add_string log_buf (s^"\n"); interpret log_buf k
  | Read f     -> interpret log_buf (f "simulated-input")

let () =
  let prog =
    Print("What is your name?",
    Read(fun name ->
    Print(Printf.sprintf "Hello, %s!" name,
    Done))) in
  let buf = Buffer.create 64 in
  interpret buf prog;
  print_string (Buffer.contents buf)

✓ Tests Rust test suite

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

    #[test]
    fn test_put_get() {
        let mut store = HashMap::new();
        interpret(&put("x", "42"), &mut store);
        let result = interpret(&get("x"), &mut store);
        assert_eq!(result, "42");
    }

    #[test]
    fn test_get_missing() {
        let mut store = HashMap::new();
        let result = interpret(&get("missing"), &mut store);
        assert_eq!(result, "");
    }
}

Deep Comparison

Free Monad

Key Idea

Separate DSL structure from interpretation:

Define operations as a functor

Wrap in Free to get monadic sequencing

Interpret with different backends

Benefits

• Testable - Mock interpretation

• Composable - Combine DSLs

• Analyzable - Inspect/optimize before running

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