Skip to content

Instantly share code, notes, and snippets.

@richdouglasevans
Forked from i-am-tom/chainRec.js
Last active November 1, 2018 09:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save richdouglasevans/4c0a197c3d8312961a1c7fba557f4425 to your computer and use it in GitHub Desktop.
Save richdouglasevans/4c0a197c3d8312961a1c7fba557f4425 to your computer and use it in GitHub Desktop.
Code from the fantas-eel post on ChainRec.
const daggy = require("daggy");
const { Loop, Done } = daggy.taggedSum("Loop", {
Loop: ["b"],
Done: ["a"]
});
Array.empty = () => [];
const Pair = T => {
const Pair_ = daggy.tagged("Pair", ["_1", "_2"]);
Pair_.prototype.map = function(f) {
return Pair_(this._1, f(this._2));
};
Pair_.prototype.ap = function(fs) {
return Pair_(fs._1.concat(this._1), fs._2(this._2));
};
Pair_.of = x => Pair_(T.empty(), x);
Pair_.prototype.chain = function(f) {
const that = f(this._2);
return Pair_(this._1.concat(that._1), that._2);
};
Pair_.chainRec = function(f, init) {
let acc = T.empty(),
step = Loop(init);
do {
const result = f(step.b);
acc = acc.concat(result._1);
step = result._2;
} while (step instanceof Loop);
return Pair_(acc, step);
};
return Pair_;
};
const Writer = Pair(Array);
const seqRec = upper =>
Writer.chainRec(
init => Writer([init], init >= upper ? Done(null) : Loop(init + 1)),
0
);
const seq = upper => {
const seq_ = init =>
init >= upper ? Writer([init], null) : Writer([init], init + 1).chain(seq_);
return seq_(0);
};
// console.log(seq(10000)._1) // Will fail
console.log(seqRec(10000)._1);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment