:chap_num: 5

:prev_link: 04_data

:next_link: 06_object

:load_files: ["js/code/ancestry.js", "js/code/05_higher_order.js"]

= Higher-Order Functions =

(((bug)))A large program is an expensive program. And not because of

the time it takes to build it. Rather, a large program provides a lot

of room in which mistakes (bugs) can hide, and, by the complexity that

comes with size, make understanding the program—which is necessary to

fix and prevent such mistakes—harder.

Let us briefly go back to the final two example programs in the

introduction. The first is self-contained, and six lines long.

[source,javascript]

----

var total = 0, count = 1;

while (count <= 10) {

total += count;

count += 1;

}

console.log(total);

----

The second relies on two external functions, and is one line long.

[source,javascript]

----

console.log(sum(range(1, 10)));

----

Which one is more likely to contain a bug?

If we count the size of the definitions of `sum` and `range`, the

second program is also big—even than the first. But still, I'd argue

that it is more likely to be correct.

The reason for this is that, by first building up a language in which

to express the problem, and then solving the problem in the terms of

the problem's own domain, it gains clarity. Summing a range of numbers

isn't about loops and counters, it is about ranges and sums.

The definitions of the vocabulary itself (the functions `sum` and

`range`) will still have to concern itself with loops and counters and

other silly details. But because they are expressing simpler concepts

(the building blocks are simpler than the building), they are easier

to get right.

Of course, getting a sum over a range of numbers right is trivial with

or without vocabulary. This example is intended as a miniature model

of other, actually difficult problems.

== Abstraction ==

(((abstraction)))In the context of programming, the usual term used

for such vocabularies is _abstractions_. Abstractions hide details,

and give us the ability to talk on a higher (more abstract) level.

(((recipe)))Another analogy is this recipe for pea soup.

____

Put 1 cup of dried peas per person in a container. Add water until

they are well covered. Leave peas in the water for at least 12 hours.

Take the peas out of the water, and put them in a cooking pan. Add 4

cups of water per person. Cover the pan and keep the peas barely

cooking for two hours. Take half an onion per person. Chop it. Add it

to the peas. Take a stalk of celery per person. Chop it. Add it to the

peas. Take a carrot per person. Chop it. Add it to the peas. Cook for

10 more minutes.

____

Compared to this one.

____

Per person: 1 cup dried split peas, half a chopped onion, a stalk of

celery, and a carrot.

Soak peas for 12 hours. Simmer them for 2 hours in 4 cups of water.

Chop and add vegetables, and cook for 10 more minutes.

____

The second is shorter, and easier to interpret. It does rely on you

understanding a few more cooking-related words—“soak”, “simmer”, and,

I guess, “vegetables”.

When programming, since we can't rely on all the words we need already

having been created by previous generations, waiting for us in the

dictionary, it is easy to fall into the pattern of the first

recipe—work out the precise steps the computer has to perform, one by

one, blind to the higher-level concepts that they express. It has to

become a second nature, during programming, to be on the lookout for

new words to create.

== Abstracting array traversal ==

Plain functions, as we've seen them so far, are a good way to build

abstractions. But sometimes they fall short.

(((for loop)))In the previous chapter, this type of `for` loop made

several appearances:

[source,javascript]

----

var array = [1, 2, 3];

for (var i = 0; i < array.length; i++) {

var current = array[i];

// do something with current

}

----

What it tries to say is “for each element in the array, do this”. But

it uses a very roundabout way that involves a counter variable, a

check against the array's length, and an extra variable declaration to

pick out the current element. Apart from being a bit of an eyesore,

this also gives us a lot of space for potential mistakes—accidentally

reuse the `i` variable, misspell `length` as `lenght`, confuse the `i`

and `current` variables, and so on.

Well then, let us try to abstract this into a function. Can you think

of a way?

The problem is that, whereas most functions just take some values,

combine them, and return something, these `for` loops contain a piece

of code that they must execute. It is easy to write a function that

goes over an array and calls `console.log` on every element:

[source,javascript]

----

function logEach(array) {

for (var i = 0; i < array.length; i++)

print(array[i]);

}

----

(((array,traversal)))(((function,as value)))(((forEach method)))But

what if we want to do something else than logging the elements? Since

“doing something” can be represented as a function and since functions

are also values, we can pass our action as a function value:

[source,javascript]

----

function forEach(array, action) {

for (var i = 0; i < array.length; i++)

action(array[i]);

}

forEach(["Wampeter", "Foma", "Granfalloon"], console.log);

// → Wampeter

// → Foma

// → Granfalloon

----

Often, you won't pass a pre-defined function to `forEach`, but create

