Free monad

 _____ ____  _____ _____   __  __  ___  _   _    _    ____  ____
|  ___|  _ \| ____| ____| |  \/  |/ _ \| \ | |  / \  |  _ \/ ___|
| |_  | |_) |  _| |  _|   | |\/| | | | |  \| | / _ \ | | | \___ \
|  _| |  _ <| |___| |___  | |  | | |_| | |\  |/ ___ \| |_| |___) |
|_|   |_| \_\_____|_____| |_|  |_|\___/|_| \_/_/   \_\____/|____/

After wrestling with comonads and their spatial wizardry — where every computation was imprisoned by its neighborhood context — we now face the ultimate plot twist: Freedom.

In programming, as in life, the word "free" comes with strings attached:

1. Free as in "Free Beer" 🍺: You get monad structure without choosing how to interpret each operation upfront
2. Free as in "Freedom" 🕊️: You can choose your interpretation later, like a philosophical choose-your-own-adventure book
3. Free as in "Free Range" 🐔: Your computations roam the semantic landscape until you decide to pin them down

A monad can also be free. But what does it mean to build one without choosing its effects? Think of it as computational procrastination elevated to an art form. Instead of immediately executing effects, we can defer the decision of how to execute them until we absolutely have to.

A Free Monad is a data structure that looks like a monadic computation but doesn't perform its described effects until you provide an interpreter. It's the programming equivalent of writing a recipe without cooking the meal.

Free Monads solve a fundamental existential crisis in functional programming:

"How can I build complex programs without committing to specific effects until interpretation?"

This creates a separation of concerns:

• What your program does (the structure)
• How your program does it (the interpretation)

It's the difference between choreographing a dance and actually dancing it. Free Monads let you perfect the choreography without worrying about whether you'll perform it in a ballroom, a barn, or a zero-gravity chamber.

Great power comes with great... well, you know the rest. Free Monads unlock several opportunities:

1. 🧪 Testing: Supply test interpretations for the effects your DSL describes without changing your core logic
2. 🔄 Optimization: Transform computations before executing them
3. 🎭 Multiple Interpretations: Run the same program in different contexts
4. 🧩 Modularity: Build programs like LEGO blocks of pure intent

Time to make our programs a lot more philosophical and slightly more confusing, but infinitely more powerful.

Free Monads #

In a nutshell, instead of defining what a monad does, we define what a monad looks like as pure data. We create a structure that captures the shape of monadic computation without committing to any particular interpretation.

Formal Definition #

A Free Monad over a functor f is defined as:

data Free f a
  = Pure a                    -- Pure value (return)
  | Free (f (Free f a))       -- Suspended computation

This recursive definition captures the essence of monadic structure:

• Pure a represents a pure value wrapped in the monad (equivalent to return or pure)
• Free (f (Free f a)) represents a suspended computation that can be further composed

The functor f represents your "instruction set" - the basic operations your program can perform. The Free Monad organizes these instructions into a program without executing them.

The Monad Instance #

Free Monads automatically satisfy the monad laws:

instance Functor f => Functor (Free f) where
  fmap g (Pure a) = Pure (g a)
  fmap g (Free layer) = Free (fmap (fmap g) layer)

instance Functor f => Applicative (Free f) where
  pure = Pure
  Pure g <*> x = fmap g x
  Free layer <*> x = Free (fmap (<*> x) layer)

instance Functor f => Monad (Free f) where
  Pure a >>= k = k a
  Free layer >>= k = Free (fmap (>>= k) layer)

Notice how >>= (bind) doesn't actually execute anything - it just builds up more structure. The real magic happens when you provide an interpreter.

Categorical Perspective #

The adjunction example built a free monoid from a set of generators. A function assigning meaning to each generator extended uniquely to a monoid homomorphism on lists. Here the generators are operations described by a functor f, and the free construction gives them monadic sequencing.

The free-monad construction is left adjoint to the forgetful functor U, which maps a monad to its underlying functor.

Here is what that means for interpretation. For any monad m, a natural transformation α : f → U(m) assigns a meaning in m to each operation. The adjunction extends α uniquely to a monad homomorphism φ : Free f → m, which interprets the whole program. Its universal property is captured by this commuting diagram:

    f -------- α --------> U(m)
     \                    ↑
    η \                   │ U(φ)
       ↓                  │
      U(Free f) ──────────┘

