:chap_num: 5

:prev_link: 04_data

:next_link: 06_object

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

:zip: node/html

= Funciones de Order Superior =

ifdef::interactive_target[]

[chapterquote="true"]

[quote, Master Yuan-Ma, The Book of Programming]

____

Tzu-li y Tzu-ssu estaban

presumiendo acerca del tamaño de sus úlitmos programas. ‘Doscientas mil líneas

,’ dijo Tzu-li, ‘¡sin contar los comentarios!’. Tzu-ssu

respondió, ‘Pssh, el mío tiene ya casi *un millión* de líneas.’ El Maestro

Yuan-Ma dijo, ‘Mi mejor programa tiene quinientas líneas’. Oyendo esto,

Tzu-li y Tzu-ssu fueron iluminados.

____

endif::interactive_target[]

[chapterquote="true"]

[quote, C.A.R. Hoare, 1980 ACM Turing Award Lecture]

____

(((Hoare+++,+++ C.A.R.)))Hay dos formas de construir un diseño de

software: Una forma es hacerlo tan simple que obviamente no tenga

deficiencias, y la otra forma es hacerlo tan complicado que

no haya obvias deficiecias.

____

(((tamaño de un programa)))Un programa grande es costoso y no sólo

por el tiempo que toma construirlo. El tamaño casi siempre involucra

((complejidad)), y la complejidad confunde a los programadores. Los

programadores confundidos, a su vez, tienden a introducir errores

(_((bug))s_) en los programas. Un programa grande, además, da un amplio

espacio para que estos bugs se oculten, haciéndolos difíciles de encontrar.

(((ejemplo de la suma)))Regresemos brevemente a los dos programas finales

en la introducción. El primero es auto-contenido y tiene seis líneas de longitud.

[source,javascript]

----

var total = 0, cuenta = 1;

while (cuenta <= 10) {

total += cuenta;

cuenta += 1;

}

console.log(total);

----

El segundo depende de dos funciones externas y es una sola línea

[source,javascript]

----

console.log(suma(rango(1, 10)));

----

¿Cuál de los dos es más probable que tenga un bug?

(((tamaño del programa)))Si contamos el tamaño de definición de

`suma` y `rango`, el segungo programa también es grande–incluso más

grande que el primero. Pero aún así, yo diría que es más probable

que sea correcto.

(((abstracción)))(((lenguaje de cominio específico)))Es más probable que

sea correcto porque la solución es expresada en un ((vocabulario)) que

corresponde al problema que está siendo resuelto. Sumar un rango de

enteros no tiene que ver con bucles y contadores. Es acerca de

rangos y sumas.

Las definiciones de este vocabulario (las funciones `suma` y `rango` )

todavía incluirán bucles, contadores y otros detalles incidentales.

Pero debido a que están expresando conceptos más simples que el

programa como un todo, es más fácil acertar.

== Abstracción ==

En el contexto de la programación, vocabularios de este estilo son usualmente

llamados _((abstracción))_. Las abstracciones econden detalles y nos

dan la habilidad de hablar de los problemas en un nivel más alto (o más

abstracto).

(((analogía de la receta)))(((sopa de guisantes)))Como una analogía,

compara estas dos recetas para la sopa de guisantes:

____

Pon una 1 taza de guisantes secos por persona en un contenedor. Agrega agua

hasta que los guisantes estén cubiertos. Deja los guisantes en el agua

por lo menos 12 horas. Saca los guisantes del agua y ponlos en en un

sartén para cocer. Agrega 4 copas de agua por persona. Cubre el sartén y mantén

los hirviéndose a fuego lento por dos horas. Agrega la mitad de una cebolla por

persona. Córtala en piezas con un cuchillo. Agrégalas a los guisantes.

Toma un diente de ajo por persona. Córtalos en piezas con un cuchillo.

Agrégalos a los guisantes. Toma una zanahoria por persona. Córtalas

