Last active
March 5, 2024 06:27
-
-
Save c2d7fa/c9e1a85d743b2033d515b0f693a72c47 to your computer and use it in GitHub Desktop.
Expressing a specific instance of the free monad in TypeScript
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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" |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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