The unit η : f → U(Free f) lifts one operation into a program. The counit Free (U(m)) → m interprets a program whose operations already belong to m. The diagram says α = U(φ) ∘ η: interpreting a lifted operation agrees with interpreting that operation directly. Choosing a different α gives the same program a different interpreter, as the example below shows.

Example: Console DSL #

We will describe console operations once, build programs from them, and then interpret the same programs in several ways.

Step 1: Define Your Operations (Functor) #

First, we define the basic operations our DSL supports:

{-# LANGUAGE DeriveFunctor #-}

-- Our basic console operations
data ConsoleF next
  = WriteLine String next           -- Write a line to console
  | ReadLine (String -> next)       -- Read a line from console
  deriving (Functor)

-- Type alias for our Free Monad
type Console = Free ConsoleF

The ConsoleF functor defines our "instruction set":

• WriteLine: Output a string and continue
• ReadLine: Input a string and use it in the continuation

Step 2: Smart Constructors #

Create convenient functions to build Free Monad programs:

-- Smart constructors for our DSL
writeLine :: String -> Console ()
writeLine s = liftF (WriteLine s ())

readLine :: Console String
readLine = liftF (ReadLine id)

-- Helper function to lift functors into Free Monads
liftF :: Functor f => f a -> Free f a
liftF fa = Free (fmap Pure fa)

Step 3: Write Programs Using the DSL #

Now we can write programs that look monadic but don't commit to any interpretation:

-- A simple greeting program
greetingProgram :: Console ()
greetingProgram = do
  writeLine "Hello! What's your name?"
  name <- readLine
  writeLine ("Nice to meet you, " ++ name ++ "!")
  writeLine "What's your favorite color?"
  color <- readLine
  writeLine (name ++ " likes " ++ color ++ ". Great choice!")

-- A more complex program with logic
surveyProgram :: Console ()
surveyProgram = do
  writeLine "Welcome to our survey!"
  writeLine "Are you over 18? (yes/no)"
  age <- readLine
  if age == "yes"
    then do
      writeLine "What's your occupation?"
      job <- readLine
      writeLine ("Thank you! We have: occupation = " ++ job)
    else writeLine "Thanks for your interest, but this survey is for adults only."

Step 4: Multiple Interpreters #

Here's where Free Monads shine - we can interpret the same program in different ways:

• Real Console Interpreter

  -- Interpret to actual IO operations
  runConsoleIO :: Console a -> IO a
  runConsoleIO (Pure a) = return a
  runConsoleIO (Free (WriteLine s next)) = do
    putStrLn s
    runConsoleIO next
  runConsoleIO (Free (ReadLine f)) = do
    input <- getLine
    runConsoleIO (f input)
  

• Test Interpreter (Pure)

  -- Interpret with predefined inputs for testing
  runConsoleTest :: [String] -> Console a -> (a, [String], [String])
  runConsoleTest inputs program =
    let ((result, outputs), remainingInputs) =
          runState (runWriterT (interpret program)) inputs
    in (result, outputs, remainingInputs)
    where
      interpret :: Console a -> WriterT [String] (State [String]) a
      interpret (Pure a) = return a
      interpret (Free (WriteLine s next)) = do
        tell [s]  -- Record output
        interpret next
      interpret (Free (ReadLine f)) = do
        remaining <- get
        case remaining of
          [] -> error "No more test inputs!"
          (x:xs) -> do
            put xs  -- Consume input
            interpret (f x)
  

• Mock Trace - Unit Tests

  -- Simple mock that just collects operations
  data MockResult = MockResult
    { mockOutputs :: [String]
    , mockInputsUsed :: [String]
    } deriving (Show, Eq)
  
  runConsoleMock :: [String] -> Console a -> MockResult
  runConsoleMock inputs prog = MockResult outputs usedInputs
    where
      (outputs, usedInputs) = runMock inputs prog
  
      runMock :: [String] -> Console a -> ([String], [String])
      runMock _ (Pure _) = ([], [])
      runMock remaining (Free (WriteLine s next)) =
        let (nextOutputs, used) = runMock remaining next
        in (s : nextOutputs, used)
      runMock [] (Free (ReadLine _)) = error "No mock input available!"
      runMock (i:is) (Free (ReadLine f)) =
        let (nextOutputs, used) = runMock is (f i)
        in (nextOutputs, i : used)
  

  This trace collector records the operations and inputs but discards the program's result. Unlike the IO and test interpreters, it is not a monad homomorphism Free ConsoleF → m.

Step 5: Running Your Programs #

main :: IO ()
main = do
  putStrLn "=== Running with real IO ==="
  runConsoleIO greetingProgram

  putStrLn "\n=== Running with test data ==="
  let testInputs = ["Alice", "blue"]
  let (_, outputs, _) = runConsoleTest testInputs greetingProgram
  putStrLn "Outputs:"
  mapM_ putStrLn outputs

  putStrLn "\n=== Running survey with test data ==="
  let (_, surveyOutputs, _) = runConsoleTest ["yes", "Engineer"] surveyProgram
  mapM_ putStrLn surveyOutputs

  putStrLn "\n=== Running with mock ==="
  let mockInputs = ["Bob", "red"]
  let mockResult = runConsoleMock mockInputs greetingProgram
  print mockResult

1. Same Logic, Different Contexts: greetingProgram works in production (IO), testing (pure), and mocking
2. Testability: You can unit test your business logic without actual I/O
3. Flexibility: Add new interpreters (logging, debugging, optimization) without changing programs
4. Composability: Programs compose naturally using monadic operations

Core power of Free Monads: separation of description from interpretation. Your programs describe what to do; interpreters decide how to do it.

// Free Monad implementation using interfaces
interface Free<F, A> {
  readonly tag: 'Pure' | 'FreeBind';
  fold<B>(
    pure: (a: A) => B,
    free: (fa: F) => B
  ): B;
}

interface Pure<F, A> extends Free<F, A> {
  readonly tag: 'Pure';
  readonly value: A;
}

interface FreeBind<F, A> extends Free<F, A> {
  readonly tag: 'FreeBind';
  readonly fa: F;
}

// Constructors for Free Monad
function makePure<F, A>(value: A): Pure<F, A> {
  return {
    tag: 'Pure',
    value,
    fold<B>(pure: (a: A) => B, free: (fa: F) => B): B {
      return pure(this.value);
    }
  };
}

function makeFreeBind<F, A>(fa: F): FreeBind<F, A> {
  return {
    tag: 'FreeBind',
    fa,
    fold<B>(pure: (a: A) => B, free: (fa: F) => B): B {
      return free(this.fa);
    }
  };
}

// Console operations using interfaces
interface ConsoleF<A> {
  readonly tag: 'WriteLine' | 'ReadLine';
  map<B>(f: (a: A) => B): ConsoleF<B>;
}

interface WriteLine<A> extends ConsoleF<A> {
  readonly tag: 'WriteLine';
  readonly message: string;
  readonly next: A;
}

interface ReadLine<A> extends ConsoleF<A> {
  readonly tag: 'ReadLine';
  readonly continuation: (input: string) => A;
}

// Constructors for console operations
function makeWriteLine<A>(message: string, next: A): WriteLine<A> {
  return {
    tag: 'WriteLine',
    message,
    next,
    map<B>(f: (a: A) => B): WriteLine<B> {
      return makeWriteLine(this.message, f(this.next));
    }
  };
}

function makeReadLine<A>(continuation: (input: string) => A): ReadLine<A> {
  return {
    tag: 'ReadLine',
    continuation,
    map<B>(f: (a: A) => B): ReadLine<B> {
      return makeReadLine((input) => f(this.continuation(input)));
    }
  };
}

// Type alias for our console Free Monad
type ConsoleProgram<A> = Free<ConsoleF<ConsoleProgram<A>>, A>;

// Smart constructors
function writeLine(message: string): ConsoleProgram<void> {
  return makeFreeBind(makeWriteLine(message, makePure(undefined)));
}

function readLine(): ConsoleProgram<string> {
  return makeFreeBind(makeReadLine((input) => makePure(input)));
}

function pure<A>(value: A): ConsoleProgram<A> {
  return makePure(value);
}

// Monadic bind operation
function bind<A, B>(ma: ConsoleProgram<A>, f: (a: A) => ConsoleProgram<B>): ConsoleProgram<B> {
  return ma.fold(
    (a) => f(a),
    (fa) => makeFreeBind(fa.map((nextProg: ConsoleProgram<A>) => bind(nextProg, f)))
  );
}

// Example programs
function greetingProgram(): ConsoleProgram<void> {
  return bind(writeLine("Hello! What's your name?"), () =>
    bind(readLine(), (name) =>
      bind(writeLine(`Nice to meet you, ${name}!`), () =>
        bind(writeLine("What's your favorite color?"), () =>
          bind(readLine(), (color) =>
            writeLine(`${name} likes ${color}. Great choice!`)
          )
        )
      )
    )
  );
}

function surveyProgram(): ConsoleProgram<void> {
  return bind(writeLine("Welcome to our survey!"), () =>
    bind(writeLine("Are you over 18? (yes/no)"), () =>
      bind(readLine(), (age) =>
        age === "yes"
          ? bind(writeLine("What's your occupation?"), () =>
              bind(readLine(), (job) =>
                writeLine(`Thank you! We have: occupation = ${job}`)
              )
            )
          : writeLine("Thanks for your interest, but this survey is for adults only.")
      )
    )
  );
}

// Real console interpreter (Node.js)
async function runConsoleIO<A>(program: ConsoleProgram<A>): Promise<A> {
  const readline = require('readline');
  const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
  });

  function interpret<T>(prog: ConsoleProgram<T>): Promise<T> {
    return prog.fold(
      async (value) => value,
      async (fa) => {
        if (fa.tag === 'WriteLine') {
          const writeOp = fa as WriteLine<ConsoleProgram<T>>;
          console.log(writeOp.message);
          return interpret(writeOp.next);
        } else if (fa.tag === 'ReadLine') {
          const readOp = fa as ReadLine<ConsoleProgram<T>>;
          return new Promise((resolve) => {
            rl.question('> ', (input: string) => {
              resolve(interpret(readOp.continuation(input)));
            });
          });
        }
        throw new Error('Unknown operation');
      }
    );
  }

  const result = await interpret(program);
  rl.close();
  return result;
}