en piezas. ¡Con un cuchillo! Agrégalas a los guisantes. Cocina por 10

minutos más.

____

Y la segunda receta:

____

Por persona: 1 taza de guisantes partidos secos, media cebolla picada, un

diente de ajo y una zanohoria.

Remoja los guisantes por 12 horas

Soak peas for 12 hours. Hierve a fuego lento por 2 horas en

4 tazas(por persona). Pica y agrega los vegetales. Cocina por 10 minutos más.

____

(((vocabulario)))La segunda es más corta y más fácil de interpretar. Pero

necesitas entender unos cuántas palabras relacionadas con la cocina-__remojar__,

__picar__ y, imagino, __vegetal__.

Cuando programamos, no podemos confiar en que todas las palbras que necesitamos

estén esperándonos en el diccionario. Así que podrías caer en el patrón de

la primera receta–trabajar en los pasos precisos que la computadora debe realizar,

uno por uno, sin ver los conceptos de alto nivel que estos expresan.

(((abstracción)))Se tiene que convertir en una segunda naturaleza, para un

programador, notar cuando un concepto está rogando ser abstraído en

una nueva palabra.

== Abstrayendo transversal de array ==

(((array)))Las fuunciones planas, como hemos visto hasta ahora, son una buena forma

de construir abstracciones. Pero algunas veces se quedan cortas.

(((bucle for)))En el link:04_data.html#data[capítulo antterior], este tipo de

((bucle)) `for` apareció varias veces:

[source,javascript]

----

var array = [1, 2, 3];

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

var actual = array[i];

console.log(actual);

}

----

(((propiedad length,para

array)))(((array,indexado)))(((legibilidad)))Está tratando de decir,

"Cada elemento, escríbelo en la consola". Pero usa una forma rebuscada que

implica una variable `i`, una revisión del tamaño del array y una declaración

de variable extra para guardar el elemento actual. A parte de causar un poco de

dolor de ojos, esto nos da mucho espacio para errores potenciales. Podríamos

qccidentalmente reusar la variable `i`, escribir mal `length` como `lenght`,

confundir las variables `i` y `actual` y así por el estilo.

Así que tratemos de abstraer esto en una función. ¿Puedes pensar en alguna forma?

Bueno, es fácil escribir una función que vaya a través de un array y llamar

`console.log` en cada elemento.

[source,javascript]

----

function logEach(array) {

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

console.log(array[i]);

}

----

[[forEach]]

indexsee:[función de orden superior,función+++,+++ orden superior](((función,orden superior)))(((bucle)))(((array,

transversal)))(((función, como valor)))(((método forEach)))Pero, ¿qué pasa si

queremos hacer otra cosa que loggear los elementos? Debido a que "hacer algo"

puede ser representado como una función y las funciones son sólo valores, podemos pasar

nuestra acción como un valor función.

[source,javascript]

----

function forEach(array, accion) {

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

accion(array[i]);

}

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

// → Wampeter

// → Foma

// → Granfalloon

----

<<<<<<< HEAD

A menudo, no le pasas una función predefinida a `forEach` sino que

creas una función en el acto.

=======

(In some browsers, calling `console.log` in this way does not work.

You can use `alert` instead of `console.log` if this example fails to

work.)

Often, you don't pass a predefined function to `forEach` but create

a function value on the spot instead.

>>>>>>> marijnh/master

[source,javascript]

----

var numeros = [1, 2, 3, 4, 5], suma = 0;

forEach(numeros, function(numero) {

suma += numero;

});

console.log(suma);

// → 15

----

(((cuerpo de un bucle)))(((llaves)))Esto luce muy parecido al clásico

bucle `for`, con su cuerpo escrito debajo de él. Sin embargo,

ahora el cuerpo está dentro del valor función, así como

dentro de los ((paréntesis)) de la llamada a `forEach`. Esta es la

razón de que tenga que ser terminado con una llave _y_ un paréntesis de cierre.

(((variable local)))(((parámetro)))Usando este patrón, podemos especificar un nombre

