Javascript Currying – An Interpretation

As intrigued and obsessed [confession] I am with this Dynamic language, my foray into Functional programming via JS has definitely wired quite a bit of neuron networks which seem to mutate (should I say grow) as days progress. This interpretation of Currying in JS is one byproduct of such mutation.

I have been using the conventional approach advocated by Crockford in his book “JavaScript: The Good Parts” (see below)

Function.prototype.crockfordCurry = function () {
	"use strict";
	var slice = Array.prototype.slice,
		args = slice.apply(arguments),
		that = this;
	return function () {
		return that.apply(null, args.concat(slice.apply(arguments)));
	};
};

until an year back when I started re-looking at Currying as a first-class Functional programming feature and Haskell’s implementation (where almost always curried functions are used to achieve multiple arguments thus having all functions have exactly one argument) of it caught my attention and led me to think why would one need to curry as below and painstakingly compute (highlighted in code below),

function add(x) {
	"use strict";
	return function (y) {
		return x + y;
	};
}

function multiply(x) {
	"use strict";
	return function (y) {
		return x * y;
	};
}

//Creating the curried functions
var adder = add.crockfordCurry();
var multiplier = multiply.crockfordCurry();
//Finding the sum of 1,2 & 3 with the curried function
console.log(adder(adder(1)(2))(3));
//Finding the product of 1,2 & 3 with the curried function
console.log(multiplier(multiplier(1)(2))(3));

especially when computational values are more than 2 and there is little or no use of the resultant partially applied functions; thus automating this and giving user a direct option to compute the results with just a curried function that can accept any number of arguments a.k.a computational values in one shot (thereby living up to the true definition excerpt from Wikipedia below):


In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments (or a tuple of arguments) into evaluating a sequence of functions, each with a single argument (partial application). It was introduced by Moses Schönfinkel and later developed by Haskell Curry.


Function.prototype.haskellCurry = function () {
	"use strict";
	var slice = Array.prototype.slice,
		that = this;
	return function () {
		var	jsEval,
			jsApply,
			fn,
			args = slice.apply(arguments),
			result = args[0];
		jsEval = function () {
			args = slice.apply(arguments);
			fn = that.call(null, result);
			jsApply.apply(null, args);
		};
		jsApply = function () {
			args = slice.apply(arguments);
			result = fn.call(null, args[0]);
			if (args.length > 1) {
				jsEval.apply(null, args.slice(1));
			}
		};
		jsEval.apply(null, args.slice(1));
		return result;
	};
};

And you end up using the curried functions quite conveniently this way (see highlighted):

//Creating the curried functions
var adder2 = add.haskellCurry(),
	multiplier2 = multiply.haskellCurry();
//Finding the sum of 1, 2 & 3 with the curried function
console.log(adder2(1, 2, 3));
//Finding the product of 1, 2, 3, 4, 5 & 6 with the curried function
console.log(multiplier2(1, 2, 3, 4, 5, 6));

I have employed the Meta-Circular Evaluator principle here, along with Partial Application, Cumulative Recursion (with tail call optimization) and Closures to devise this currying operation in JavaScript.

And most surprising was that I found this approach resonate well with a paper (“Making a Fast Curry: Push/Enter vs Eval/Apply for higher-order languages” by none other than the great Simon Peyton Jones and Simon Marlow) published by Microsoft Research on March 17, 2004. I stumbled upon this actually quite recently which prompted me to let this piece of code thaw that was lying in cold a.k.a code storage for the past one year.

Hey! I now have a way to formally or rather [computer] scientifically explain my code.

Though the authors in their paper, drew a conclusion that the ‘Eval-Apply’ currying approach should be employed in compiled implementations, I was curious to find out how it would fare in an interpreted one. Well here’s my jslitmus benchmarking results that seem to corroborate their recommendation (Charts shows ops/second – higher is better!):

Currying Benchmarks

Anyone who likes to fiddle around and see if they can push the bars on the ‘Eval-Apply’ implementation are free to do that at my Github Repo.

Happy Coding!

JSpell