// Test interpreter (pure)
interface TestResult<A> {
  result: A;
  outputs: string[];
  inputsUsed: string[];
}

function runConsoleTest<A>(
  inputs: string[],
  program: ConsoleProgram<A>
): TestResult<A> {
  let inputIndex = 0;
  const outputs: string[] = [];
  const inputsUsed: string[] = [];

  function interpret<T>(prog: ConsoleProgram<T>): T {
    return prog.fold(
      (value) => value,
      (fa) => {
        if (fa.tag === 'WriteLine') {
          const writeOp = fa as WriteLine<ConsoleProgram<T>>;
          outputs.push(writeOp.message);
          return interpret(writeOp.next);
        } else if (fa.tag === 'ReadLine') {
          const readOp = fa as ReadLine<ConsoleProgram<T>>;
          if (inputIndex >= inputs.length) {
            throw new Error('No more test inputs available!');
          }
          const input = inputs[inputIndex++];
          inputsUsed.push(input);
          return interpret(readOp.continuation(input));
        }
        throw new Error('Unknown operation');
      }
    );
  }

  const result = interpret(program);
  return { result, outputs, inputsUsed };
}

// Mock interpreter
interface MockResult {
  outputs: string[];
  inputsUsed: string[];
}

function runConsoleMock<A>(
  inputs: string[],
  program: ConsoleProgram<A>
): MockResult {
  let inputIndex = 0;
  const outputs: string[] = [];
  const inputsUsed: string[] = [];

  function interpret<T>(prog: ConsoleProgram<T>): void {
    prog.fold(
      () => undefined,
      (fa) => {
        if (fa.tag === 'WriteLine') {
          const writeOp = fa as WriteLine<ConsoleProgram<T>>;
          outputs.push(writeOp.message);
          interpret(writeOp.next);
        } else if (fa.tag === 'ReadLine') {
          const readOp = fa as ReadLine<ConsoleProgram<T>>;
          if (inputIndex >= inputs.length) {
            throw new Error('No mock input available!');
          }
          const input = inputs[inputIndex++];
          inputsUsed.push(input);
          interpret(readOp.continuation(input));
        }
      }
    );
  }

  interpret(program);
  return { outputs, inputsUsed };
}

