Skip to content

Instantly share code, notes, and snippets.

@c2d7fa
Last active March 5, 2024 06:27
Show Gist options
  • Save c2d7fa/c9e1a85d743b2033d515b0f693a72c47 to your computer and use it in GitHub Desktop.
Save c2d7fa/c9e1a85d743b2033d515b0f693a72c47 to your computer and use it in GitHub Desktop.
Expressing a specific instance of the free monad in TypeScript
// https://underscore.io/blog/posts/2015/04/23/deriving-the-free-monad.html
// Example of implementing a specific instance of a free monad (for getting and
// setting an integer value) in TypeScript. The type system is not expressive
// enough to express free monads in general, but we can express a specific
// instance.
type AtomicOperation<T> = ["get", (x: number) => T] | ["set", number, T];
type Program<T> = ["return", T] | ["suspend", AtomicOperation<Program<T>>];
const exampleProgram: Program<string> =
["suspend", ["get", (a) =>
["suspend", ["set", a + 1,
["suspend", ["get", (b) =>
["return", `Incremented ${a} so it became ${b}`]]]]]]];
function execute<T>(current: number, program: Program<T>): T {
if (program[0] === "return") return program[1];
const operation = program[1];
switch (operation[0]) {
case "get": return execute(current, operation[1](current));
case "set": return execute(operation[1], operation[2])
}
}
console.log(execute<string>(3, exampleProgram)); // => "Incremented 3 so it became 4"
// Here we implement the `program` procedure, which exploits generators to
// emulate something like Haskell's do-notation for this specific free monad
// instance.
type AtomicOperation<T> = ["get", (x: number) => T] | ["set", number, T];
type Program<T> = ["return", T] | ["suspend", AtomicOperation<Program<T>>];
function program<T>(generator: () => Generator<["get"] | ["set", number], T, any>): Program<T> {
const instance = generator();
function iterate(lastValue: any): Program<T> {
const result = instance.next(lastValue);
if (result.done) return ["return", result.value];
const operation = result.value as ["get"] | ["set", number];
switch (operation[0]) {
case "get": return ["suspend", ["get", (x: number) => iterate(x)]];
case "set": return ["suspend", ["set", operation[1], iterate(undefined)]];
}
}
return iterate(undefined);
}
const get: ["get"] = ["get"];
const set = (x: number): ["set", number] => ["set", x];
// Now we can write our program like this! It still has the same structure as
// above, just expressed in a more natural way.
const exampleProgram: Program<string> = program<string>(function* () {
const a = yield get;
yield set((yield get) * (yield get));
const b = yield get;
return `Squared ${a} so it became ${b}`;
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment