Difference between revisions of "JavaScript/Higher-order programming"

Latest revision as of 00:44, 15 June 2013

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 Print.js module at the end of the page.

Simple example: Potions

We have HP, and we want some way to heal ourselves:

var hero = {hp: 10, hpMax: 85};

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

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.");
}

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:

var inventory = [Potion, SuperPotion, MegaPotion];
inventory[0]();
inventory[1]();
inventory[2]();

With the output:

Drank Potion! Recovered 10 HP.
Drank Super Potion! Recovered 20 HP.
Drank Mega Potion! Recovered 45 HP.

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.

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

Here, the higher-order function is HealingItem(), because, as you can see, it returns a function as its result. Note that even after HealingItem() has returned, name, stat and amount 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:

var inventory = [Potion(), SuperPotion(), MegaPotion()];
inventory[0]();
inventory[1]();
inventory[2]();

Producing the same output:

Drank Potion! Recovered 10 HP.
Drank Super Potion! Recovered 20 HP.
Drank Mega Potion! Recovered 45 HP.

Note that Potion(), SuperPotion() and MegaPotion() 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:

function Ether() {
  return HealingItem("Ether", "mp", 10);
}
 
function SuperEther() {
  return HealingItem("Super Ether", "mp", 20);
}
 
function MegaEther() {
  return HealingItem("Mega Ether", "mp", 50);
}

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

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

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

Here's an example that prints a bunch of names:

var names = ["John", "Dean", "Sam"];
forEach(names, Print.printLine);
Print.display();

Output:

John
Dean
Sam

map

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

This function goes through all the elements of array, applies func 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:

function square(x) {
  return x * x;
}
 
var numbers = [1, 2, 3, 4, 5];
var result = map(square, numbers);
Print.printLine(result.join(", "));
Print.display();

The output is:

1, 4, 9, 16, 25

filter

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

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:

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(", "));

And the output:

2, 4, 6, 8, 10

reduce

function reduce(combine, base, array) {
  forEach(array, function (element) {
    base = combine(base, element);
  });
  return base;
}

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.

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

The processing looks a bit like this:

(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

Output:

15

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:

var stats = [
  "Hero L" + level,
  "Exp: " + exp + " / " + next,
  "",
  "HP: " + hp + " / " + hpMax,
  "MP: " + mp + " / " + mpMax
];

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

The chump's way

var maxWidth = 0;
for (var i = 0; i < stats.length; ++i) {
  if (maxWidth < GetSystemFont().getStringWidth(stats[i]))
    maxWidth = GetSystemFont().getStringWidth(stats[i]);
}

What's wrong with it?

• for 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 i 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 for loop has two lines which are almost identical. Copy-paste == more lines to change if a single line needs changing.

A smarter way

var maxWidth = reduce(function (a, b) {
  return a > b ? a : b;
}, 0, map(GetSystemFont().getStringWidth, stats));

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

var maxWidth = Math.max.apply(null, map(GetSystemFont().getStringWidth, stats));

The kind folk behind Sphere's JavaScript engine gave us the standard JavaScript library. It doesn't include much, but it's got 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:

var enemies = [
  {name: "Duck", hp: 10},
  {name: "Duck", hp: 10},
  {name: "Goose", hp: 15}
];

Let's kill them off:

forEach(enemies, function (enemy) {
   enemy.hp = 0;
});

Now they're all dead.

Our problem is to find out when every enemy's HP has dropped to zero.

The chump's way

var allDead = true;
for (var i = 0; i < enemies.length; ++i) {
  if (enemies[i].hp > 0)
    allDead = false;
}

This presents another problem which isn't in the previous example: what if the variable i is being used for something? Battle systems tend to occur in loops, and for all we know, that loop could be using i. We could shift onto variable j, and then future code changes would move into variable k... 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?

1. Should allDead start false and turn into true when going through the loop and discovering all enemies are dead?
2. Should allDead 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:

var allDead = filter(function (enemy) {
  return enemy.hp > 0;
}, enemies).length === 0;

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

• EloquentJavaScript.net Chapter 6 - The whole nine yards of functional programming in JavaScript. Provides explanations, code examples and exercises.
• Mozilla's JavaScript Array iteration methods - Functional programming methods introduced after JS 1.5.
• Higher-order Programming - Uses JavaScript for examples.
• EloquentJavaScript.net Chapter 9 - Deals with the global namespace pollution issue by using modules.

Appendix A: Print module

This goes in Print.js:

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

To use it, in your main script file:

RequireScript("Print.js");