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);

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()

-- 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

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