Sunday, August 26, 2012

Learning CoffeeScript, F#, and Haskell (and brushing up on math)

I've started to get very interested in new programming languages, as a result of working with people at http://www.VersionOne.com. At V1, they use CoffeeScript for some of the UI features. While also brushing up on some of my math fundamentals, I started watching this old (but good) video series:  http://www.learner.org/resources/series66.html?pop=yes&pid=189

The three algorithms I wanted to implement are factorial, the permutations algorithm, and combinations algorithm. The mathematical short hands for these are typically:
• n!
• P(n, r)
• C(n, r)
To read more about these, you can find thousands of pages on the internet, including http://en.wikipedia.org/wiki/Permutation. But, I like http://www.MathIsFun.com in the algebra section.

Anyway, it's easier for me to memorize math concepts when I write my own functions to give me conceptual, hands-on grounding.

CoffeeScript:

factorial = (number) ->
total = { Value : 1 }
iteration = (number, total) ->
unless number is 0
total.Value = total.Value * number
iteration number - 1, total
total.Value
iteration number, total
factorialSplit = (number) ->
total = { Value : 1 }
factorialSplit_iteration number, total
total.Value
factorialSplit_iteration = (number, total) ->
unless number is 0
total.Value = total.Value * number
factorialSplit_iteration number - 1, total
total.Value

permutations = (totalNumberOfItems, numberOfItemsToChoose) ->
unless numberOfItemsToChoose <= totalNumberOfItems
throw "numberOfItemsToChoose cannot exceed totalNumberOfItems"
total = factorial totalNumberOfItems
divisorBase = totalNumberOfItems - numberOfItemsToChoose
divisorTotal = factorial divisorBase
total / divisorTotal

combinations = (totalNumberOfItems, numberOfItemsToChoose) ->
unless numberOfItemsToChoose <= totalNumberOfItems
throw "numberOfItemsToChoose cannot exceed totalNumberOfItems"
total = factorial totalNumberOfItems
divisorBase = totalNumberOfItems - numberOfItemsToChoose
divisorSubTotal = factorial divisorBase
total / divisorTotal
console.log factorial 5
console.log factorial 10

console.log factorialSplit 5
console.log factorialSplit 10

console.log permutations 5, 3
console.log permutations 12, 4

console.log combinations 15, 5
console.log combinations 5, 3

Syntax Explanation

The syntax is a simplification of JavaScript, and is inspired by languages like Ruby and Python, for example. A few key highlights:
• The "->" syntax just means that what follows will be the definition of a function.
• Whitespace is significant (get over it).
• The last statement in a function is the return value, though you can return values earlier by using the return statement.
• I made two versions of factorial, one with an embedded function defined within the first, and split one that uses a call to a separately defined function.
Using with Node.js on Windows

Testing with Node.js was trivial. I ran "npm install coffee-script -g" then after creating JMath.coffee, ran "coffee -c JMath.coffee", and finally typed "node JMath.js".

The output was:

120
3628800
120
3628800
60
11880
3003
10

Running the coffee -c command generates the following JavaScript code:

// Generated by CoffeeScript 1.3.3
(function() {
var combinations, factorial, factorialSplit, factorialSplit_iteration, permutations;

factorial = function(number) {
var iteration, total;
total = {
Value: 1
};
iteration = function(number, total) {
if (number !== 0) {
total.Value = total.Value * number;
iteration(number - 1, total);
}
};
return iteration(number, total);
};

factorialSplit = function(number) {
var total;
total = {
Value: 1
};
factorialSplit_iteration(number, total);
};

factorialSplit_iteration = function(number, total) {
if (number !== 0) {
total.Value = total.Value * number;
factorialSplit_iteration(number - 1, total);
}
};

permutations = function(totalNumberOfItems, numberOfItemsToChoose) {
var divisorBase, divisorTotal, numberOfEvents, total;
if (!(numberOfItemsToChoose <= totalNumberOfItems)) {
throw "numberOfItemsToChoose cannot exceed totalNumberOfItems";
}
total =  factorial(totalNumberOfItems);
divisorBase = totalNumberOfItems - numberOfItemsToChoose;
divisorTotal = factorial(divisorBase);
};

combinations = function(totalNumberOfItems, numberOfItemsToChoose) {
var divisorAdditionalToReduceBy, divisorBase, divisorSubTotal, divisorTotal, numberOfEvents, total;
if (!(numberOfItemsToChoose <= totalNumberOfItems)) {
throw "numberOfItemsToChoose cannot exceed totalNumberOfItems";
}
total = factorial(totalNumberOfItems);
divisorBase = totalNumberOfItems - numberOfItemsToChoose;
divisorSubTotal = factorial(divisorBase);
};

console.log(factorial(5));

console.log(factorial(10));

console.log(factorialSplit(5));

console.log(factorialSplit(10));

console.log(permutations(5, 3));

console.log(permutations(12, 4));

console.log(combinations(15, 5));

console.log(combinations(5, 3));

}).call(this);

I've been working with Joe Koberg at V1, and he's been exploring a lot of functional languages, which has sparked my interest. Here are my first attempts at writing the same functions in F# and in Haskell:

F#:

open System

let rec factorial (n : uint64) =
if n = 0UL then
1UL
else
n * factorial (n - 1UL)

let permutations totalNumberOfItems numberOfItemstoChoose =
let total = factorial totalNumberOfItems
let divisorBase = totalNumberOfItems - numberOfItemstoChoose
let divisorTotal = factorial divisorBase
total / divisorTotal

let combinations totalNumberOfItems numberOfItemsToChoose =
let total = factorial totalNumberOfItems
let divisorBase = totalNumberOfItems - numberOfItemsToChoose
let divisorSubTotal = factorial divisorBase
let divisorTotal = (divisorSubTotal * divisorAdditionalToReduceBy)
let result = total / divisorTotal
result

printfn "%A" (factorial 5UL)
printfn "%A" (factorial 10UL)

printfn "%A" (permutations 5UL 3UL)
printfn "%A" (permutations 12UL 4UL)

printfn "%A" (combinations 15UL 5UL)
printfn "%A" (combinations 5UL 3UL)

-- n!
factorial number =
if number < 1 then
1
else
number * factorial (number - 1)

factorial2 0 = 1
factorial2 n = n * factorial (n - 1)

-- P(n, r)
permutations totalNumberOfItems itemsToChoose =
(factorial totalNumberOfItems) / (factorial (totalNumberOfItems - itemsToChoose) )

permutations2 n r =
fac_n / fac_n_minus_r
where
fac_n = factorial n
fac_n_minus_r = factorial (n - r)

-- C(n, r)
combinations totalNumberOfItems itemsToChoose =
(factorial totalNumberOfItems) / ((factorial (totalNumberOfItems - itemsToChoose) ) * (factorial itemsToChoose) )

combinations2 n r =
fac_n / ( fac_n_minus_r * fac_r )
where
fac_n = factorial n
fac_n_minus_r = factorial (n - r)
fac_r = factorial r

Now, in the Haskell version there are a couple of versions of each, but it's still less code than any of the others. What I love about this is the minimal number of parentheses, no curly braces, and the where clause that assigns "local definitions" for the permutations2 and combinations2 functions. I'll admit that until I read http://en.wikibooks.org/wiki/Haskell/Variables_and_functions, I was a bit miffed as to how to do this without defining a constant outside the function, which would have made no sense at all for reusability.

Thus, while I like all three of these languages so far, I'm most intrigued by the Haskell program and its economy of syntax.