a function value no the spot instead.

[source,javascript]

----

var numbers = [1, 2, 3, 4, 5], sum = 0;

forEach(numbers, function(number) {

sum += number;

});

console.log(sum);

// → 15

----

This looks quite a lot like the classical `for` loop, with its body

written as a block below it. Except that now the body is inside of the

function value, as well as inside of the parentheses of the call to

`forEach` and inside a regular statement. This is why it has to be

finished with the punctuation `});`.

In this pattern, we can simply specify a variable name (`number`) for

the current element as the function's argument, rather than having to

pick it out the array ourselves.

We do not need to write `forEach` ourselves. It is available as a

standard method on arrays (taking the function as first argument,

since the array is already provides as the thing the method acts on).

As an example, here is a function from the previous chapter that

contains two array-traversing loops.

[source,javascript]

----

function gatherCorrelations(journal) {

var numbers = {};

for (var entry = 0; entry < journal.length; ++entry) {

var events = journal[entry].events;

for (var i = 0; i < events.length; i++) {

var event = events[i];

if (!(event in tables))

tables[event] = phi(tableFor(event, journal));

}

}

return numbers;

}

----

Using `forEach` makes it slightly shorter and less noisy:

[source,javascript]

----

function gatherCorrelations(journal) {

var numbers = {};

journal.forEach(function(entry) {

entry.events.forEach(function(event) {

if (!(event in tables))

tables[event] = phi(tableFor(event, journal));

});

});

return numbers;

}

----

== Higher-order functions ==

(((function,higher-order)))The term for functions that operate on

functions (by taking them as arguments, or returning them) is

_higher-order functions_. For JavaScript programmers, who are used to

functions being regular values, there is actually nothing remarkable

about the fact that such functions exist. The term comes from

mathematics, where the distinction between functions and other values

is taken a little more seriously.

Higher-order functions allow us to abstract over actions as well as

regular values. They come in several forms. You can have functions

that create a new function.

[source,javascript]

----

function greaterThan(n) {

return function(m) { return m > n; };

}

var greaterThan10 = greaterThan(10);

console.log(greaterThan10(11));

// → true

----

Or functions that change another function.

[source,javascript]

----

function noisy(f) {

return function(arg) {

console.log("calling with", arg);

var val = f(arg);

console.log("called with", arg, "got", val);

return val;

};

}

----

Or even create functions that implement your own types of control

flow.

[source,javascript]

----

function unless(test, then) {

if (!test) then();

}

function repeat(times, body) {

for (var i = 0; i < times; i++) body(i);

}

repeat(3, function(n) {

unless(n % 2, function() {

console.log(n, "is even");

});

});

// → 0 "is even"

// → 1 "is even"

----

(((lexical scoping)))(((closure)))The “lexical scoping” rules that we

discussed in chapter 3 greatly work to our advantage when using

functions in this way. In the example above, the `n` variable is a

parameter to the outer function, but because the inner function lives

inside the environment of the outer one, it does have access to it.

Because of this, the bodies of such functions can freely use the

variables around them, and thus play a role similar to the regular

`{}` blocks that form the bodies of loops and conditional statements.

An important difference is that variables declared inside of them do

not end up in the environment of the outer function. And that is

usually a good thing.

== Passing on arguments ==

The `noisy` function above, which wraps its argument in another

function, has a rather serious deficit.

[source,javascript]

----

function noisy(f) {

return function(arg) {

console.log("calling with", arg);

var val = f(arg);

console.log("called with", arg, "got", val);

return val;

};

}

----

If `f` takes more than one parameter, only the first one is passed

through to it. We could add a bunch of arguments to the inner function

(`arg1`, `arg2`, and so on), and pass them to `f`, but it is unclear

how many would be necessary. It would also deprive `f` of the

information in `arguments.length`, since we'd always pass the same

amount of arguments to it, it wouldn't know how many argument were

_really_ given.

For these kinds of situations, JavaScript functions have an `apply`

method. The `apply` method will call the function, passing a given

array (or pseudo-array) as its arguments.

[source,javascript]

----

function transparentWrapping(f) {

return function() {

return f.apply(null, arguments);

};

}

----

That's a particularly useless function, but it shows the pattern we

are interested in—the resulting function will pass all of given

arguments, and only those arguments, to `f`. It does this by passing

its own `arguments` object to `apply`. The first argument to `apply`,

for which we are passing `null` here, will be explained in REF(obj).

== Array filtering ==

(((array)))Higher-order functions that somehow apply a function to the

elements of an array are widely used in JavaScript. The `forEach`

method is the most primitive such function. There are a number of

