		// Diagonalizes a generator function that:
		// - returns when the computation is complete
		// - throws to prune a bad branch
		// - yields a recursive call to explore a candidate branch
		function diagonalize(fn, args = []) {
		var rec = [fn(...args)];
		for (var i = 0; i < Infinity; ++i) {
		var neo = [];
		for (var fun of rec) {
		while (true) {
		try {
		var got = fun.next();
		if (got.done) {
		return got.value;
		} else {
		neo.push(got.value);
		}
		} catch (e) {
		break;
		}
		// - yields an array of generators to explore infinite branches
		function diagonalize(func) {
		var visit = [[null, func(), null]];
		var revis = [];
		var index = 0;
		visits: while (index < visit.length \|\| revis.length > 0) {
		if (revis.length > 0) {
		var [back,func,argm] = visit[revis.pop()];
		} else {
		var [back,func,argm] = visit[index];
		}
		try {
		var next = func.next(argm);
		if (next.done) {
		if (back === null) {
		return next.value;
		} else {
		visit[back][2] = next.value;
		revis.push(back);
		};
		} else {
		for (var down of next.value) {
		visit.push([index, down, null]);
		};
		}
		}
		if (neo.length === 0) {
		throw "Search failed.";
		} else {
		rec = neo;
		};
		};
		} catch (e) {}
		++index;
		}
		};

		module.exports = diagonalize;

example.js

		var diagonalize = require(".");

		// Performs a search on binary strings
		function* search(cond, str = "") {
		yield search(cond, "0" + str);
		yield search(cond, "1" + str);
		if (cond(str)) {
		return str;
		// Searches for a 12-bit string following the 0101... pattern
		function* search(s = "") {
		if (s.length === 20 && /^(01)*$/.test(s)) {
		return s;
		} else if (/(11)/.test(s)) {
		throw "pruned";
		} else {
		throw null;
		}
		var a = yield [
		search("0" + s),
		search("1" + s),
		];
		return a;
		};
		};

		// Searches for a 12-bit string that matches /^(011)*$/
		console.log(diagonalize(search, [str => {
		return str.length === 12 && /^(011)*$/.test(str);
		}, ""]));
		console.log(diagonalize(search));

package.json

		{
		"name": "diagonalize",
		"version": "0.1.1",
		"version": "0.1.2",
		"description": "Searches through infinite branches",
		@@ -5,0 +5,0 @@ "main": "diagonalize.js",

diagonalize - npm Package Compare versions

New alerts