// Usage example
async function main() {
  console.log("=== Running with real IO ===");
  await runConsoleIO(greetingProgram());

  console.log("\n=== Running with test data ===");
  const testInputs = ["Alice", "blue"];
  const testResult = runConsoleTest(testInputs, greetingProgram());
  console.log("Outputs:", testResult.outputs);
  console.log("Inputs used:", testResult.inputsUsed);

  console.log("\n=== Running with mock ===");
  const mockInputs = ["Bob", "red"];
  const mockResult = runConsoleMock(mockInputs, greetingProgram());
  console.log("Mock result:", mockResult);
}

main().catch(console.error);

using System;
using System.Collections.Generic;
using System.Threading.Tasks;

// Free Monad implementation using interfaces
public interface IFree<F, A>
{
    string Tag { get; }
    B Fold<B>(Func<A, B> pure, Func<F, B> free);
}

public interface IPure<F, A> : IFree<F, A>
{
    A Value { get; }
}

public interface IFreeBind<F, A> : IFree<F, A>
{
    F Fa { get; }
}

// Concrete implementations
public class Pure<F, A> : IPure<F, A>
{
    public string Tag => "Pure";
    public A Value { get; }

    public Pure(A value)
    {
        Value = value;
    }

    public B Fold<B>(Func<A, B> pure, Func<F, B> free)
    {
        return pure(Value);
    }
}

