JavaScript/Higher-order programming - Revision history

Apollolux: /* Example: Detecting when all enemies have died in battle */ split out

2013-06-15T00:44:54Z

‎Example: Detecting when all enemies have died in battle: split out

Apollolux: /* Simple example: Potions */ split out

2013-06-15T00:43:45Z

‎Simple example: Potions: split out

Apollolux: /* Example: Maximum length of an array of strings */ split out

2013-06-15T00:42:49Z

‎Example: Maximum length of an array of strings: split out

Apollolux: /* Appendix A: Print module */

2013-06-15T00:38:48Z

‎Appendix A: Print module

Apollolux: Apollolux moved page Higher-order programming in JavaScript to JavaScript/Higher-order programming: new conventions

2013-06-15T00:30:32Z

Apollolux moved page Higher-order programming in JavaScript to JavaScript/Higher-order programming: new conventions

Apollolux: created from http://web.archive.org/web/20120828191718/http://www.spheredev.org/wiki/Higher-order_programming_in_JavaScript

2013-06-15T00:29:16Z

created from http://web.archive.org/web/20120828191718/http://www.spheredev.org/wiki/Higher-order_programming_in_JavaScript

New page

A '''higher-order function''' is a function that works with functions. That is, they either take them as arguments, or return them.

This article isn't about the theory behind higher-order functions or functional programming; you can find plenty of that on the intertubes. This article is about exploiting them to make coding in JavaScript a little easier.

Some examples make use of the <var>Print.js</var> module at the end of the page.

__TOC__

==Simple example: Potions==
We have HP, and we want some way to heal ourselves:
<syntaxhighlight>
var hero = {hp: 10, hpMax: 85};
</syntaxhighlight>

It'd be nice to have a Potion, a Super Potion and a Mega Potion, healing 10, 20 and 50 HP respectively. It'd also be nice to see a dialog saying which item was used and how much HP we recovered.

===The chump's way===
<syntaxhighlight>
function Potion() {
var oldHp = hero.hp;
hero.hp += 10;
if (hero.hp > hero.hpMax) hero.hp = hero.hpMax;

var heal = hero.hp - oldHp;
if (heal > 0)
Print.printLine("Drank Potion! Recovered " + heal + " HP.");
else
Print.printLine("Drank Potion! Nothing happened.");
}

function SuperPotion() {
var oldHp = hero.hp;
hero.hp += 20;
if (hero.hp > hero.hpMax) hero.hp = hero.hpMax;

var heal = hero.hp - oldHp;
if (heal > 0)
Print.printLine("Drank Super Potion! Recovered " + heal + " HP.");
else
Print.printLine("Drank Super Potion! Nothing happened.");
}

function MegaPotion() {
var oldHp = hero.hp;
hero.hp += 50;
if (hero.hp > hero.hpMax) hero.hp = hero.hpMax;

var heal = hero.hp - oldHp;
if (heal > 0)
Print.printLine("Drank Mega Potion! Recovered " + heal + " HP.");
else
Print.printLine("Drank Mega Potion! Nothing happened.");
}
</syntaxhighlight>

Ugh. Copy-pasting this was a pain. Imagine if we had to change the message format, or if we had 10 items. Miserable. Absolutely miserable. Anyway, we can use it like this:
<syntaxhighlight>
var inventory = [Potion, SuperPotion, MegaPotion];
inventory[0]();
inventory[1]();
inventory[2]();
</syntaxhighlight>

With the output:
<pre>
Drank Potion! Recovered 10 HP.
Drank Super Potion! Recovered 20 HP.
Drank Mega Potion! Recovered 45 HP.
</pre>