other variants available as methods on arrays. In order to familiarize

ourselves with them, let us play around with another data set.

A few years ago, someone crawled through a lot of archives in order to

put together a book on the history of my family name

(“Haverbeke”—literally “Oatbrook”). Though I was hoping to find

knights, pirates, and alchemists, the book turns out to be mostly full

of Flemish farmers. For my amusement, I extracted the information on

my direct ancestors, and put it into a computer-readable format. Let

us play with this data.

== JSON ==

(((JSON)))The file I created looks something like this:

[source,application/json]

----

[

{"name": "Emma de Milliano", "sex": "f",

"born": 1876, "died": 1956,

"father": "Petrus de Milliano",

"mother": "Sophia van Damme"},

{"name": "Carolus Haverbeke", "sex": "m",

"born": 1832, "died": 1905,

"father": "Carel Haverbeke",

"mother": "Maria van Brussel"},

.. and so on

]

----

This notation is very similar to JavaScript's way of writing arrays

and objects, with a few restrictions. All property names are

surrounded by quotes, and only simple data expressions (no function

calls, or variables, or anything that requires actual computation) are

allowed.

This format is called JSON, pronounced “Jason”, which stands for

JavaScript Object Notation. It is used as a data storage and

communication format that corresponds nicely to JavaScript's data

structures. JSON is widely used to send information back and forth

over the Internet.

JavaScript provides two functions, `JSON.stringify` and `JSON.parse`,

that convert data from and to this format.

[source,javascript]

----

var string = JSON.stringify({name: "X", born: 1980});

console.log(string);

// → {"name":"X","born":1980}

console.log(JSON.parse(string)).born;

// → 1980

----

The variable `ANCESTRY_FILE`, available in the sandbox for this

chapter as well as in a

http://eloquentjavascript.net/code/ancestry.js[a downloadable file] on

the website!!tex (`eloquentjavascript.net/code`)!!,

contains the content of my JSON file as a string. Let us decode it and

see how many people it contains:

[source,javascript]

----

var ancestry = JSON.parse(ANCESTRY_FILE);

console.log(ancestry.length);

// → 40

----

== Filtering an array ==

A function passed as an argument to a higher-order function doesn't

just represent an action that can be run. It also returns a value, and

we could use it to, for example, make a decision.

To find the people in the ancestry data set that were young in the

1924, the following function might be helpful. It filters out the

elements in an array that don't pass a test.

[source,javascript]

----

function filter(array, test) {

var passed = [];

for (var i = 0; i < array.length; i++) {

if (test(array[i]))

passed.push(array[i]);

}

return passed;

}

console.log(filter(ancestry, function(person) {

return person.born > 1900 && person.born < 1925;

}));

// → [{name: "Philibert Haverbeke", ...}, ...]

----

Three people in the file were alive and young in 1924: My grandfather,

grandmother, and great-aunt.

Like `forEach`, `filter` is also a standard method on arrays. The

example only uses our own definition in order to show what it does

internally.

== Transforming with map ==

Say we have an array of person object, produced by filtering the

`ancestry` array somehow. But we want an array of names, which is

easier to read through.

The `map` method transforms an array by applying a function to all of

its elements, and building a new array from the results. The new array

will have the same length as the input array, but its content will

have been “mapped” to a new form by the function.

[source,javascript]

----

function map(array, transform) {

var mapped = [];

for (var i = 0; i < array.length; i++)

mapped.push(transform(array[i]));

return mapped;

}

var over90 = ancestry.filter(function(person) {

return person.died - person.born > 90;

});

console.log(map(over90, function(person) {

return person.name;

}));

// → ["Clara Aernoudts", "Emile Haverbeke",

"Maria Haverbeke"]

----

Interestingly, the people that lived to over 90 years of age are the

same set of people that we saw before—the people were young in the

1920s, which happens to be the youngest generation in my data set. I

guess medicine has really come a long way.

Of course, `map` is also a standard method on arrays.

== Summarizing with reduce ==

Another common pattern of computation on arrays is computing a single

value from them. Our primordial example, the summing of a range of

numbers, is an instance of this. If we wanted to find the person with

the earliest year of birth in the data set, that would also follow

this pattern.

First, you take a start value. Then, for each element in the array,

you combine the element and the current value to create a new value.

The higher-order operation that represents this pattern is called

_reduce_ (or sometimes _fold_). It is a little less straightforward

than the previous examples, but still not hard to follow.

[source,javascript]

----

function reduce(array, combine, start) {

var current = start;

for (var i = 0; i < array.length; i++)

current = combine(current, array[i]);

return current;

}

