The Free Monad:

Programs as Data, Interpreters as Plug-Ins

The Idea: Your Program Is a Shopping List

Imagine writing a shopping list. The list describes what to buy — it doesn't actually buy anything. The same list could be:

• Executed at the supermarket (production)
• Priced up without buying anything (dry-run)
• Checked against the pantry (testing)
• Delegated to someone else (different interpreter)

The Free monad works the same way. Instead of executing side effects directly, you build a program as a data structure. Then you choose an interpreter to run it:

Program (data structure):            Interpreter 1 (real I/O):
  printLine("What is your name?")      → System.out.println(...)
  readLine()                           → scanner.nextLine()
  printLine("Hello, " + name + "!")    → System.out.println(...)

                                     Interpreter 2 (testing):
  (same program, zero changes)         → output.add(...)
                                       → return "Alice" from list
                                       → output.add(...)

                                     Interpreter 3 (logging):
  (same program, zero changes)         → log.info(...)
                                       → return cached input
                                       → log.info(...)

One program. Three interpreters. Zero code changes between them.

The Payoff: See It Before You Build It

Before diving into infrastructure, here is the punchline. Given this program:

Free<ConsoleOpKind.Witness, Unit> program =
    printLine("What is your name?")
        .flatMap(ignored -> readLine()
            .flatMap(name -> printLine("Hello, " + name + "!")));

Run it with a real interpreter — it talks to the console:

ioInterpreter.run(program);
// Console: What is your name?
// User types: Alice
// Console: Hello, Alice!

Run the same program with a test interpreter — no console, pure assertions:

TestInterpreter test = new TestInterpreter(List.of("Alice"));
test.run(program);

assertEquals(List.of("What is your name?", "Hello, Alice!"), test.getOutput());

That is the Free monad's value: write once, interpret many ways.

Core Components

The Free Structure

The HKT Bridge for Free

Type Classes for Free

