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
divisorAdditionalToReduceBy = factorial numberOfItemsToChoose
divisorTotal = divisorSubTotal * divisorAdditionalToReduceBy
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.
You can learn more about the CoffeeScript by reading a few good resources:
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:
120362880012036288006011880300310
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 total.Value;
};
return iteration(number, total);
};
factorialSplit = function(number) {
var total;
total = {
Value: 1
};
factorialSplit_iteration(number, total);
return total.Value;
};
factorialSplit_iteration = function(number, total) {
if (number !== 0) {
total.Value = total.Value * number;
factorialSplit_iteration(number - 1, total);
}
return total.Value;
};
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);
return total / divisorTotal;
};
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);
divisorAdditionalToReduceBy = factorial(numberOfItemsToChoose);
divisorTotal = divisorSubTotal * divisorAdditionalToReduceBy;
return 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));
}).call(this);
F# and Haskell:
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 divisorAdditionalToReduceBy = factorial numberOfItemsToChoose
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)
Console.Read()
Haskell
-- 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.
Learn more about these two languages:
F# and Haskell:
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 divisorAdditionalToReduceBy = factorial numberOfItemsToChoose
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)
Console.Read()
Haskell
-- 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.
Learn more about these two languages:
- http://www.tryfsharp.org/ (Features online execution env)
- http://en.wikibooks.org/wiki/F_Sharp_Programming
- http://tryhaskell.org/ (Features online execution env)
- http://learnyouahaskell.com/chapters
- http://en.wikibooks.org/wiki/Haskell
0 comments:
Post a Comment