===A smarter way===
These potions do almost exactly the same thing. Let's reflect that in our code. We express the idea of a healing item '''once and only once'''. In fact, there's no reason to restrict it to HP.
<syntaxhighlight>
function HealingItem(name, stat, amount) {
return function () {
var oldStat = hero[stat];
hero[stat] += amount;
if (hero[stat] > hero[stat + "Max"]) hero[stat] = hero[stat + "Max"];

var heal = hero[stat] - oldStat;
if (heal > 0)
Print.printLine("Drank " + name + "! Recovered " + heal + " " + stat.toUpperCase() + ".");
else
Print.printLine("Drank " + name + "! Nothing happened.");
};
}

function Potion() {
return HealingItem("Potion", "hp", 10);
}

function SuperPotion() {
return HealingItem("Super Potion", "hp", 20);
}

function MegaPotion() {
return HealingItem("Mega Potion", "hp", 50);
}
</syntaxhighlight>

Here, the higher-order function is <code>HealingItem()</code>, because, as you can see, it returns a function as its result. Note that even after <code>HealingItem()</code> has returned, <var>name</var>, <var>stat</var> and <var>amount</var> are still "remembered". This funky property of returned functions is known as '''closure'''. We won't cover that here, but suffice to say, they're useful.
Potion(), SuperPotion() and MegaPotion() just wrap conveniently around HealingItem() so we don't have to provide all the mundane parameters such as the name, statistic and amount each time. We call them wrappers: they make code easier to read.

We can use them as before:
<syntaxhighlight>
var inventory = [Potion(), SuperPotion(), MegaPotion()];
inventory[0]();
inventory[1]();
inventory[2]();
</syntaxhighlight>

Producing the same output:
<pre>
Drank Potion! Recovered 10 HP.
Drank Super Potion! Recovered 20 HP.
Drank Mega Potion! Recovered 45 HP.
</pre>

Note that <code>Potion()</code>, <code>SuperPotion()</code> and <code>MegaPotion()</code> now ''make'' items, so we need to put the parentheses there to "manufacture" the potions.

This demonstrates both the power of JavaScript's functions, but also the flexibility provided by its '''reflection''': seeing and using program info when the program is running. Thanks to not restricting ourselves to HP, we can make ethers too:
<syntaxhighlight>
function Ether() {
return HealingItem("Ether", "mp", 10);
}

function SuperEther() {
return HealingItem("Super Ether", "mp", 20);
}

function MegaEther() {
return HealingItem("Mega Ether", "mp", 50);
}
</syntaxhighlight>

In the chump's way, this would have doubled the size of the code.

==Tools of the trade==
Let's focus on the functional constructs that help us work with lots of values. Don't worry too much about how they work, just that they do.

===forEach===
<syntaxhighlight>
function forEach(array, action) {
for (var i = 0; i < array.length; ++i)
action(array[i]);
}
</syntaxhighlight>

This function goes through each element of array and runs it through action. <code>forEach</code> is the ''higher-order function'', since it works on the ''first-class function'' passed through the <var>action</var> parameter.

Here's an example that prints a bunch of names:
<syntaxhighlight>
var names = ["John", "Dean", "Sam"];
forEach(names, Print.printLine);
Print.display();
</syntaxhighlight>

Output:
<pre>
John
Dean
Sam
</pre>

===map===
<syntaxhighlight>
function map(func, array) {
var result = [];
forEach(array, function (element) {
result.push(func(element));
});
return result;
}
</syntaxhighlight>

This function goes through all the elements of <var>array</var>, applies <var>func</var> to each one, and returns a new array with those transformed elements.

Here's an example of getting the squares of an array of numbers:
<syntaxhighlight>
function square(x) {
return x * x;
}

var numbers = [1, 2, 3, 4, 5];
var result = map(square, numbers);
Print.printLine(result.join(", "));
Print.display();
</syntaxhighlight>

The output is:
<pre>
1, 4, 9, 16, 25
</pre>

===filter===
<syntaxhighlight>
function filter(condition, array) {
var result = [];
forEach(array, function (element) {
if (condition(element))
result.push(element);
});
return result;
}
</syntaxhighlight>

This function filters out any element in array that doesn't return true for the condition. Here's an example to weed out odd numbers from an array:
<syntaxhighlight>
function isEven(number) {
return number % 2 === 0;
}

var numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
var result = filter(isEven, numbers);
Print.printLine(result.join(", "));
</syntaxhighlight>

And the output:
<pre>
2, 4, 6, 8, 10
</pre>

===reduce===
<syntaxhighlight>
function reduce(combine, base, array) {
forEach(array, function (element) {
base = combine(base, element);
});
return base;
}
</syntaxhighlight>

This one's a bit tricky. It goes through each element of the array, rolling the result along using the combine function. Here's an example of summing a bunch of numbers.
<syntaxhighlight>
function add(a, b) {
return a + b;
}

var numbers = [1, 2, 3, 4, 5];
var sum = reduce(add, 0, numbers);
Print.printLine(sum);
Print.display();
</syntaxhighlight>

The processing looks a bit like this:
<pre>
(0) [1, 2, 3, 4, 5] // start
(1) [2, 3, 4, 5] // 0 + 1 (result + head of array)
(3) [3, 4, 5] // 1 + 2
(6) [4, 5] // 3 + 3
(10) [5] // 6 + 4
(15) [] // 10 + 5
</pre>

Output:
<pre>
15
</pre>

==Example: Maximum length of an array of strings==
Say I've got this, an array of strings holding stats to be displayed in a box:
<syntaxhighlight>
var stats = [
"Hero L" + level,
"Exp: " + exp + " / " + next,
"",
"HP: " + hp + " / " + hpMax,
"MP: " + mp + " / " + mpMax
];
</syntaxhighlight>

In order to draw a window style around it, we'll need to find out which line is longest.

===The chump's way===
<syntaxhighlight>
var maxWidth = 0;
for (var i = 0; i < stats.length; ++i) {
if (maxWidth < GetSystemFont().getStringWidth(stats[i]))
maxWidth = GetSystemFont().getStringWidth(stats[i]);
}
</syntaxhighlight>

What's wrong with it?

* ''<code>for</code> loop is crappy'' - We're good coders, so we recognise that this looks for a maximum without even reading it. But if we really sat down and ''read'' it, we're looking at 20+ tokens spread across four lines. And this is just a simple loop. In a more complex loop body, a bug would be almost impossible to find.
* ''Focus is on iteration instead of task'' - The variable <var>i</var> occurs in no less than 5 places. As it turns out later on, we don't even need it.
* ''Copy-paste coding style'' - The body of the <code>for</code> loop has two lines which are almost identical. Copy-paste == more lines to change if a single line needs changing.

===A smarter way===
<syntaxhighlight>
var maxWidth = reduce(function (a, b) {
return a > b ? a : b;
}, 0, map(GetSystemFont().getStringWidth, stats));
</syntaxhighlight>

Basically, the stats have been ''mapped'' from strings to their widths according to the system font, and those widths have been ''reduced'' to find the maximum of them.

Note that we can use Sphere's API functions with our higher-order functions, just by omitting the "call" parentheses.

Why it's good:

* ''Less typing'' - Compare these to the chump's way. Do you really want to type all that? Less typing == less typos == less chance of errors.
* ''No unnecessary index'' - I told you we didn't need the index.
* ''No copy-paste'' - Copy-paste == bad. I shouldn't have to explain this.

===An even smarter way===
<syntaxhighlight>
var maxWidth = Math.max.apply(null, map(GetSystemFont().getStringWidth, stats));
</syntaxhighlight>

The kind folk behind Sphere's JavaScript engine gave us the standard JavaScript library. It doesn't include much, but it's got [https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Math/max Math.max], which we can link with our own higher-order functions to do lots of heavy lifting.

Same benefits as the smarter way, plus it's shorter, and now the intent is very, very clear. This is what we're aiming for.

==Example: Detecting when all enemies have died in battle==

Here's a bunch of enemies we're fighting against:
<syntaxhighlight>
var enemies = [
{name: "Duck", hp: 10},
{name: "Duck", hp: 10},
{name: "Goose", hp: 15}
];
</syntaxhighlight>

Let's kill them off:
<syntaxhighlight>
forEach(enemies, function (enemy) {
enemy.hp = 0;
});
</syntaxhighlight>

Now they're all dead.

Our problem is to find out when every enemy's HP has dropped to zero.
===The chump's way===
<syntaxhighlight>
var allDead = true;
for (var i = 0; i < enemies.length; ++i) {
if (enemies[i].hp > 0)
allDead = false;
}
</syntaxhighlight>

This presents another problem which isn't in the previous example: what if the variable <var>i</var> is being used for something? Battle systems tend to occur in loops, and for all we know, that loop could be using <var>i</var>. We could shift onto variable <var>j</var>, and then future code changes would move into variable <var>k</var>... and it goes on. What a mess.

Another problem was developing the algorithm itself: I had to stop and think, how should I do this?

# Should <var>allDead</var> start false and turn into true when going through the loop and discovering all enemies are dead?
# Should <var>allDead</var> start true and turn into false when discovering a single living enemy?

I got side-tracked by the "how", and lost sight of the "what".

===A smarter way===
We could take advantage of our higher-order functions to express our intent more clearly:
<syntaxhighlight>
var allDead = filter(function (enemy) {
return enemy.hp > 0;
}, enemies).length === 0;
</syntaxhighlight>

This is easy to read: we filter through all enemies to get all the living ones in an array. If the length of that array is 0, they're all dead. Again, shorter and a lot easier to read.

Note also that it expresses what I was after: all enemies are dead if the length of living enemies found is zero.

==Final words==
As you've hopefully seen here, functions can make working with lots of data easier. It's no silver bullet, just like object-oriented programming, but used the right way, and mixed with other techniques, it can help you beat code complexity before it beats you.

Some people avoid making new functions in JavaScript, due to namespace issues. In response to that, it's very possible to place functions inside little organised "modules" (See the further reading section.)

Some people avoid this style of programming altogether, due to the fact that they have trouble understanding it. Think of things this way: if you understood both traditional imperative programming and this style of programming equally well, wouldn't you choose the shorter one?

Finally, it's a nice change of pace if you're tired of using nested for loops.

==Further reading==
* [http://eloquentjavascript.net/chapter6.html EloquentJavaScript.net Chapter 6] - The whole nine yards of functional programming in JavaScript. Provides explanations, code examples and exercises.
* [https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array#Iteration_methods Mozilla's JavaScript Array iteration methods] - Functional programming methods introduced after JS 1.5.
* [http://w3future.com/html/stories/hop.xml Higher-order Programming] - Uses JavaScript for examples.
* [http://eloquentjavascript.net/chapter9.html EloquentJavaScript.net Chapter 9] - Deals with the global namespace pollution issue by using modules.

==Appendix A: Print module==
This goes in Print.js:
<syntaxhighlight>
var Print = function () {
var fullString = "";

function clear() {
fullString = "";
}

function print(value) {
fullString += value.toString();
}

function printLine(value) {
if (value)
print(value);
print("\n");
}

function display() {
Abort(fullString + "\n");
}

return {
clear: clear,
print: print,
printLine: printLine,
display: display
};
}();
</syntaxhighlight>

To use it, in your main script file:
<syntaxhighlight>
RequireScript("Print.js");
</syntaxhighlight>

[[Category:Tutorials]]

@@ Line 136: / Line 136: @@
 ==Example: Detecting when all enemies have died in battle==
+{{:JavaScript/Higher-order programming/Example 3}}
 ==Final words==

@@ Line 8: / Line 8: @@
 ==Simple example: Potions==
-We have HP, and we want some way to heal ourselves:
+{{:JavaScript/Higher-order programming/Example 1}}
 ==Tools of the trade==

@@ Line 259: / Line 259: @@
 ==Example: Maximum length of an array of strings==
-Say I've got this, an array of strings holding stats to be displayed in a box:
+{{:JavaScript/Higher-order programming/Example 2}}
 ==Example: Detecting when all enemies have died in battle==

@@ Line 381: / Line 381: @@
 ==Appendix A: Print module==
 This goes in Print.js:
-<syntaxhighlight>
-var Print = function () {
+{{:JavaScript/Higher-order programming/Print.js}}
 To use it, in your main script file:

← Older revision	Revision as of 00:30, 15 June 2013
(No difference)