Skip to content

Instantly share code, notes, and snippets.

# divarvel/continuation.js Last active May 11, 2018

implementation of the continuation monad in JS
 console.log("\033[39mRunning tests…"); function assertEquals(actual, expected, description) { if(typeof actual === "undefined") { console.error("\033[31m" + description + " not implemented\033[39m"); } else { if(actual !== expected) { console.error("\033[31m" + description + " failed, expected " + expected + ", got " + actual + "\033[39m"); } else { console.log(description + " \033[32m ok\033[39m"); } } } // A continuation is a computation that's been interrupted // you give it a callback (function from a to r) and it will resume the // computation by giving your callback a value of type a, eventually producing // a value of type r // So we can describe a continuation as a function from (a function from a to // r) to r // Cont r a :: (a -> r) -> r // Let's define return :: a -> m a // for Cont, it's // a -> Cont r a // or // a -> ((a -> r) -> r) function returnCont(value) { // value has type a // we have to construct a value of type Cont r a // that is (a -> r) -> r return function(cb) { return cb(value); }; } // Helpers // Curried add function to have more legible tests function add(x) { return function(y) { return x + y; }; } var add10 = add(10); var add5 = add(5); var cont4 = returnCont(4); function runCont(continuation) { return continuation && continuation(add10); } assertEquals(runCont(cont4), 14, "returnContTest"); // Let's define map :: f a -> (a -> b) -> f b // for Cont, it's // Cont r a -> (a -> b) -> Cont r b // or // ((a -> r) -> r) -> (a -> b) -> ((b -> r) -> r) //; function mapCont(continuation, f) { // continuation has type (a -> r) -> r // f has type a -> b // // we have to construct a value of type (b -> r) -> r return function(cb) { // cb has type b -> r // we have to construct a value of type r var result = continuation(function(x) { // since continuation has type (a -> r) -> r // x has type a // and we have to construct a value of type r // the only way we have to produce a value of type r is by calling // cb with a value of type b // the only way we have to produce a value of type b is by calling // f with a value of type a // x is the only value of type a we have return cb(f(x)); }); return result; }; } function curriedMap(f) { return function(continuation) { return mapCont(continuation, f);}; } function identity(x) { return x; } function compose(f, g) { return function(x) { return f(g(x)); }; } function curriedCompose(f) { return function(g) { return function(x) { return f(g(x)); }; }; } console.log("=== Functor Laws ==="); // for all // m of type Cont r a // mapCont(m, identity) === m assertEquals(runCont(mapCont(cont4, identity)), runCont(cont4), "mapCont identity"); // for all // m of type Cont r a // f of type a -> b // g of type b -> c // mapCont(m, compose(g,f)) === compose(curriedMap(g), curriedMap(f))(m) assertEquals( runCont(mapCont(cont4, compose(add5, add10))), runCont(compose( curriedMap(add5), curriedMap(add10) )(cont4)), "mapCont composition"); // Let's define apply :: m (a -> b) -> m a -> m b // Cont r (a -> b) -> Cont r a -> Cont r b // or // (((a -> b) -> r) -> r) -> ((a -> r) -> r) -> ((b -> r) -> r) function applyCont(fCont, cont) { // fCont has type ((a -> b) -> r) -> r // cont has type (a -> r) -> r // // we have to construct a value of type (b -> r) -> r return function(callback) { // callback has type b -> r // we have to construct a value of type r var result = fCont(function(f) { // f has type a -> b // we have to construct a value of type r return cont(function(value) { // value has type a // we have to construct a value of type r return callback(f(value)); }); }); return result; }; } console.log("=== Applicative Laws ==="); // for all // u of type Cont r (a -> b) // v of type Cont r (b -> c) // w of type Cont r c // applyCont(applyCont(applyCont(returnCont(curriedCompose), u), v), w) // === // applyCont(u, applyCont(v, w)) (function () { var u = returnCont(add10); var v = returnCont(add5); var w = returnCont(5); assertEquals( runCont(applyCont(applyCont(applyCont(returnCont(curriedCompose), u), v), w)), runCont(applyCont(u, applyCont(v, w))), "applyCont composition" ); })(); // for all // f of type (a -> b) // x of type a // applyCont(returnCont(f), returnCont(x)) === returnCont(f(x)) assertEquals( runCont(applyCont(returnCont(add5), returnCont(4))), runCont(returnCont(add5(4))), "applyCont homomorphism" ); // for all // u of type Cont r (a -> b) // y of type a // applyCont(u, returnCont(y)) === applyCont(returnCont(function(f) { return f(y); }), u) (function() { var u = returnCont(add10); function apply(value) { return function(f) { return f(value); }; } assertEquals( runCont(applyCont(u, returnCont(4))), runCont(applyCont(returnCont(apply(4)), u)), "applyCont interchange" ); })(); // Let's define join :: m (m a) -> m a // Cont r (Cont r a) -> Cont r a // or // ((Cont r a -> r) -> r) -> ((a -> r) -> r) // ((((a -> r) -> r) -> r) -> r) -> ((a -> r) -> r) function joinCont(outerContinuation) { // outerContinuation has type ((((a -> r) -> r) -> r) -> r) -> r // we have to construct a value of type (a -> r) -> r return function(resultCallback) { // resultCallback has type (a -> r) // we have to construct a value of type r var outerResult = outerContinuation(function(innerContinuation) { // innerContinuation has type (a -> r) -> r // we have to construct a value of type r var innerResult = innerContinuation(function(x) { // x has type a // we have to construct a value of type r return resultCallback(x); }); return innerResult; }); return outerResult; }; } // Let's define bind :: m a -> (a -> m b) -> m b // for cont, it's // Cont r a -> (a -> Cont r b) -> Cont r b // or // ((a -> r) -> r) -> (a -> ((b -> r) -> r)) -> ((b -> r) -> r) function bindCont(continuation, f) { return joinCont(mapCont(continuation, f)); } console.log("=== Monad Laws ==="); // for all // a of type a // k of type a -> Cont r a // bindCont(returnCont(a), k) === k(a) assertEquals( runCont(bindCont(cont4, function(x) { return returnCont(x); })), runCont(returnCont(4)), "bindCont left indentity" ); // for all // m of type Cont r a // bindCont(m, returnCont) === m assertEquals( runCont(bindCont(cont4, returnCont)), runCont(cont4), "bindCont right indentity" ); // for all // m of type Cont r a // k of type a -> Cont r b // h of type b -> Cont r c // bindCont(m, function(x) { return bindCont(k(x), h); }) === bindCont(bindCont(m, k), h) assertEquals( runCont(bindCont(cont4, function(x) { return bindCont(returnCont(x), returnCont); })), runCont(bindCont(bindCont(cont4, returnCont), returnCont)), "bindCont composition" ); // Let's try to define extract :: m a -> a // for cont, it's // Cont r a -> a // or // ((a -> r) -> r) -> a function extractCont(continuation) { // continuation has type (a -> r) -> r // // we have to construct a value of type a // ToDo }
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.