Hone logo
Hone
Problems

Implementing Free Monad in TypeScript

This challenge focuses on building a foundational abstraction in functional programming: the Free Monad. Free monads allow you to represent computations as data structures, enabling you to interpret those computations in various ways without altering the original definition. This is crucial for building domain-specific languages (DSLs), effect systems, and separating computation definition from its execution.

Problem Description

Your task is to implement a generic FreeMonad type and its associated interpreter in TypeScript. This implementation should allow you to define effectful computations as a series of instructions and then provide a mechanism to execute these instructions.

Key Requirements:

  1. FreeMonad<T, F> Type:

    • This type will represent a free monad.
    • T will be the type of the final result of the computation.
    • F will be a type that represents the "effect" or instruction type. This F will be a functor.

  2. Constructors for FreeMonad:

    • Pure<T>(value: T): Represents a pure value, the end of a computation.
    • FlatMap<T, F>(value: FreeMonad<any, F>, fn: (val: any) => FreeMonad<T, F>): Represents a monadic bind operation. It takes a previous computation (value) and a function (fn) to produce the next step.

  3. Interpreter Function:

    • interpret<T, F>(freeMonad: FreeMonad<T, F>, handler: (effect: F<any>) => any): T: This function takes a FreeMonad computation and a handler function. The handler should know how to process each effect (F<any>) in the computation. The interpreter should recursively evaluate the FreeMonad until it reaches a Pure value, applying the handler to any encountered effects.

  4. Functor Constraint: The F type parameter must be a functor. You don't need to explicitly enforce this at compile time with TypeScript's type system in this challenge, but your implementation should assume F has a map method.

Expected Behavior:

  • Pure values should be returned directly.
  • FlatMap operations should be decomposed. The value part should be recursively interpreted. If the value resolves to a pure value, the fn should be applied to that value to produce the next FreeMonad. If the value is an effect, the interpreter should delegate to the handler.

Important Edge Cases:

  • Deeply nested FlatMap structures.
  • Computations that end with a Pure value immediately.
  • Computations that involve effects.

Examples

Example 1: Simple Pure Computation

// Assume FreeMonad and interpreter are defined

// Representing a simple value
const pureComputation = FreeMonad.Pure(10);

// A handler that does nothing for this pure case (or could throw if it encountered an effect)
const noOpHandler = <A>(effect: any): A => {
  throw new Error("Unexpected effect in pure computation");
};

const result = interpret(pureComputation, noOpHandler);

console.log(result); // Expected output: 10

Example 2: Computation with a Single Effect

Let's define a simple effect type for logging.

// A simple Functor for logging
interface Log {
  message: string;
}

// A dummy functor type for Log
type LogF<A> = { tag: 'Log', value: Log, chain: (a: A) => void }; // Simplified for demonstration

// Helper to create a functor instance
function createLogEffect<T>(message: string): LogF<T> {
    return {
        tag: 'Log',
        value: { message },
        chain: (a: T) => { /* in a real scenario, this would actually do something */ }
    };
}

// A FreeMonad that logs a message and then returns a value
const loggingComputation = FreeMonad.FlatMap(
    FreeMonad.Pure(undefined as void), // Start with a pure step to create the effect
    () => FreeMonad.Pure({ type: 'Log', payload: { message: "User logged in" } }) as any // This is a simplified representation of an effect
);

// A handler that processes Log effects
const logHandler = <A>(effect: { type: string, payload: any }): A => {
  if (effect.type === 'Log') {
    console.log(`[LOG]: ${effect.payload.message}`);
    // For this example, we'll just return undefined, assuming the log itself is the action
    return undefined as any;
  }
  throw new Error(`Unknown effect: ${effect.type}`);
};

// This example requires a bit of interpretation of how effects are represented.
// Let's refine the FreeMonad structure to better handle effect representation.

// REVISED approach for Example 2, reflecting a more typical Free Monad structure

// Define the instruction set (effects)
interface ConsoleLogInstruction {
  type: 'ConsoleLog';
  message: string;
}

interface AddInstruction {
  type: 'Add';
  a: number;
  b: number;
}

// A union type for all possible instructions
type Instruction = ConsoleLogInstruction | AddInstruction;

// A simple Functor for Instruction
// We'll use a discriminated union to represent the functor.
type InstructionF<A> =
  | { tag: 'ConsoleLog', value: ConsoleLogInstruction, map: <B>(f: (a: A) => B) => InstructionF<B> }
  | { tag: 'Add', value: AddInstruction, map: <B>(f: (a: A) => B) => InstructionF<B> };