console.log(reduce([1, 2, 3, 4], function(a, b) {

return a + b;

}, 0));

// → 10

----

The standard array method `reduce` has an additional convenience. If

your array contains at least one element, you are allowed to leave off

the `start` argument, and the method will take the first element of

the array as its start value, and start reducing at the second

element.

To use this to find my most ancient known ancestor, we can write

something like this:

[source,javascript]

----

console.log(ancestry.reduce(function(min, cur) {

if (cur.born < min.born) return cur

else return min;

}));

// → {name: "Pauwels van Haverbeke", born: 1535, …}

----

== Composability ==

Let us back up for a moment and consider how we would have written the

previous example (finding the person with the earliest year of birth)

without higher order functions. The code is not that much worse:

[source,javascript]

----

var min = ancestry[0];

for (var i = 1; i < ancestry.length; i++) {

var cur = ancestry[i];

if (cur.born < min.born)

min = cur;

}

console.log(min);

// → {name: "Pauwels van Haverbeke", born: 1535, …}

----

There are a few more variables being created and assigned to, and the

program is two lines longer, but still quite easy to understand.

The higher-order function approach really starts to shine when you

need to compose several concepts. As an example, let us write code

that finds the average age for men and for women in the data set.

[source,javascript]

----

function average(array) {

function plus(a, b) { return a + b; }

return array.reduce(plus) / array.length;

}

function age(p) { return p.died - p.born; }

function male(p) { return p.sex == "m"; }

function female(p) { return p.sex == "f"; }

console.log(average(ancestry

.filter(male).map(age)));

// → 61.67

console.log(average(ancestry

.filter(female).map(age)));

// → 54.56

----