public class FreeBind<F, A> : IFreeBind<F, A>
{
    public string Tag => "FreeBind";
    public F Fa { get; }

    public FreeBind(F fa)
    {
        Fa = fa;
    }

    public B Fold<B>(Func<A, B> pure, Func<F, B> free)
    {
        return free(Fa);
    }
}

// Console operations using interfaces
public interface IConsoleF<A>
{
    string Tag { get; }
    IConsoleF<B> Map<B>(Func<A, B> f);
}

public interface IWriteLine<A> : IConsoleF<A>
{
    string Message { get; }
    A Next { get; }
}

public interface IReadLine<A> : IConsoleF<A>
{
    Func<string, A> Continuation { get; }
}

// Concrete console operations
public class WriteLine<A> : IWriteLine<A>
{
    public string Tag => "WriteLine";
    public string Message { get; }
    public A Next { get; }

    public WriteLine(string message, A next)
    {
        Message = message;
        Next = next;
    }

    public IConsoleF<B> Map<B>(Func<A, B> f)
    {
        return new WriteLine<B>(Message, f(Next));
    }
}

public class ReadLine<A> : IReadLine<A>
{
    public string Tag => "ReadLine";
    public Func<string, A> Continuation { get; }

    public ReadLine(Func<string, A> continuation)
    {
        Continuation = continuation;
    }

    public IConsoleF<B> Map<B>(Func<A, B> f)
    {
        return new ReadLine<B>(input => f(Continuation(input)));
    }
}

// Wrapper for our console Free Monad
public class ConsoleProgram<A> : IFree<IConsoleF<ConsoleProgram<A>>, A>
{
    private readonly IFree<IConsoleF<ConsoleProgram<A>>, A> _inner;

    public ConsoleProgram(IFree<IConsoleF<ConsoleProgram<A>>, A> inner)
    {
        _inner = inner;
    }

    public string Tag => _inner.Tag;

    public B Fold<B>(Func<A, B> pure, Func<IConsoleF<ConsoleProgram<A>>, B> free)
    {
        return _inner.Fold(pure, free);
    }
}

// Smart constructors
public static class Console
{
    public static ConsoleProgram<Unit> WriteLine(string message)
    {
        var writeOp = new WriteLine<ConsoleProgram<Unit>>(message, Pure(Unit.Instance));
        return new ConsoleProgram<Unit>(new FreeBind<IConsoleF<ConsoleProgram<Unit>>, Unit>(writeOp));
    }

    public static ConsoleProgram<string> ReadLine()
    {
        var readOp = new ReadLine<ConsoleProgram<string>>(input => Pure(input));
        return new ConsoleProgram<string>(new FreeBind<IConsoleF<ConsoleProgram<string>>, string>(readOp));
    }

    public static ConsoleProgram<A> Pure<A>(A value)
    {
        return new ConsoleProgram<A>(new Pure<IConsoleF<ConsoleProgram<A>>, A>(value));
    }

    // Monadic bind operation
    public static ConsoleProgram<B> Bind<A, B>(
        ConsoleProgram<A> ma,
        Func<A, ConsoleProgram<B>> f)
    {
        return new ConsoleProgram<B>(ma.Fold<IFree<IConsoleF<ConsoleProgram<B>>, B>>(
            a => f(a),
            fa => new FreeBind<IConsoleF<ConsoleProgram<B>>, B>(
                fa.Map<ConsoleProgram<B>>(nextProg => Bind(nextProg, f))
            )
        ));
    }
}

// Unit type for void operations
public class Unit
{
    public static readonly Unit Instance = new Unit();
    private Unit() { }
}

// Example programs
public static class Programs
{
    public static ConsoleProgram<Unit> GreetingProgram()
    {
        return Console.Bind(Console.WriteLine("Hello! What's your name?"), _ =>
            Console.Bind(Console.ReadLine(), name =>
                Console.Bind(Console.WriteLine($"Nice to meet you, {name}!"), _ =>
                    Console.Bind(Console.WriteLine("What's your favorite color?"), _ =>
                        Console.Bind(Console.ReadLine(), color =>
                            Console.WriteLine($"{name} likes {color}. Great choice!")
                        )
                    )
                )
            )
        );
    }

    public static ConsoleProgram<Unit> SurveyProgram()
    {
        return Console.Bind(Console.WriteLine("Welcome to our survey!"), _ =>
            Console.Bind(Console.WriteLine("Are you over 18? (yes/no)"), _ =>
                Console.Bind(Console.ReadLine(), age =>
                    age == "yes"
                        ? Console.Bind(Console.WriteLine("What's your occupation?"), _ =>
                            Console.Bind(Console.ReadLine(), job =>
                                Console.WriteLine($"Thank you! We have: occupation = {job}")
                            )
                        )
                        : Console.WriteLine("Thanks for your interest, but this survey is for adults only.")
                )
            )
        );
    }
}

// Real console interpreter
public static class ConsoleInterpreter
{
    public static async Task<A> RunConsoleIO<A>(ConsoleProgram<A> program)
    {
        return await Interpret(program);

        async Task<T> Interpret<T>(ConsoleProgram<T> prog)
        {
            return await prog.Fold<Task<T>>(
                value => Task.FromResult(value),
                async fa =>
                {
                    switch (fa.Tag)
                    {
                        case "WriteLine":
                            var writeOp = fa as IWriteLine<ConsoleProgram<T>>;
                            if (writeOp != null)
                            {
                                System.Console.WriteLine(writeOp.Message);
                                return await Interpret(writeOp.Next);
                            }
                            throw new InvalidOperationException("Invalid WriteLine operation");

                        case "ReadLine":
                            var readOp = fa as IReadLine<ConsoleProgram<T>>;
                            if (readOp != null)
                            {
                                var input = System.Console.ReadLine() ?? string.Empty;
                                return await Interpret(readOp.Continuation(input));
                            }
                            throw new InvalidOperationException("Invalid ReadLine operation");

                        default:
                            throw new InvalidOperationException("Unknown operation");
                    }
                }
            );
        }
    }
}

// Test interpreter (pure)
public class TestResult<A>
{
    public A? Result { get; set; }
    public List<string> Outputs { get; set; } = new List<string>();
    public List<string> InputsUsed { get; set; } = new List<string>();
}

public static class TestInterpreter
{
    public static TestResult<A> RunConsoleTest<A>(
        List<string> inputs,
        ConsoleProgram<A> program)
    {
        var inputIndex = 0;
        var outputs = new List<string>();
        var inputsUsed = new List<string>();

        T Interpret<T>(ConsoleProgram<T> prog)
        {
            return prog.Fold(
                value => value,
                fa =>
                {
                    switch (fa.Tag)
                    {
                        case "WriteLine":
                            var writeOp = fa as IWriteLine<ConsoleProgram<T>>;
                            if (writeOp != null)
                            {
                                outputs.Add(writeOp.Message);
                                return Interpret(writeOp.Next);
                            }
                            throw new InvalidOperationException("Invalid WriteLine operation");

                        case "ReadLine":
                            var readOp = fa as IReadLine<ConsoleProgram<T>>;
                            if (readOp != null)
                            {
                                if (inputIndex >= inputs.Count)
                                    throw new InvalidOperationException("No more test inputs available!");

                                var input = inputs[inputIndex++];
                                inputsUsed.Add(input);
                                return Interpret(readOp.Continuation(input));
                            }
                            throw new InvalidOperationException("Invalid ReadLine operation");

                        default:
                            throw new InvalidOperationException("Unknown operation");
                    }
                }
            );
        }

        var result = Interpret(program);
        return new TestResult<A>
        {
            Result = result,
            Outputs = outputs,
            InputsUsed = inputsUsed
        };
    }
}

