187 Expert

Free Monad with State

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Free Monad with State" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. Combining the free monad pattern with state — a mutable counter, accumulator, or environment — requires threading state through the interpreter. Key difference from OCaml: 1. **State threading**: Both pass state as an accumulator through recursive calls; neither uses mutable state in the interpreter.

Tutorial

The Problem

Combining the free monad pattern with state — a mutable counter, accumulator, or environment — requires threading state through the interpreter. A state-carrying free monad DSL enables programs that read and write state as pure operations, with the actual state management happening in the interpreter. This models how database transactions, accumulating computations, and stateful protocols can be expressed purely and tested without mutable global state.

🎯 Learning Outcomes

• Extend a free monad DSL with Get and Put state operations

• Implement an interpreter that threads state through computation

• See how stateful programs are expressed as pure trees with state operations at the leaves

• Understand the connection between free monad state and the state monad

Code Example

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

(* State monad encoded as a free monad.
   No mutation — the state is threaded through the interpreter. *)

type 's state_f =
  | Get : ('s -> 'a) -> 'a state_f
  | Put : 's * 'a -> 'a state_f

type 'a free =
  | Pure : 'a -> 'a free
  | Free : 'a free state_f -> 'a free

let get ()   = Free (Get  (fun s -> Pure s))
let put s    = Free (Put  (s, Pure ()))

let rec bind m f = match m with
  | Pure x -> f x
  | Free (Get cont)    -> Free (Get  (fun s -> bind (cont s) f))
  | Free (Put (s, n))  -> Free (Put  (s, bind n f))

let run init program =
  let rec go s = function
    | Pure x          -> (x, s)
    | Free (Get cont) -> go s (cont s)
    | Free (Put (s', next)) -> go s' next
  in go init program

let () =
  (* Increment counter 3 times *)
  let program =
    bind (get ()) (fun n ->
    bind (put (n + 1)) (fun () ->
    bind (get ()) (fun n ->
    bind (put (n + 1)) (fun () ->
    bind (get ()) (fun n ->
    bind (put (n + 1)) (fun () ->
    bind (get ()) (fun final ->
    Pure final)))))))
  in
  let (result, final_state) = run 0 program in
  Printf.printf "result=%d state=%d\n" result final_state;
  assert (result = 3 && final_state = 3);
  Printf.printf "State free monad works\n"

Key Differences

State threading: Both pass state as an accumulator through recursive calls; neither uses mutable state in the interpreter.

OCaml effects: OCaml 5 effects replace free monad state with a cleaner effect Get : int declaration and a single match_with handler.

Composability: Free monad state composes with other DSL operations (Print, ReadLine) by building larger sum types; OCaml effects compose automatically.

Stack depth: Stateful programs with many operations risk stack overflow; both languages need trampolining for deeply recursive state operations.

OCaml Approach

OCaml's state monad and free monad can be combined:

type _ state_op =
  | Get : (int -> 'a state_op) -> 'a state_op
  | Put : int * (unit -> 'a state_op) -> 'a state_op
  | Pure : 'a -> 'a state_op

The interpreter run_state : 'a state_op -> int -> 'a * int has the same structure. OCaml 5's effect handlers can express this more directly: effect Get : int and effect Put : int -> unit with an match_with handler that carries state.

Full Source

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

(* State monad encoded as a free monad.
   No mutation — the state is threaded through the interpreter. *)

type 's state_f =
  | Get : ('s -> 'a) -> 'a state_f
  | Put : 's * 'a -> 'a state_f

type 'a free =
  | Pure : 'a -> 'a free
  | Free : 'a free state_f -> 'a free

let get ()   = Free (Get  (fun s -> Pure s))
let put s    = Free (Put  (s, Pure ()))

let rec bind m f = match m with
  | Pure x -> f x
  | Free (Get cont)    -> Free (Get  (fun s -> bind (cont s) f))
  | Free (Put (s, n))  -> Free (Put  (s, bind n f))

let run init program =
  let rec go s = function
    | Pure x          -> (x, s)
    | Free (Get cont) -> go s (cont s)
    | Free (Put (s', next)) -> go s' next
  in go init program

let () =
  (* Increment counter 3 times *)
  let program =
    bind (get ()) (fun n ->
    bind (put (n + 1)) (fun () ->
    bind (get ()) (fun n ->
    bind (put (n + 1)) (fun () ->
    bind (get ()) (fun n ->
    bind (put (n + 1)) (fun () ->
    bind (get ()) (fun final ->
    Pure final)))))))
  in
  let (result, final_state) = run 0 program in
  Printf.printf "result=%d state=%d\n" result final_state;
  assert (result = 3 && final_state = 3);
  Printf.printf "State free monad works\n"

Deep Comparison

OCaml vs Rust: Free Monad State

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

Add a Modify(f: Box<dyn Fn(i32) -> i32>, continuation: ...) operation that applies a function to the state.

Implement a run_state_with_log(program, state) interpreter that logs each Get and Put operation.

Combine the console DSL (example 185) with state to build a program that counts the number of lines read.

Open Source Repos

functional-rust

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

Rust