de variable para el elemento actual(`numero`), en vez de tener que

tomarlo del array manuelmente.

(((array,métodos)))(((función,orden superior)))(((forEach

método)))(((array)))De hecho, no necesitamos escribir `forEach`

nosotros mismos. Está disponible como un método estándar en los arrays.

Debido a que el array le es pasado como el elemento sobre el que actúa

el método, `forEach` sólo recibe un argumento requerido: la función que será

ejecutada para cada elemento.

Para ilustrar lo útil que esto es, miremos otra vez la función del

link:04_data.html#analysis[capítulo anterior]. Contiene dos bucles que

recorren un arreglo.

[source,javascript]

----

function reuneCorrelaciones(diario) {

var phis = {};

for (var entrada = 0; entrada < diario.length; entrada++) {

var eventos = diario[entrada].events;

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

var evento = eventos[i];

if (!(evento in phis))

phis[evento] = phi(tableFor(evento, diario));

}

}

return phis;

}

----

(((método forEach))) `forEach` la hace un poco más corta y limpia.

[source,javascript]

----

function reuneCorrelaciones(diario) {

var phis = {};

diario.forEach(function(entrada) {

entrada.eventos.forEach(function(evento) {

if (!(evento in phis))

phis[evento] = phi(tableFor(evento, diario));

});

});

return phis;

}

----

== Funciones de Orden Superior ==

(((función,de orden superior)))(((función,como valor)))Las funciones que

operan en otras funceiones, ya sea tomándolas como argumentos o regresándolas,

son llamadas _funciones de orden superior_. Si ya has aceptado el hecho de que las funciones son

valores reulares, no hay nada de especial en el hecho de que estas funciones

existan. El términos viene de las ((matemáticas)), en dónde la distinción

entre las funciones y otros valores es tomado más seriamente.

(((abstracción)))Las funciones de orden superior nos permiten abstraer

_acciones_, no sólo valores. Pueden venir en diferentes formas. Por ejemplo

puedes tener funciones que creen nuevas funciones.

[source,javascript]

----

function mayorQue(n) {

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

}

var mayorQue10 = mayorQue(10);

console.log(mayorQue10(11));

// → true

----

Y puedes tener funciones que cambien otras funciones.

[source,javascript]

----

function ruidosa(f) {

return function(arg) {

console.log("llamando con", arg);

var val = f(arg);

console.log("llamada con", arg, "- got", val);

return val;

};

}

ruidosa(Boolean)(0);

// → llamando con 0

// → llamada con 0 - obtuve false

----

Incluso puedes escribir funciones que creen nuevos tipos ((control de flujo)).

[source,javascript]

----

function a_menos_que(condicion, entonces) {

if (!condicion) entonces();

}

function repetir(veces, cuerpo) {

for (var i = 0; i < veces; i++) cuerpo(i);

}

repetir(3, function(n) {

a_menos_que(n % 2, function() {

console.log(n, "es par");

});

});

// → 0 es par

// → 2 es par

----

(((inner function)))(((nesting,of functions)))((({}

(block))))(((local variable)))(((closure)))The ((lexical scoping))

rules that we discussed in link:03_functions.html#scoping[Chapter 3]

work to our advantage when using functions in this way. In the previous example, the `n` variable is a ((parameter)) to the outer function.

Because the inner function lives inside the environment of the outer

one, it can use `n`. The bodies of such inner functions can access the

variables around them. They can play a role similar to the `{}` blocks

used in regular loops and conditional statements. An important

difference is that variables declared inside inner functions do not

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

good thing.

== Passing along arguments ==

(((function,wrapping)))(((arguments object)))The `noisy` function

defined earlier, 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)), it gets only the first one.

We could add a bunch of arguments to the inner function (`arg1`,

`arg2`, and so on) and pass them all to `f`, but it is not clear how many

would be enough. This solution would also deprive `f` of the

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

number of arguments, it wouldn't know how many arguments were