// Mock interpreter
public class MockResult
{
    public List<string> Outputs { get; set; } = new List<string>();
    public List<string> InputsUsed { get; set; } = new List<string>();
}

public static class MockInterpreter
{
    public static MockResult RunConsoleMock<A>(
        List<string> inputs,
        ConsoleProgram<A> program)
    {
        var inputIndex = 0;
        var outputs = new List<string>();
        var inputsUsed = new List<string>();

        void Interpret<T>(ConsoleProgram<T> prog)
        {
            prog.Fold<Unit>(
                _ => Unit.Instance,
                fa =>
                {
                    switch (fa.Tag)
                    {
                        case "WriteLine":
                            var writeOp = fa as IWriteLine<ConsoleProgram<T>>;
                            if (writeOp != null)
                            {
                                outputs.Add(writeOp.Message);
                                Interpret(writeOp.Next);
                            }
                            break;

                        case "ReadLine":
                            var readOp = fa as IReadLine<ConsoleProgram<T>>;
                            if (readOp != null)
                            {
                                if (inputIndex >= inputs.Count)
                                    throw new InvalidOperationException("No mock input available!");

                                var input = inputs[inputIndex++];
                                inputsUsed.Add(input);
                                Interpret(readOp.Continuation(input));
                            }
                            break;

                        default:
                            throw new InvalidOperationException("Unknown operation");
                    }
                    return Unit.Instance;
                }
            );
        }

        Interpret(program);
        return new MockResult
        {
            Outputs = outputs,
            InputsUsed = inputsUsed
        };
    }
}

// Usage example
public class Program
{
    public static async Task Main(string[] args)
    {
        System.Console.WriteLine("=== Running with real IO ===");
        await ConsoleInterpreter.RunConsoleIO(Programs.GreetingProgram());

        System.Console.WriteLine("\n=== Running with test data ===");
        var testInputs = new List<string> { "Alice", "blue" };
        var testResult = TestInterpreter.RunConsoleTest(testInputs, Programs.GreetingProgram());
        System.Console.WriteLine("Outputs:");
        testResult.Outputs.ForEach(System.Console.WriteLine);
        System.Console.WriteLine("Inputs used:");
        testResult.InputsUsed.ForEach(System.Console.WriteLine);

        System.Console.WriteLine("\n=== Running with mock ===");
        var mockInputs = new List<string> { "Bob", "red" };
        var mockResult = MockInterpreter.RunConsoleMock(mockInputs, Programs.GreetingProgram());
        System.Console.WriteLine($"Mock outputs: [{string.Join(", ", mockResult.Outputs)}]");
        System.Console.WriteLine($"Mock inputs used: [{string.Join(", ", mockResult.InputsUsed)}]");
    }
}

Free Monad Visualization #

Visually, Free Monads represent a separation between structure and interpretation. Every Free Monad computation can be seen as building a syntax tree that gets interpreted later.

FREE MONAD STRUCTURE           INTERPRETER EXECUTION
────────────────────           ─────────────────────

Program Description            Program Execution
┌─────────────────┐            ┌─────────────────┐
│                 │            │                 │
│   Free f a      │ ---------> |     m a         │
│  (Syntax Tree)  │ interpret  │  (Real Effect)  │
│                 │            │                 │
└─────────────────┘            └─────────────────┘
  Pure structure                Effectful computation

Data Structure Tree            Evaluation Strategy
┌─────────────────┐            ┌─────────────────┐
│      Pure a     │ -- fold -->│     return a    │
└─────────────────┘            └─────────────────┘

┌─────────────────┐            ┌─────────────────┐
│  Free(f(...))   │ -- fold -->│   interpret f   │
└─────────────────┘            └─────────────────┘

1. Free Monad Construction vs Interpretation

CONSTRUCTION PHASE                INTERPRETATION PHASE
──────────────────                ────────────────────

Build Abstract Syntax            Execute with Strategy

    Operations                        Interpreters
  ┌─────────────┐                 ┌─────────────────┐
  │ WriteLine   │                 │    putStrLn     │
  │ ReadLine    │    --------->   │    getLine      │
  └─────────────┘                 └─────────────────┘
   Pure DSL                        Concrete Effects

  Free Monad Tree                  Execution Tree