(It is a bit of a shame that we have to define `plus` as a

function—operators in JavaScript, unlike functions, are not values, so

we can't just pass `+`.)

Instead of tangling all of the logic required into a big loop, we can

neatly decompose it into the concepts we are interested in (deciding

on sex, computing age, averaging numbers), and apply those one by one

to get the result we were looking for.

This is _fabulous_ for writing clear code. But there is a dark cloud

on the horizon.

== The cost ==

In the happy land of pretty, elegant code and rainbows, there lives a

mean spoil-sport of a monster called “inefficiency.”

Reducing the processing of an array into a sequence of cleanly

separated steps that each do something with the array and produce a

new array is easy to think about. But building up all those arrays in

_inefficient_.

Passing a function to `forEach` and letting that method handle the

array iteration for us is convenient and elegant. But function calls

in JavaScript are _costly_.

And so it goes with a lot of techniques that help improve the clarity

of a program. They add additional layers between the raw things the

computer is doing and the concepts we are working with, and thus cause

the machine to perform more work. This is not a inescapable, iron

law—there are programming languages that have better support for

building abstractions without adding inefficiencies, and even in

JavaScript, an experienced programmer can find ways to write

relatively abstract code that is still fast—but it is a problem that

comes up all the time.

Fortunately, most computers are insanely fast, and if you are

processing a modest set of data, or doing something that only has to

happen on a human time scale (once, or once every time the user clicks

a button), then it _does not matter_ whether you wrote the pretty

solution that takes half a millisecond, or the super-optimized

solution that takes a tenth of a millisecond.

What does matter is that you keep a an eye on how often your code is

going to run. If you have a loop inside a loop (directly, or though

the outer loop calling a function that ends up performing the inner

loop), the code inside the inner loop will end up running N×M times,

where N is the amount of times the outer loop repeats, and M the

amount of times the inner loop repeats. If that inner loop contains

another loop that makes P rounds, its body will run M×N×P times, and

so on. This adds up.

== Great-great-great-great-... ==

My grandfather, Philibert Haverbeke, is included in the data file. As

a final example problem, I want to know whether the most ancient

person in the data (Lieven van Haverbeke) is my direct ancestor, and

if so, how much DNA I theoretically share with him.

First, I build up an object that makes it possible to easily find

people by name.

[source,javascript]

----

var byName = {};

ancestry.forEach(function(person) {

byName[person.name] = person;

});

console.log(byName["Philibert Haverbeke"]);

// → {name: "Philibert Haverbeke", …}

----

Now, the problem is not entirely as simple as following the `parent`

properties and counting how many we need to reach Lieven. There are

several cases in the family tree where people married their second

cousins (these people were, for the most part, living in tiny

communities). This causes the branches of the family tree to re-join

in a few places, which means I share more than 1 / 2^generations^

(each generation splitting the gene pool in two) with this person.

A reasonable way to think about this problem is to put it in similar

terms as the `reduce` algorithm. A family tree has a more interesting

structure than a flat array—a structure that in fact already suggests

a way of computing values from it.

Given a person, a function to combine values from the two parents of a

given person, and a zero value that is to be used for unknown persons,

the `reduceAncestors` function computes a value from a family tree.

[source,javascript]

----

function reduceAncestors(person, f, zero) {

function reduce(person) {

if (person == null) return zero;

var father = byName[person.father];

var mother = byName[person.mother];

return f(person, reduce(father),

reduce(mother));

}

return reduce(person, 0);

}

----

The inner function (`reduce`) handles a single person. Through the

magic of recursion, it can simply call itself to handle the father and

the mother of this person. The results, along with the person object

itself, are passed to `f`.

Some people's father and mother are not in the data set (obviously, or

it'd include an awful lot of people). So when looking up a parent

doesn't yield a value, `reduce` simply returns the `zero` value that

was passed to `reduceAncestors`.

We can then use this to compute the amount of DNA my grandfather

shared with Lieven van Haverbeke, and divide that by four.

[source,javascript]

----

console.log(reduceAncestors(

byName["Philibert Haverbeke"],

function(person, fromFather, fromMother) {

if (person.name == "Lieven van Haverbeke")

return 1;

else

return (fromFather + fromMother) / 2;

},

0

) / 4);

// → 0.00098

----

The person with the name Lieven van Haverbeke obviously shared 100% of

his DNA with Lieven van Haverbeke (there are no people who share names

in the data set). All other people share the average of the amount

that their parents share.

So, statistically speaking, I share about 0.1% of my DNA with this

16th-century person. The chances of one of my 44 non-XY chromosomes

coming from him are thus rather small. Hover, assuming no extramarital

children in the family history, I do have his Y chromosome.

Data structures (such as this family tree) can often be made easier to

use (as well as easier to think about) by finding analogues to

`forEach` (iterate), `map` (transform), and `reduce` that apply to

them. A `forEachAncestor` function would simply call a function for

each ancestor. A mapping function probably isn't much use for this

data structure, but would, for example, be useful for the list type

that was introduced in the exercises to the last chapter.

== Partial application ==

FIXME

== Summary ==

Being able to pass function values to other functions is not a random

gimmick, but a deeply useful aspect of JavaScript. It allows us to

describe computations with “holes” in them using functions, and allow

the code that calls these functions to define what should be filled in

in the holes by passing in function values.

Arrays provide a number of very useful higher-order methods—`forEach`

to do something with each element in an array, `map` to build a new

array where each element has been put through a function, and `reduce`

to combine all the elements in the array into a single value.

Functions have an `apply` method that can be used to call them passing

a set of arguments for an array, which is useful when the amount of

arguments is not always the same.

== Exercises ==

=== Every and some ===

Arrays also come with the standard methods `every` and `some`, which

are analogous to the `&&` and `||` operators.

Both take a predicate function that, when called with an array element

as argument, returns true or false. Just like `&&` only returns a true

value when the expressions on both sides are true, `every` only

returns true only when the predicate returned true for _all_ elements

of the array. Similarly, `some` returns true as soon as the predicate

returned true for _any_ of the elements. They do not process more

elements than necessary—for example, if `some` finds that the

predicate holds for the first element of the array, it will not look

at the values after that.

Write two functions, `every` and `some`, that behave like these

methods, except that they take the array as their first argument,

rather than being a method.

ifdef::html_target[]

[source,javascript]

----

// Your code here...

every([NaN, NaN, NaN], isNaN);

// → true

every([NaN, NaN, 4], isNaN);

// → false

some([NaN, 3, 4], isNaN);

// → true

some([2, 3, 4], isNaN);

// → false

----

endif::html_target[]

The two functions are each other's mirror image, in a way. As an

extra, somewhat silly, exercise, create a higher-order function

`logicReducer` that accepts a boolean argument (`positive`) and

creates `every` when given the value `false`, and `some` when given

the value `true`. (Don't just return the functions you defined

earlier. Have it return an anonymous function that uses the argument

given to `logicReducer`.)

''''

The functions can follow a similar pattern to the definition of

`forEach` at the start of the chapter, except that they must return

immediately (with the right value) when the predicate function returns

false—or true. Don't forget to put another `return` statement after

the loop, so that the function also returns the correct value when it

reaches the end of the array.

To solve the `logicReducer` part thoroughly, you will have to ensure

that it also works when the predicate functions return a value that is

not a boolean. The `Boolean` function can be used to convert the

returned value to a proper boolean before comparing it with the

`positive` variable. Alternatively, applying the logical not operator

twice (`!!`) also converts a value to a boolean.