originally given.

(((apply method)))(((array-like object)))(((function,application)))For

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

method. You pass it an array (or array-like object) of arguments, and

it will call the function with those arguments.

[source,javascript]

----

function transparentWrapping(f) {

return function() {

return f.apply(null, arguments);

};

}

----

(((null)))That's a useless function, but it shows the pattern we are

interested in—the function it returns passes all of the 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, can be used to simulate a

((method)) call. We will come back to that in the

link:06_object.html#call_method[next chapter].

== JSON ==

(((array)))(((function,higher-order)))(((forEach method)))(((data

set)))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. To familiarize

ourselves with them, let's play around with another data set.

(((ancestry example)))A few years ago, someone crawled through a lot

of archives and put together a book on the history of my family name

(Haverbeke—meaning Oatbrook). I opened it hoping to find

knights, pirates, and alchemists ... but the book turns out to be

mostly full of Flemish ((farmer))s. For my amusement, I extracted the

information on my direct ancestors and put it into a

computer-readable format.

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

]

----

indexsee:[JavaScript Object Notation,JSON](((World Wide Web)))This format is called JSON (pronounced “Jason”),

which stands for JavaScript Object Notation. It is widely used as a

data storage and communication format on the Web.

(((array)))(((object)))(((quoting,in JSON)))(((comment)))JSON is similar to

JavaScript's way of writing arrays and objects, with a few

restrictions. All property names have to be surrounded by double quotes, and

only simple data expressions are allowed—no function calls,

variables, or anything that involves actual computation. Comments are not

allowed in JSON.

(((JSON.stringify function)))(((JSON.parse

function)))(((serialization)))(((deserialization)))(((parsing)))JavaScript

gives us functions, `JSON.stringify` and `JSON.parse`, that convert

data from and to this format. The first takes a JavaScript value and

returns a JSON-encoded string. The second takes such a string and

converts it to the value it encodes.

[source,javascript]

----

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

console.log(string);

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

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

// → 1980

----

(((ANCESTRY_FILE data set)))The variable `ANCESTRY_FILE`, available in

the ((sandbox)) for this chapter and in

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

the website(!book (http://eloquentjavascript.net/code#5[_eloquentjavascript.net/code#5_])!), contains the

content of my ((JSON)) file as a string. Let's decode it and see how

many people it contains.

// include_code strip_log

[source,javascript]

----

var ancestry = JSON.parse(ANCESTRY_FILE);

console.log(ancestry.length);

// → 39

----

== Filtering an array ==

(((array,methods)))(((array,filtering)))(((filter

method)))(((function,higher-order)))(((predicate function)))To find

the people in the ancestry data set who were young in 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", …}, …]

----

(((function,as value)))(((function,application)))This uses the

argument named `test`, a function value, to fill in a “gap” in the

computation. The `test` function is called for each element, and its

return value determines whether an element is included in the returned

array.

(((ancestry example)))Three people in the file were alive and young in

1924: my grandfather, grandmother, and great-aunt.

(((filter method)))(((pure function)))(((side effect)))Note how the

`filter` function, rather than deleting elements from the existing

array, builds up a new array with only the elements that pass the

test. This function is _pure_. It does not modify the array it is

given.

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

example defined the function only in order to show what it does

internally. From now on, we'll use it like this instead:

[source,javascript]

----

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

return person.father == "Carel Haverbeke";

}));

// → [{name: "Carolus Haverbeke", …}]

----

== Transforming with map ==

(((array,methods)))(((map method)))(((ancestry example)))Say we

have an array of objects representing people, produced by filtering

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

easier to read.

(((function,higher-order)))The `map` method transforms an array by

applying a function to all of its elements and building a new array

from the returned values. 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.

// test: join

[source,javascript]

----

function map(array, transform) {

var mapped = [];

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

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

return mapped;

}

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

return person.died - person.born > 90;

});

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

return person.name;

}));

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

// "Maria Haverbeke"]