┌─────────────────┐               ┌─────────────────┐
│ Free WriteLine  │               │   putStrLn      │
│        │        │               │        │        │
│ Free ReadLine   │ ------------> │    getLine      │
│        │        │               │        │        │
│      Pure b     │               │    return b     │
└─────────────────┘               └─────────────────┘
   Description                     Interpreted


2. Multiple Interpretation Strategies

SINGLE FREE MONAD                 MULTIPLE INTERPRETERS
─────────────────                 ─────────────────────

  One Program                     Many Strategies
┌─────────────────┐
│                 │               ┌─── Real IO ────────┐
│  ConsoleProgram │               │   putStrLn         │
│      Free       │ ------------> │   getLine          │
│   ConsoleF a    │               └────────────────────┘
│                 │
└─────────────────┘               ┌─── Test Mock ──────┐
        │                         │  ["output1"]       │
        │                         │  ["input1","in2"]  │
        │                         └────────────────────┘
        │
        │                         ┌─── Logging ────────┐
        │                         │  log operations    │
        └─────────────────────────│  trace execution   │
                                  └────────────────────┘

Same Structure, Different Meanings

3. Free Monad Bind Operation

MONADIC BIND IN FREE MONADS
───────────────────────────

Free f a >>= k  where k : a → Free f b

Case 1: Pure Value
┌─────────────┐            ┌─────────────┐
│   Pure a    │ >>= k ---> │     k a     │
└─────────────┘            └─────────────┘
Direct application

Case 2: Suspended Computation
┌─────────────────────┐            ┌──────────────────────┐
│ Free (f (Free f a)) │ >>= k ---> │ Free (fmap(>>= k)f)  │
└─────────────────────┘            └──────────────────────┘

Recursive bind propagation

Visual Flow:
     Free f a
        │
    >>= │ k : a → Free f b
        │
        ▼
  ┌─────────────┐
  │ Is it Pure? │----------
  └─────┬───────┘          │
        │                  │
    ┌───▼───┐         ┌────▼────┐
   ┌┴──Yes──┴┐       ┌┴───No────┴┐
   │ Pure a  │       │ Free f... │
   └─────────┘       └───────────┘
        │                  │
        ▼                  ▼
   ┌─────────┐    ┌─────────────────────┐
   │  k a    │    │ Free (fmap(>>= k)f) |
   └─────────┘    └─────────────────────┘

Conclusion #

Free Monads represent a solution to a fundamental problem: how to build complex, effectful programs while maintaining the ability to reason about them, test them, and interpret them in multiple ways.

Where Comonads imprisoned computations within their spatial context, Free Monads offer the opposite extreme: complete liberation from interpretation until the last possible moment. This philosophical shift from "immediate execution" to "deferred description" unlocks unprecedented flexibility in program design.

A Free Monad is just data that looks like a computation

This simple insight has profound implications:

1. Separation of Concerns: What your program does vs. how it does it
2. Multiple Interpretations: Test, production, optimization, debugging - all from one description
3. Compositional Safety: Build complex operations from simple, reliable building blocks
4. Pure Reasoning: Think about effects without being entangled by them

Free Monads aren't without cost:

• Performance: Building syntax trees has overhead compared to direct execution. For performance-critical code, this indirection may be prohibitive.

• Complexity: Free Monads introduce concepts that can overwhelm developers unfamiliar with categorical thinking.

• Memory: Large Free Monad computations create substantial data structures before interpretation.

• Learning Curve: The abstraction requires understanding functors, monads, and categorical relationships.

Free Monads shine when you need:

• Multiple execution strategies for the same logic
• Comprehensive testing of effectful code
• Domain-specific languages with clean separation of syntax and semantics
• Modularity where effect interpretation can be swapped out

Source code #

Reference implementation (opens in a new tab)

References

1. Free structure (opens in a new tab)
2. Free Monad (opens in a new tab)

Continue exploring

• Monad (Part I) Sequencing computations in a context Shared tags: functional-programming, category-theory · Same collection
• Monad (Part II) Practical monad implementations and examples Shared tags: functional-programming, category-theory · Same collection
• MonadPlus Choice and failure for monadic computations Shared tags: functional-programming, category-theory · Same collection