I was able to implement a JavaScript based spelling corrector based on an article by Peter Norvig (How to Write a Spelling Corrector) and wanted to share this with any interested reader. I always wanted to do this the moment I was shared this link by my mentor and friend (almost 2-3 years now). I always had it in my wish-list and now it’s an accomplishment (a good note to end the year I guess). It is so special and unique in regards to employing Bayes theorem in devising the actual algorithm for the spelling corrector. The code has been optimized to a great extent yet preserved adequate styling for brevity. Future work as suggested by Norvig (in his original article) hasn’t been accommodated though. I have enjoyed using currying extensively especially for the precedence-based filtering part in the algorithm. The Spelling Corrector is an object with the following 2 interfaces:

  1. train – use this function to provide the text for the training model.
  2. correct – use this function to provide the words (or a list) for corrections.

Please read the article (link provided above) for all the details. Additional information (especially training text information) could be found here . I have also documented the code for readability.

var NorvigSpellChecker = function () {
	var that = {},
		filter = /([a-z]+)/g,
		alphabets = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'],
		NWORDS = {};//Training Model
	
	var train = function(trainingText) {
		var features = trainingText.match(filter);
		for(var f in features) {
			var feature = features[f];
			if (NWORDS.hasOwnProperty(feature)) {
				NWORDS[feature] += 1;
			}
			else {
				NWORDS[feature] = 1;
			}
		}
	};
	
	var edits1 = function (words) {
		var edits1Set = [];
		for(var w = 0; w < words.length; w++) {
			var word = words[w];
			for (var i = 0; i <= word.length; i++) {
				//splits (a & b)
				var a = word.slice(0,i),
					b = word.slice(i),
					c = b.slice(1),
					d = b.slice(2);
				if (b != '') {
					//deletes
					edits1Set.push(a + c);
					//transposes
					if (b.length > 1) {
						edits1Set.push(a + b.charAt(1) + b.charAt(0) + d);
					}
					//replaces & inserts
					for (var j = 0; j < alphabets.length; j++) {
						edits1Set.push(a + alphabets[j] + c);//replaces
						edits1Set.push(a + alphabets[j] + b);//inserts
					}
				}
				else {
					//inserts (remaining set for b == '')
					for (var j = 0; j < alphabets.length; j++) {
						edits1Set.push(a + alphabets[j] + b);
					}
				}
			}
		}
		return edits1Set;
	};
	
	var edits2 = function (words) {
		return edits1(edits1(words));
	};

	Object.prototype.isEmpty = function () {
		var that = this;
		for(var prop in that) {
			if(that.hasOwnProperty(prop))
				return false;
		}
		return true;
	};

	Function.prototype.curry = function () {
		var slice = Array.prototype.slice,
			args = slice.apply(arguments),
			that = this;
		return function () {
			return that.apply(null, args.concat(slice.apply(arguments)));
		};
	};
	
	var known = function () {
		var knownSet = {};
		for (var i = 0; knownSet.isEmpty() && i < arguments.length; i++) {
			var words = arguments[i];
			for (var j = 0; j < words.length; j++) {
				var word = words[j];
				if (!knownSet.hasOwnProperty(word) && NWORDS.hasOwnProperty(word)) {
					knownSet[word] = NWORDS[word];
				}
			}
		}
		return knownSet;
	};
	
	var max = function(candidates) {
		var maxCandidateKey = null,
			maxCandidateVal = 0,
			currentCandidateVal;
		for (var candidate in candidates) {
			currentCandidateVal = candidates[candidate];
			if (candidates.hasOwnProperty(candidate) && currentCandidateVal > maxCandidateVal) {
				maxCandidateKey = candidate;
				maxCandidateVal = currentCandidateVal;
			}
		}
		return maxCandidateKey;
	};

	var correct = function () {
		var corrections = {};
		for (var i = 0; i < arguments.length; i++) {
			var word = arguments[i];
			var candidates = known.curry()([word],edits1([word]),edits2([word]));
			corrections[word] = candidates.isEmpty() ? word : max(candidates);
		}
		return corrections;
	};
	
	that.train = train;
	that.correct = correct.curry();
	
	return that;
};
I have also hosted the source code (free for use) and sample test code. Please provide the training text as a string in the sample test code for trying JSpell. Happy New Year!