----

Interestingly, the people who lived to at least 90 years of age are the

same three people who we saw before—the people who were young in the

1920s, which happens to be the most recent generation in my data set.

I guess ((medicine)) has come a long way.

Like `forEach` and `filter`, `map` is also a standard method on

arrays.

== Summarizing with reduce ==

(((array,methods)))(((summing example)))(((reduce method)))(((ancestry

example)))Another common pattern of computation on arrays is computing

a single value from them. Our recurring example, summing a collection

of numbers, is an instance of this. Another example would be finding

the person with the earliest year of birth in the data set.

(((function,higher-order)))(((fold function)))The higher-order

operation that represents this pattern is called _reduce_ (or

sometimes _fold_). You can think of it as folding up the array, one

element at a time. When summing numbers, you'd start with the number

zero and, for each element, combine it with the current sum by adding

the two.

The parameters to the `reduce` function are, apart from the array, a

combining function and a start value. This function is a little less

straightforward than `filter` and `map`, so pay careful attention.

[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

----

(((reduce method)))The standard array method `reduce`, which of course

corresponds to this function, has an added convenience. If your array

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

`start` argument. The method will take the first element of the array

as its start value and start reducing at the second element.

(((ancestry example)))(((minimum)))To use `reduce` to find my most

ancient known ancestor, we can write something like this:

// test: no

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

(((loop)))(((minimum)))(((ancestry example)))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.

// test: no

[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 ((variable))s, and the program is two lines

longer but still quite easy to understand.

[[average_function]]

(((average

function)))(((composability)))(((function,higher-order)))Higher-order

functions start to shine when you need to _compose_ functions. As an

example, let's write code that finds the average age for men and for

women in the data set.

// test: clip

[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

----

(((plus function)))(((+ operator)))(((function,as value)))(It's a bit

silly that we have to define `plus` as a function, but operators in

JavaScript, unlike functions, are not values, so you can't pass them

as arguments.)

(((abstraction)))(((vocabulary)))Instead of tangling the logic into a

big ((loop)), it is neatly composed into the concepts we are

interested in—determining sex, computing age, and averaging numbers. We

can apply these one by one to get the result we are looking for.

This is _fabulous_ for writing clear code. Unfortunately, this clarity

comes at a cost.

== The cost ==

(((efficiency)))(((optimization)))In the happy land of elegant code

and pretty rainbows, there lives a spoil-sport monster called

_inefficiency_.

(((elegance)))(((array,creation)))(((pure

function)))(((composability)))A program that processes an array is most

elegantly expressed as a sequence of cleanly separated steps that each

do something with the array and produce a new array. But building up

all those intermediate arrays is somewhat expensive.

(((readability)))(((function,application)))(((forEach

method)))(((function,as value)))Likewise, passing a function to

`forEach` and letting that method handle the array iteration for us is

convenient and easy to read. But function calls in JavaScript are

costly compared to simple loop bodies.

(((abstraction)))And so it goes with a lot of techniques that help

improve the clarity of a program. Abstractions add 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 an 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 abstract

code that is still fast. But it is a problem that comes up a lot.

(((profiling)))Fortunately, most computers are insanely fast. If you

are processing a modest set of data or doing something that has

to happen only on a human time scale (say, every time the user clicks a

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

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

a tenth of a millisecond.

(((nesting,of loops)))(((inner loop)))(((complexity)))It is helpful to

roughly keep track of how often a piece of your program is going to

run. If you have a ((loop)) inside a loop (either directly or through

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 number of times the outer loop repeats and

_M_ is the number of times the inner loop repeats within each iteration

of the outer loop. If that inner loop contains another loop that makes

_P_ rounds, its body will run __M__×__N__×__P__ times, and so on. This

can add up to large numbers, and when a program is slow, the problem

can often be traced to only a small part of the code, which sits inside an inner loop.

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

(((ancestry example)))My ((grandfather)), Philibert Haverbeke, is

included in the data file. By starting with him, I can trace my

lineage to find out whether the most ancient person in the data,

Pauwels van Haverbeke, is my direct ancestor. And if he is, I would

like to know how much ((DNA)) I theoretically share with him.

(((byName object)))(((map)))(((data structure)))(((object,as

map)))To be able to go from a parent's name to the actual object that

represents this person, we first build up an object that associates

names with people.

// include_code strip_log

[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 `father`

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

several cases in the family ((tree)) where people married their second

cousins (tiny villages and all that). This causes the branches of the

family tree to rejoin in a few places, which means I share more than

1/2^_G_^ of my genes with this person, where _G_ for the number of

generations between Pauwels and me. This formula comes from the idea

that each generation splits the gene pool in two.

(((reduce method)))(((data structure)))A reasonable way to think about

this problem is to look at it as being analogous to `reduce`, which

condenses an array to a single value by repeatedly combining

values, left to right. In this case, we also want to condense our data

structure to a single value but in a way that follows family

lines. The _shape_ of the data is that of a family tree, rather than a

flat list.

The way we want to reduce this shape is by computing a value for a

given person by combining values from their ancestors. This can be

done recursively: if we are interested in person _A_, we have to

compute the values for __A__’s parents, which in turn requires us to

compute the value for __A__’s grandparents, and so on. In principle,

that'd require us to look at an infinite number of people, but since

our data set is finite, we have to stop somewhere. We'll allow a

((default value)) to be given to our reduction function, which will be

used for people who are not in the data. In our case, that value is

simply zero, on the assumption that people not in the list don't share

DNA with the ancestor we are looking at.

(((recursion)))(((reduceAncestors function)))Given a person, a

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

a default value, `reduceAncestors` condenses a value from a family

tree.

// include_code

[source,javascript]

----

function reduceAncestors(person, f, defaultValue) {

function valueFor(person) {

if (person == null)

return defaultValue;

else

return f(person, valueFor(byName[person.mother]),

valueFor(byName[person.father]));

}

return valueFor(person);

}

----

(((function,higher-order)))The inner function (`valueFor`) 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`, which

returns the actual value for this person.

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

((grandfather)) shared with Pauwels van Haverbeke and divide that by

four.

// start_code bottom_lines: 2

// test: clip

// include_code top_lines: 6

[source,javascript]

----

function sharedDNA(person, fromMother, fromFather) {

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

return 1;

else

return (fromMother + fromFather) / 2;

}

var ph = byName["Philibert Haverbeke"];

console.log(reduceAncestors(ph, sharedDNA, 0) / 4);

// → 0.00049

----

The person with the name Pauwels van Haverbeke obviously shared 100 percent

of his DNA with Pauwels van Haverbeke (there are no people who share

names in the data set), so the function returns 1 for him. All other

people share the average of the amounts that their parents share.

So, statistically speaking, I share about 0.05 percent of my ((DNA)) with

this 16th-century person. It should be noted that this is only a

statistical approximation, not an exact amount. It is a rather small

number, but given how much genetic material we carry (about 3 billion

base pairs), there's still probably some aspect in the biological

machine that is me that originates with Pauwels.

(((ancestry example)))(((reduceAncestors

function)))(((abstraction)))We could also have computed this number

without relying on `reduceAncestors`. But separating the general

approach (condensing a family tree) from the specific case (computing

shared DNA) can improve the clarity of the code and allows us to reuse

the abstract part of the program for other cases. For example, the

following code finds the percentage of a person's known ancestors who

lived past 70 (by lineage, so people may be counted multiple times):

// test: clip

[source,javascript]

----

function countAncestors(person, test) {

function combine(current, fromMother, fromFather) {

var thisOneCounts = current != person && test(current);

return fromMother + fromFather + (thisOneCounts ? 1 : 0);

}

return reduceAncestors(person, combine, 0);

}

function longLivingPercentage(person) {

var all = countAncestors(person, function(person) {

return true;

});

var longLiving = countAncestors(person, function(person) {

return (person.died - person.born) >= 70;

});

return longLiving / all;

}

console.log(longLivingPercentage(byName["Emile Haverbeke"]));

// → 0.129

----

Such numbers are not to be taken too seriously, given that

our data set contains a rather arbitrary collection of people. But the

code illustrates the fact that `reduceAncestors` gives us a useful

piece of ((vocabulary)) for working with the family tree data

structure.

== Binding ==

(((bind method)))(((partial

application)))(((function,application)))The `bind` method, which all

functions have, creates a new function that will call the original

function but with some of the arguments already fixed.

(((filter method)))(((function,as value)))The following code shows an

example of `bind` in use. It defines a function `isInSet` that

tells us whether a person is in a given set of strings. To call

`filter` in order to collect those person objects whose names are in a

specific set, we can either write a function expression that makes a

call to `isInSet` with our set as its first argument or _partially

apply_ the `isInSet` function.

[source,javascript]

----

var theSet = ["Carel Haverbeke", "Maria van Brussel",

"Donald Duck"];

function isInSet(set, person) {

return set.indexOf(person.name) > -1;

}

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

return isInSet(theSet, person);

}));

// → [{name: "Maria van Brussel", …},

// {name: "Carel Haverbeke", …}]

console.log(ancestry.filter(isInSet.bind(null, theSet)));

// → … same result

----

The call to `bind` returns a function that will call `isInSet` with

`theSet` as first argument, followed by any remaining arguments given

to the bound function.

(((null)))The first argument, where the example passes `null`, is used

for ((method call))s, similar to the first argument to `apply`. I'll

describe this in more detail in the

link:06_object.html#call_method[next chapter].

== Summary ==

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

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

write computations with “gaps” in them as functions and have the code

that calls these functions fill in those gaps by providing function

values that describe the missing computations.

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

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

array with some elements filtered out, `map` to build a new array

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

combine all an array's elements into a single value.

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

array specifying their arguments. They also have a `bind` method,

which is used to create a partially applied version of the function.

== Exercises ==

=== Flattening ===

(((flattening (exercise))))(((reduce method)))(((concat

method)))(((array)))Use the `reduce` method in combination with

the `concat` method to “flatten” an array of arrays into a single

array that has all the elements of the input arrays.

ifdef::interactive_target[]

// test: no

[source,javascript]

----

var arrays = [[1, 2, 3], [4, 5], [6]];

// Your code here.

// → [1, 2, 3, 4, 5, 6]

----

endif::interactive_target[]

=== Mother-child age difference ===

(((ancestry example)))(((age difference (exercise))))(((average

function)))Using the example data set from this chapter, compute the

average age difference between mothers and children (the age of the

mother when the child is born). You can use the `average` function

defined link:05_higher_order.html#average_function[earlier] in this

chapter.

(((byName object)))Note that not all the mothers mentioned in the data

are themselves present in the array. The `byName` object, which makes

it easy to find a person's object from their name, might be useful

here.

ifdef::interactive_target[]

// test: no

// include_code

[source,javascript]

----

function average(array) {

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

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

}

var byName = {};

ancestry.forEach(function(person) {

byName[person.name] = person;

});

// Your code here.

// → 31.2

----

endif::interactive_target[]

!!hint!!

(((age difference (exercise))))(((filter method)))(((map

method)))(((null)))(((average function)))Because not all elements in

the `ancestry` array produce useful data (we can't compute the age

difference unless we know the birth date of the mother), we will have

to apply `filter` in some manner before calling `average`. You could

do it as a first pass, by defining a `hasKnownMother` function and

filtering on that first. Alternatively, you could start by calling

`map` and in your mapping function return either the age difference

or `null` if no mother is known. Then, you can call `filter` to remove

the `null` elements before passing the array to `average`.

!!hint!!

=== Historical life expectancy ===

(((life expectancy (exercise))))When we looked up all the people in