// Helper to create a functor instance for ConsoleLog
function consoleLog(message: string): InstructionF<void> {
  const instruction: ConsoleLogInstruction = { type: 'ConsoleLog', message };
  return {
    tag: 'ConsoleLog',
    value: instruction,
    map: <B>(f: (a: void) => B) => {
      // When mapping over a functor containing an instruction,
      // we create a new functor that applies 'f' *after* the instruction is processed.
      // For this specific challenge, the interpreter handles this.
      // The map here is more for demonstrating functor properties, not directly used by *this* interpreter.
      return consoleLog(message) as any; // Placeholder for simplicity, actual map logic depends on how you want to chain operations *within* the functor.
    }
  };
}

// Helper to create a functor instance for Add
function add(a: number, b: number): InstructionF<number> {
    const instruction: AddInstruction = { type: 'Add', a, b };
    return {
        tag: 'Add',
        value: instruction,
        map: <B>(f: (a: number) => B) => add(a, b) as any // Placeholder
    };
}


// The FreeMonad type definition
abstract class FreeMonad<T, F_INST> {
  abstract flatMap<U>(fn: (value: T) => FreeMonad<U, F_INST>): FreeMonad<U, F_INST>;
  abstract map<U>(fn: (value: T) => U): FreeMonad<U, F_INST>;

  static Pure<T, F_INST>(value: T): FreeMonad<T, F_INST> {
    return new Pure(value);
  }

  static FlatMap<T, F_INST>(value: FreeMonad<any, F_INST>, fn: (val: any) => FreeMonad<T, F_INST>): FreeMonad<T, F_INST> {
    return new FlatMap(value, fn);
  }

  static Lift<A, F_INST>(effect: F_INST): FreeMonad<A, F_INST> {
      // This would typically be used to lift an effect into the FreeMonad context.
      // For this challenge, we'll focus on FlatMap and Pure.
      return new FlatMap(FreeMonad.Pure(undefined as any), () => new Effect(effect)) as any;
  }
}

class Pure<T, F_INST> extends FreeMonad<T, F_INST> {
  constructor(public readonly value: T) {
    super();
  }

  flatMap<U>(fn: (value: T) => FreeMonad<U, F_INST>): FreeMonad<U, F_INST> {
    return fn(this.value);
  }

  map<U>(fn: (value: T) => U): FreeMonad<U, F_INST> {
    return new Pure(fn(this.value));
  }
}

class FlatMap<T, F_INST> extends FreeMonad<T, F_INST> {
  constructor(
    public readonly value: FreeMonad<any, F_INST>,
    public readonly fn: (val: any) => FreeMonad<T, F_INST>
  ) {
    super();
  }

  flatMap<U>(nextFn: (value: T) => FreeMonad<U, F_INST>): FreeMonad<U, F_INST> {
    return new FlatMap(this, (val) => nextFn(val));
  }

  map<U>(fn: (value: T) => U): FreeMonad<U, F_INST> {
    return new FlatMap(this, (val) => new Pure(fn(val)));
  }
}

// A special kind of FlatMap that represents an effect
class Effect<T, F_INST> extends FreeMonad<T, F_INST> {
    constructor(public readonly instruction: F_INST) {
        super();
    }

    flatMap<U>(fn: (value: T) => FreeMonad<U, F_INST>): FreeMonad<U, F_INST> {
        // When we flatMap an Effect, the next step is to chain another computation *after* this effect is processed.
        // The interpreter will handle executing this effect and then continuing with 'fn'.
        return new FlatMap(this, fn);
    }

    map<U>(fn: (value: T) => U): FreeMonad<U, F_INST> {
        return new FlatMap(this, (val) => new Pure(fn(val)));
    }
}

// Interpreter function
function interpret<T, F_INST>(
  freeMonad: FreeMonad<T, F_INST>,
  handler: (instruction: F_INST) => any
): T {
  if (freeMonad instanceof Pure) {
    return freeMonad.value;
  } else if (freeMonad instanceof FlatMap) {
    const resolvedValue = interpret(freeMonad.value, handler);
    return interpret(freeMonad.fn(resolvedValue), handler);
  } else if (freeMonad instanceof Effect) {
    // When we encounter an Effect, we call the handler
    const effectResult = handler(freeMonad.instruction);
    // The handler returns a value, which then needs to be interpreted.
    // If the handler itself returns a FreeMonad, we should interpret that.
    if (effectResult instanceof FreeMonad) {
        return interpret(effectResult, handler);
    }
    // Otherwise, assume the handler produced a raw value, and we're done with this branch.
    return effectResult;
  }
  throw new Error("Unknown FreeMonad type");
}


// --- Example 2 with refined structure ---

// Let's assume our instruction type F_INST is `InstructionF<any>` for this example,
// where the `value` field within InstructionF is the actual instruction data.

// A handler that processes InstructionF effects
const instructionHandler = <A>(effect: InstructionF<any>): A => {
  switch (effect.tag) {
    case 'ConsoleLog':
      console.log(`[LOG]: ${effect.value.message}`);
      // The handler should return a value that can continue the computation.
      // For logging, we might return nothing, or a value that the next step expects.
      return undefined as any;
    case 'Add':
      const result = effect.value.a + effect.value.b;
      console.log(`[ADD]: ${effect.value.a} + ${effect.value.b} = ${result}`);
      // The handler returns the result of the operation, which becomes the 'resolvedValue' for the next FlatMap.
      return result as any;
    default:
      throw new Error(`Unknown instruction tag: ${(effect as any).tag}`);
  }
};

// Computation that logs a message
const logMessageComputation = FreeMonad.FlatMap(
    FreeMonad.Pure(undefined as void), // A starting point
    () => FreeMonad.Lift<void, InstructionF<any>>(consoleLog("First message"))
);

console.log("--- Running Log Message Computation ---");
interpret(logMessageComputation, instructionHandler);
// Expected output in console:
// [LOG]: First message

// Computation that adds two numbers and then logs the result
const addAndLogComputation = FreeMonad.FlatMap(
    FreeMonad.Lift<number, InstructionF<any>>(add(5, 3)), // Add 5 and 3
    (sum: number) => FreeMonad.Lift<void, InstructionF<any>>(consoleLog(`The sum is: ${sum}`)) // Log the sum
);

console.log("\n--- Running Add and Log Computation ---");
interpret(addAndLogComputation, instructionHandler);
// Expected output in console:
// [ADD]: 5 + 3 = 8
// [LOG]: The sum is: 8

// Computation that logs, then adds, then logs again
const complexComputation = FreeMonad.FlatMap(
    FreeMonad.Lift<void, InstructionF<any>>(consoleLog("Starting complex task")),
    () => FreeMonad.FlatMap(
        FreeMonad.Lift<number, InstructionF<any>>(add(10, 20)),
        (sum: number) => FreeMonad.Lift<void, InstructionF<any>>(consoleLog(`Intermediate sum: ${sum}`))
    )
);

console.log("\n--- Running Complex Computation ---");
interpret(complexComputation, instructionHandler);
// Expected output in console:
// [LOG]: Starting complex task
// [ADD]: 10 + 20 = 30
// [LOG]: Intermediate sum: 30

Example 3: Chaining Operations and Returning a Final Value

This example demonstrates how a Free Monad can be used to build a sequence of operations that ultimately produce a specific result.

// Using the InstructionF and interpreter from Example 2

// A computation that adds two numbers, and then returns the square of the sum.
const addAndSquareComputation = FreeMonad.FlatMap(
    FreeMonad.Lift<number, InstructionF<any>>(add(7, 3)), // Calculate 7 + 3 = 10
    (sum: number) => {
        const squared = sum * sum;
        return FreeMonad.Pure(squared); // Return the squared value
    }
);

console.log("\n--- Running Add and Square Computation ---");
const finalResult = interpret(addAndSquareComputation, instructionHandler);
console.log(`Final result: ${finalResult}`);
// Expected output in console:
// [ADD]: 7 + 3 = 10
// Final result: 100

Constraints

  • The FreeMonad implementation should be generic over the result type T and the effect type F.
  • The interpret function should be generic and work with any F that can be handled by the provided handler.
  • The interpreter should be tail-recursive or use an iterative approach to avoid stack overflow issues with deeply nested computations. (For this challenge, a direct recursive approach is acceptable, but be mindful of performance for very large computations).
  • The F type (the effect type) should be representable as a functor, meaning it has a map operation. You can assume this structure for the effects you define in your examples (e.g., InstructionF has a map method).

Notes

  • Think carefully about how you represent the "effect" (F) within your FreeMonad. A common pattern is to use a discriminated union of instruction types, where each instruction represents a specific effect.
  • The handler function is the key to interpreting the FreeMonad. It defines how each effect is executed. This separation allows you to define computations once and run them in different environments (e.g., console logging vs. sending logs to a server).
  • Consider using helper functions (like lift, pure, flatMap) to make building FreeMonad computations more concise and readable.
  • The map operation on a FreeMonad can be implemented by transforming the final result of a computation. Alternatively, it can be seen as lifting a pure function to operate on the result of a FreeMonad computation.
Loading editor...
typescript