Free program (tree):                  foldMap walks it:
  FlatMapped                          1. Interpret Suspend → target monad
    ├── Suspend(PrintLine("Hi"))      2. Apply continuation (flatMap fn)
    └── fn: name →                    3. Interpret next Suspend
        Suspend(PrintLine("Hello,     4. Combine via target monad's flatMap
                " + name))           5. Return final result in target monad

Building a DSL: Step by Step

Step 1: Define Your Instruction Set

Create a sealed interface for every operation in your domain:

public sealed interface ConsoleOp<A> {
    record PrintLine(String text) implements ConsoleOp<Unit> {}
    record ReadLine()             implements ConsoleOp<String> {}
}

This is your vocabulary. PrintLine returns Unit (like void). ReadLine returns String.

Step 2: HKT Plumbing

// HKT marker
public interface ConsoleOpKind<A> extends Kind<ConsoleOpKind.Witness, A> {
    final class Witness { private Witness() {} }
}

// Widen/narrow helper
public enum ConsoleOpKindHelper {
    CONSOLE;
    record ConsoleOpHolder<A>(ConsoleOp<A> op) implements ConsoleOpKind<A> {}
    public <A> Kind<ConsoleOpKind.Witness, A> widen(ConsoleOp<A> op) {
        return new ConsoleOpHolder<>(op);
    }
    public <A> ConsoleOp<A> narrow(Kind<ConsoleOpKind.Witness, A> kind) {
        return ((ConsoleOpHolder<A>) kind).op();
    }
}

// Functor instance
public class ConsoleOpFunctor implements Functor<ConsoleOpKind.Witness> {
    @Override
    public <A, B> Kind<ConsoleOpKind.Witness, B> map(
            Function<? super A, ? extends B> f,
            Kind<ConsoleOpKind.Witness, A> fa) {
        return (Kind<ConsoleOpKind.Witness, B>) fa;
    }
}

Step 3: Create DSL Helpers

Wrap liftF calls in friendly methods:

public class ConsoleOps {
    private static final ConsoleOpFunctor FUNCTOR = new ConsoleOpFunctor();

    public static Free<ConsoleOpKind.Witness, Unit> printLine(String text) {
        return Free.liftF(ConsoleOpKindHelper.CONSOLE.widen(
            new ConsoleOp.PrintLine(text)), FUNCTOR);
    }

    public static Free<ConsoleOpKind.Witness, String> readLine() {
        return Free.liftF(ConsoleOpKindHelper.CONSOLE.widen(
            new ConsoleOp.ReadLine()), FUNCTOR);
    }
}

Step 4: Write Programs

Now build programs using familiar flatMap chains:

import static ConsoleOps.*;

Free<ConsoleOpKind.Witness, Unit> greetingProgram =
    printLine("What is your name?")
        .flatMap(ignored -> readLine()
            .flatMap(name -> printLine("Hello, " + name + "!")));

Nothing has executed. You have built a data structure that describes what should happen.

Multiple Interpreters: The Payoff

public class IOInterpreter {
    private static final Scanner scanner = new Scanner(System.in);

    public <A> A run(Free<ConsoleOpKind.Witness, A> program) {
        Function<Kind<ConsoleOpKind.Witness, ?>, Kind<IdKind.Witness, ?>> transform =
            kind -> {
                ConsoleOp<?> op = ConsoleOpKindHelper.CONSOLE.narrow(kind);
                Object result = switch (op) {
                    case ConsoleOp.PrintLine p -> { System.out.println(p.text()); yield Unit.INSTANCE; }
                    case ConsoleOp.ReadLine r  -> scanner.nextLine();
                };
                return Id.of(result);
            };
        return IdKindHelper.ID.narrow(
            program.foldMap(transform, IdMonad.instance())).value();
    }
}

public class TestInterpreter {
    private final List<String> input;
    private final List<String> output = new ArrayList<>();
    private int inputIndex = 0;

    public TestInterpreter(List<String> input) { this.input = input; }

    public <A> A run(Free<ConsoleOpKind.Witness, A> program) {
        Function<Kind<ConsoleOpKind.Witness, ?>, Kind<IdKind.Witness, ?>> transform =
            kind -> {
                ConsoleOp<?> op = ConsoleOpKindHelper.CONSOLE.narrow(kind);
                Object result = switch (op) {
                    case ConsoleOp.PrintLine p -> { output.add(p.text()); yield Unit.INSTANCE; }
                    case ConsoleOp.ReadLine r  -> input.get(inputIndex++);
                };
                return Id.of(result);
            };
        return IdKindHelper.ID.narrow(
            program.foldMap(transform, IdMonad.instance())).value();
    }

    public List<String> getOutput() { return output; }
}

// Pure test — no console, no I/O, no flakiness
@Test void testGreeting() {
    var test = new TestInterpreter(List.of("Alice"));
    test.run(greetingProgram);
    assertEquals(List.of("What is your name?", "Hello, Alice!"), test.getOutput());
}

Composing Programs from Building Blocks

Free programs compose like Lego. Build small pieces, snap them together:

// Reusable building blocks
Free<ConsoleOpKind.Witness, String> askQuestion(String question) {
    return printLine(question).flatMap(ignored -> readLine());
}

Free<ConsoleOpKind.Witness, Unit> confirm(String action) {
    return askQuestion(action + " — sure? (yes/no)")
        .flatMap(answer -> answer.equalsIgnoreCase("yes")
            ? printLine("Confirmed.")
            : printLine("Cancelled."));
}

// Composed program — built from pieces
Free<ConsoleOpKind.Witness, Unit> registration() {
    return askQuestion("Username:")
        .flatMap(user -> askQuestion("Email:")
            .flatMap(email -> confirm("Register " + user + "?")
                .flatMap(ignored -> printLine("Done! Welcome, " + user))));
}

Each building block is independently testable and reusable.

FreeFactory: Fixing Java's Type Inference

Java struggles to infer the functor type F when chaining operations on Free.pure():

// Fails to compile — Java can't infer F
Free<IdKind.Witness, Integer> result = Free.pure(2).map(x -> x * 2); // ERROR

// FreeFactory captures F once, then inference works everywhere
FreeFactory<IdKind.Witness> FREE = FreeFactory.of();

Free<IdKind.Witness, Integer> result = FREE.pure(2).map(x -> x * 2); // Works!

Free<IdKind.Witness, Integer> program = FREE.pure(10)
    .map(x -> x + 1)
    .flatMap(x -> FREE.pure(x * 2))
    .map(x -> x - 5);

When to Use Free Monad

Free Monad vs Traditional Java Patterns

All three patterns solve part of the problem. Free monad unifies them: your entire program is data that can be inspected, composed, transformed, and interpreted in multiple ways.

Advanced Topics

./gradlew :hkj-benchmarks:jmh --includes=".*FreeBenchmark.*"

Previous: Trampoline Next: Free Applicative