184 Expert

Introduction to Free Monads

Functional Programming

Tutorial

The Problem

Free monads separate the description of a computation from its execution. A program built from free monad operations is a pure data structure — a tree of instructions. Different interpreters can then execute the same program in different ways: one runs it against a real console, another tests it with mocked input/output, a third logs every operation. This separation enables dependency injection at the computation level, pure testing without mocks, and multiple execution strategies for the same program description.

🎯 Learning Outcomes

• Understand the free monad as a way to separate program description from interpretation

• Learn to build a simple console DSL using the Console<A> enum

• See how Print and GetLine operations form a tree of deferred computations

• Understand the connection between free monads and effect systems

Code Example

enum Console<A> {
    Pure(A),
    Print(String, Box<Console<A>>),
    GetLine(Box<dyn FnOnce(String) -> Console<A>>),
}

type 'next console_f =
  | Print of string * 'next
  | GetLine of (string -> 'next)

type 'a console =
  | CPure of 'a
  | CFree of 'a console console_f

Key Differences

**let* syntax**: OCaml's monadic bind notation makes free monad programs readable; Rust lacks similar syntax sugar, requiring explicit closures.

FnOnce continuations: Rust uses Box<dyn FnOnce(String) -> Console<A>> for GetLine; OCaml uses string -> 'a console — structurally identical.

Functor instance: OCaml's free monad requires a Functor instance on the base functor; Rust builds the monad directly as an enum without abstracting over the functor.

Performance: Free monads build a heap-allocated tree; interpreting large programs is slower than direct execution; algebraic effects (example 189) are more efficient.

OCaml Approach

OCaml's free monad uses GADTs for type safety:

type _ console =
  | Pure : 'a -> 'a console
  | Print : string * (unit -> 'a console) -> 'a console
  | GetLine : (string -> 'a console) -> 'a console
let ( >>= ) : 'a console -> ('a -> 'b console) -> 'b console = ...

OCaml's let* syntax makes writing free monad programs feel almost imperative:

let program = let* () = print "Enter name: " in
              let* name = get_line () in
              print ("Hello, " ^ name)

Full Source

#![allow(clippy::all)]
// Example 184: Introduction to Free Monads
// Separate program description from interpretation

// === Approach 1: Free monad as enum ===

enum Console<A> {
    Pure(A),
    Print(String, Box<Console<A>>),
    GetLine(Box<dyn FnOnce(String) -> Console<A>>),
}

impl<A> Console<A> {
    fn pure(a: A) -> Self {
        Console::Pure(a)
    }
}

fn console_print(msg: &str) -> Console<()> {
    Console::Print(msg.to_string(), Box::new(Console::Pure(())))
}

fn console_get_line() -> Console<String> {
    Console::GetLine(Box::new(Console::Pure))
}

// bind (flatmap) — chain free monad computations
fn bind<A: 'static, B: 'static>(
    ma: Console<A>,
    f: impl FnOnce(A) -> Console<B> + 'static,
) -> Console<B> {
    match ma {
        Console::Pure(a) => f(a),
        Console::Print(msg, next) => Console::Print(msg, Box::new(bind(*next, f))),
        Console::GetLine(k) => Console::GetLine(Box::new(move |s| bind(k(s), f))),
    }
}

// === Approach 2: Pure interpreter (collects output, feeds input) ===

fn interpret_pure(inputs: &[&str], prog: Console<String>) -> (Vec<String>, String) {
    let mut outputs = Vec::new();
    let mut input_idx = 0;
    let mut current = prog;

    loop {
        match current {
            Console::Pure(a) => return (outputs, a),
            Console::Print(msg, next) => {
                outputs.push(msg);
                current = *next;
            }
            Console::GetLine(k) => {
                let input = inputs.get(input_idx).unwrap_or(&"");
                input_idx += 1;
                current = k(input.to_string());
            }
        }
    }
}

// === Approach 3: Builder-style DSL with macro ===

fn greet_program() -> Console<String> {
    bind(console_print("What is your name?"), move |()| {
        bind(console_get_line(), move |name: String| {
            bind(console_print(&format!("Hello, {}!", name)), move |()| {
                Console::pure(name)
            })
        })
    })
}

// Alternate: sequence of operations without result threading
fn log_program(messages: Vec<String>) -> Console<()> {
    let mut prog = Console::pure(());
    // Build in reverse
    for msg in messages.into_iter().rev() {
        let next = prog;
        prog = Console::Print(msg, Box::new(next));
    }
    prog
}

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

    #[test]
    fn test_pure() {
        let (outputs, result) = interpret_pure(&[], Console::pure("hello".to_string()));
        assert!(outputs.is_empty());
        assert_eq!(result, "hello");
    }

    #[test]
    fn test_greet_alice() {
        let (outputs, result) = interpret_pure(&["Alice"], greet_program());
        assert_eq!(outputs, vec!["What is your name?", "Hello, Alice!"]);
        assert_eq!(result, "Alice");
    }

    #[test]
    fn test_greet_bob() {
        let (outputs, result) = interpret_pure(&["Bob"], greet_program());
        assert_eq!(outputs, vec!["What is your name?", "Hello, Bob!"]);
        assert_eq!(result, "Bob");
    }

    #[test]
    fn test_print_only() {
        let prog = bind(console_print("hi"), |()| Console::pure("done".to_string()));
        let (outputs, result) = interpret_pure(&[], prog);
        assert_eq!(outputs, vec!["hi"]);
        assert_eq!(result, "done");
    }

    #[test]
    fn test_get_line() {
        let prog = bind(console_get_line(), |s: String| Console::pure(s));
        let (_, result) = interpret_pure(&["test"], prog);
        assert_eq!(result, "test");
    }
}

(* Example 184: Introduction to Free Monads *)
(* Separate program description from interpretation *)

(* Approach 1: Basic Free monad *)
type ('f, 'a) free =
  | Pure of 'a
  | Free of ('f, 'a) free 'f
(* OCaml can't directly express higher-kinded types for Free,
   so we specialize for a concrete functor *)

(* Approach 1: Free monad specialized for a simple DSL *)
type 'next console_f =
  | Print of string * 'next
  | GetLine of (string -> 'next)

type 'a console =
  | CPure of 'a
  | CFree of 'a console console_f

let print msg = CFree (Print (msg, CPure ()))
let get_line () = CFree (GetLine (fun s -> CPure s))

let rec bind : type a b. a console -> (a -> b console) -> b console =
  fun m f -> match m with
  | CPure a -> f a
  | CFree (Print (msg, next)) -> CFree (Print (msg, bind next f))
  | CFree (GetLine k) -> CFree (GetLine (fun s -> bind (k s) f))

let (>>=) = bind
let return_ x = CPure x

(* Approach 2: Interpret to string list (pure) *)
let rec interpret_pure (inputs : string list) (prog : 'a console) : string list * 'a =
  match prog with
  | CPure a -> ([], a)
  | CFree (Print (msg, next)) ->
    let (outputs, result) = interpret_pure inputs next in
    (msg :: outputs, result)
  | CFree (GetLine k) ->
    (match inputs with
     | [] -> failwith "No more input"
     | x :: rest -> interpret_pure rest (k x))

(* Approach 3: Chain operations *)
let program =
  print "What is your name?" >>= fun () ->
  get_line () >>= fun name ->
  print ("Hello, " ^ name ^ "!") >>= fun () ->
  return_ name

let () =
  (* Test pure interpretation *)
  let (outputs, result) = interpret_pure ["Alice"] program in
  assert (outputs = ["What is your name?"; "Hello, Alice!"]);
  assert (result = "Alice");

  let (outputs2, _) = interpret_pure ["Bob"] program in
  assert (outputs2 = ["What is your name?"; "Hello, Bob!"]);

  (* Test simple programs *)
  let (out, _) = interpret_pure [] (print "hi") in
  assert (out = ["hi"]);

  let (_, v) = interpret_pure ["test"] (get_line ()) in
  assert (v = "test");

  print_endline "✓ All tests passed"

✓ Tests Rust test suite

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

    #[test]
    fn test_pure() {
        let (outputs, result) = interpret_pure(&[], Console::pure("hello".to_string()));
        assert!(outputs.is_empty());
        assert_eq!(result, "hello");
    }

    #[test]
    fn test_greet_alice() {
        let (outputs, result) = interpret_pure(&["Alice"], greet_program());
        assert_eq!(outputs, vec!["What is your name?", "Hello, Alice!"]);
        assert_eq!(result, "Alice");
    }

    #[test]
    fn test_greet_bob() {
        let (outputs, result) = interpret_pure(&["Bob"], greet_program());
        assert_eq!(outputs, vec!["What is your name?", "Hello, Bob!"]);
        assert_eq!(result, "Bob");
    }

    #[test]
    fn test_print_only() {
        let prog = bind(console_print("hi"), |()| Console::pure("done".to_string()));
        let (outputs, result) = interpret_pure(&[], prog);
        assert_eq!(outputs, vec!["hi"]);
        assert_eq!(result, "done");
    }

    #[test]
    fn test_get_line() {
        let prog = bind(console_get_line(), |s: String| Console::pure(s));
        let (_, result) = interpret_pure(&["test"], prog);
        assert_eq!(result, "test");
    }
}

Deep Comparison

Comparison: Example 184 — Free Monad Introduction

Free Monad Type

OCaml

type 'next console_f =
  | Print of string * 'next
  | GetLine of (string -> 'next)

type 'a console =
  | CPure of 'a
  | CFree of 'a console console_f

Rust

enum Console<A> {
    Pure(A),
    Print(String, Box<Console<A>>),
    GetLine(Box<dyn FnOnce(String) -> Console<A>>),
}

Bind (FlatMap)

OCaml

let rec bind m f = match m with
  | CPure a -> f a
  | CFree (Print (msg, next)) -> CFree (Print (msg, bind next f))
  | CFree (GetLine k) -> CFree (GetLine (fun s -> bind (k s) f))

Rust

fn bind<A: 'static, B: 'static>(
    ma: Console<A>, f: impl FnOnce(A) -> Console<B> + 'static,
) -> Console<B> {
    match ma {
        Console::Pure(a) => f(a),
        Console::Print(msg, next) => Console::Print(msg, Box::new(bind(*next, f))),
        Console::GetLine(k) => Console::GetLine(Box::new(move |s| bind(k(s), f))),
    }
}

Program Construction

OCaml

let program =
  print "What is your name?" >>= fun () ->
  get_line () >>= fun name ->
  print ("Hello, " ^ name ^ "!") >>= fun () ->
  return_ name

Rust

fn greet_program() -> Console<String> {
    bind(Console::print("What is your name?"), move |()| {
        bind(Console::get_line(), move |name: String| {
            bind(Console::print(&format!("Hello, {}!", name)), move |()| {
                Console::pure(name)
            })
        })
    })
}

Pure Interpreter

OCaml

let rec interpret_pure inputs prog = match prog with
  | CPure a -> ([], a)
  | CFree (Print (msg, next)) ->
    let (outputs, result) = interpret_pure inputs next in
    (msg :: outputs, result)
  | CFree (GetLine k) -> interpret_pure (List.tl inputs) (k (List.hd inputs))

Rust

fn interpret_pure(inputs: &[&str], prog: Console<String>) -> (Vec<String>, String) {
    let mut current = prog;
    let mut outputs = Vec::new();
    let mut idx = 0;
    loop {
        match current {
            Console::Pure(a) => return (outputs, a),
            Console::Print(msg, next) => { outputs.push(msg); current = *next; }
            Console::GetLine(k) => { current = k(inputs[idx].into()); idx += 1; }
        }
    }
}

Exercises

Add a ReadFile(path: String, continuation: Box<dyn FnOnce(String) -> Console<A>>) operation.

Write a test interpreter that provides mock input and captures output in a Vec<String>.

Implement a logging interpreter that wraps every operation with println!("[LOG] ...") before executing it.

Open Source Repos

functional-rust

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

Rust