Capítulo 4
Estructuras de Datos: Objetos y Arreglos

En dos ocasiones me han preguntado “Disculpe, Sr. Babbage, si introduce los números incorrectos en la máquina, ¿van a salir las respuestas correctas?” [...] No puedo terminar de comprender el tipo de confusión de ideas que podrían provocar esta pregunta.

Charles Babbage, Passages from the Life of a Philosopher (1864)

Números, Booleanos y cadenas son los ladrillos de los que están hechas las estructuras de datos. Pero no podrás construir mucha casa de un solo ladrillo. Los objetos nos permiten agrupar valores, incluyendo otros objetos, permitiéndonos construir estructuras más complejas.

Los programas que hemos construido hasta ahora han sido seriamente limitados debido al hecho de que estaban operando únicamente en tipos de datos simples. Este capítulo agregará a tu caja de herramientas un entendimiento básico de las estructuras de datos. Al finalizarlo, sabrás lo suficiente para empezar a escribir algunos programas de utilidad.

El capítulo trabajará a lo largo de un ejemplo de programación más o menos realista, introduciendo conceptos conforme apliquen al problema en cuestión. El código de ejemplo muchas veces construirá sobre funciones y variables que fueron presentadas previamente en el texto.

El hombre ardilla

De vez en cuando, comúnmente entre las ocho y las diez de la noche, Jacques se transforma en un pequeño y peludo roedor con una frondosa cola.

Por un lado, Jacques esta bastante contento de no tener la clásica licantropía. Convertirse en una ardilla suele causar menos problemas que convertirse en un lobo. En vez de tener que preocuparse por comerse accidentalmente a un vecino (eso sería penoso), le preocupa el ser deborado por el gato del vecino. Después de un par de ocasiones donde se despertó, en una delgada rama en la cima de un roble, desnudo y desorientado, se ha asegurado de cerrar puertas y ventanas de su cuarto por las noches y poner algunas bellotas en el suelo para mantenerse ocupado.

The weresquirrel

Eso resuelve los problemas del gato y el roble. Pero Jacques aún sufre de su enfermedad. Las ocurrencias irregulares de la transformación le hacen sospechar que pudieran ser detonadas por algo. Por algún tiempo, creyó que sucedía sólo en los dias que había tocado árboles. Así que dejó de tocar árboles de manera definitiva e incluso evitó acercarse a ellos. Pero el problema presistió.

Cambiando a una perspectiva más científica, Jacques intenta empezar un registro diario de todo lo que hizo ese día y si tuvo una transformación. Con estos datos espera limitar las condiciones que disparan las transformaciones.

Lo primero que hace es diseñar una estructura de datos para almacenar esta información.

Conjuntos de datos

Para trabajar con un pedazo de datos digitales, primero tendremos que encontrar una forma de representarlo en la memoria de nuestra máquina. Digamos, como un pequeño ejemplo, que queremos representar una colección de números: 2, 3, 5, 7 y 11.

Podríamos ponernos creativos usando cadenas; después de todo, las cadenas pueden ser de cualquier longitud, así que podemos poner mucha información en ellas; y usar "2 3 5 7 11" como nuestra representación. Pero esto es incómodo. De alguna forma tendrías que extraer los dígitos y convertirlos de vuelta a números para acceder a ellos.

Afortunadamente, Javascript proporciona un tipo de dato específico para almacenar secuencias de valores. Se le llama arreglo (array) y se escribe como una lista de valores entre corchetes, separados por comas.

var listaDeNumeros = [2, 3, 5, 7, 11];
console.log(listaDeNumeros[1]);
// → 3
console.log(listaDeNumeros[1 - 1]);
// → 2

La notación para obtener los elementos dentro de un arreglo también utiliza corchetes. Un par de corchetes inmediatamente después de una expresión, con otra expresión dentro de los corchetes, buscará el elemento en la expresión de la izquierda que corresponda al índice dado por la expresión en corchetes.

El primer índice de un arreglo es cero, no uno. Así que el primer elemento puede leerse usando listaDeNumeros[0]. Si no tienes antecedentes en programación, acostumbrarte a esta convención puede tomarte algún tiempo. Pero el conteo con base cero tiene una larga tradición en tecnología y mientras la convención se siga de manera consistente (que se ha hecho en Javascript), funciona bien.

Propiedades

Hemos visto algunas expresiones sospechosas como myString.length (para obtener la longitud de una cadena) y Math.max (la función máximo) en ejemplos pasados. Estas son expresiones que acceden una propiedad de algún valor. En el primer caso, accedemos a la propiedad length de el valor en myString. En el segundo, accedemos a la propiedad llamada max en el objeto Math (que es una colección de valores y funciones relacionadas con las matemáticas).

Casi todos los valores de JavaScript tienen propiedades. Las excepciones son null y undefined. Si intentas acceder una propiedad de alguno de estos valores inválidos recibirás un error.

null.length;
// → TypeError: Cannot read property 'length' of null

Las dos maneras comunes de acceder a propiedades en Javascript son con un punto y con corchetes. Ambas valor.x y valor[x] acceden a una propiedad en valor, pero no necesariamente la misma propiedad. La diferencia radica en cómo se interpreta x. Cuando usamos un punto, la parte después del punto debe ser un nombre de variable válido y nombra de manera directa a la propiedad. Cuando usamos corchetes, la expresión dentro de los corchetes es evaluada para obtener el nombre de la propiedad. Mientras que valor.x busca la propiedad de valor llamada “x”, valor[x] intenta evaluar la expresión x y usa el resultado como el nombre de la propiedad.

Así que si sabes que la propiedad que te interesa se llama “length”, usas valor.length. Si deseas extraer la propiedad nombrada por el valor almacenado en la variable i, usas valor[i]. Y debido a que el nombre de las propiedades puede ser cualquier cadena, si quieres accesar una propiedad llamada “2” o “Fulano”, debes utilizar corchetes:valor[2] or valor["Fulano de Tal"]. Así lo harías incluso si conoces el nombre preciso de la propiedad de antemano, ya que ni “2” ni “Fulano de Tal” son nombres válidos de variables y por lo tanto no puede accederse a traves de la notación con punto.

Los elementos en un arreglo se almacenan en propiedades. Debido a que los nombres de estas propiedades son números y usualmente necesitamos obtener su nombre de una variable, tenemos que usar la sintaxis de corchetes para accesarlos. La propiedad length (longitud) de un arreglo nos dice cuantos elementos contiene. Este nombre de propiedad es un nombre de variable válido, y conocemos su nombre por anticipado, así que para encontrar la longitud de un arreglo, comúnmente escribiremos arreglo.length ya que es más fácil de escribir que arreglo["length"].

Métodos

Ambos objetos, las cadenas y los arreglos contienen, adicionalmente a la propiedad length (longitud), varias propiedades que refieren a valores que son funciones.

var doh = "Doh";
console.log(typeof doh.toUpperCase);
// → function
console.log(doh.toUpperCase());
// → DOH

Todas las cadenas tienen una propiedad toUpperCase. Cuando es invocada, regresará una copia de la cadena en la que todas las letras han sido convertidas a mayúsculas. También existe toLowerCase. Puedes adivinar que es lo que hace.

Es interesante que, aunque la función toUpperCase no recibe ningún argumento, delaguna forma accede a la cadena "Doh", el valor en que se llamó la función. Esto funciona como se describe en el Capítulo 6.

Las propiedades que contienen funciones genralmente son llamadas métodos del valor al que pertenecen. Así, "toUpperCase es un método de una cadena".

Este ejemplo demuestra algunos métodos que los objetos arrays tienen:

var mack = [];
mack.push("Mack");
mack.push("the", "Knife");
console.log(mack);
// → ["Mack", "the", "Knife"]
console.log(mack.join(" "));
// → Mack the Knife
console.log(mack.pop());
// → Knife
console.log(mack);
// → ["Mack", "the"]

El método push puede ser usado para añadir valores al final de un array. El método pop hace lo contrario: elimina el valor al final del array y lo regresa. Un array de cadenas puede ser transformado a una sola cadena con el método join. El argumento que se da a join determina el texto que se usa entre los elementos del array.

Objetos

De regreso con el hombre ardilla. Un conjunto de entradas diaras de registro pueden ser representadas como un array. Pero las entradas no consisten de sólo un número o una cadena, cada entrada necesita guarda una lista de actividades y un valor Booleano que indica si Jacques se convirtió en ardilla. Idealmente, nos gustaría agrupar estos valores juntos en un solo valor y poner estos valores agrupados en un array de entradas del registro.

Los valores del tipo objeto son colecciones arbitrarias de propiedades, y podemos añadir o remover estas propiedades a placer. Una manera de crear un objeto es usando la notación de llaves.

var dia1 = {
  ardilla: false,
  eventos: ["trabajo", "toqué un arbol", "pizza", "correr",
           "televisión"]
};
console.log(dia1.ardilla);
// → false
console.log(dia1.lobo);
// → undefined
dia1.lobo = false;
console.log(dia1.lobo);
// → false

Dentro de las llaves, podemos dar una lista de propiedades separadas por comas. Cada propiedad está escritra como un nombre seguido por dos puntos, seguidos pos una expresión que le asigna el valor a esa propiedad. Los espacios y saltos de línea no son afectan. Cunado un objeto tiene múltiples líneas, indentarlas como en el ejemplo previo mejora la legibilidad. Las propiedades que tengan nombres que no sean nombres de variable válidos o números válidos tienen que estar entrecomilladas.

var descripciones = {
  trabajo: "Fui al trabajo",
  "toqué un arbol": "Toqué el arbol del vecino"
};

Esto significa que las llaves tienen dos significados en JavaScript. Al principio de una sentencia, empiezan un bloque de sentencia. En cualquier otra posición, describen un objeto. Afortunadamente, casi nunca es útil empezar una sentencia con un objeto declarado con llaves, y en programas típicos, no hay ambigüedad entre esos dos usos.

Al leer una propiedad que no existe se produce el valor undefined, es lo que pasa la primera vez que intentamos leer la propiedad lobo en el ejemplo previo.

Es posible asignar un valor a una expresión de propiedad con el operador =. Esto reemplazará el valor de la propiedad si ya existía o creará una nueva propiedad en el objeto si no.

Para regresar brevemente a nuestro modelo de tentáculos para asignaciones de variable, la asignación de propiedades es parecida. Estas agarran valores, pero otras variables y propiedades pudieran estar agarrando estos mismos valores. Puedes pensar que los objetos son pulpos con un número indefinido de tentáculos, cada uno de los cuales tiene un nombre escrito en él.

Representación de un objeto de un artista.

El operador delete le corta un tentáculo a este pulpo. Es un operador unario que, cuando es aplicado a una expresión de acceso a una propiedad, eliminará la propiedad nombrada del objeto. Esto no es algo que se haga comúnmente, pero es posible.

var unObjeto = {izq: 1, der: 2};
console.log(unObjeto.izq);
// → 1
delete unObjeto.izq;
console.log(unObjeto.izq);
// → undefined
console.log("izq" in unObjeto);
// → false
console.log("der" in unObjeto);
// → true

El operador binario in, cuando se aplica a una cadena y un objeto, devuelve un valor Booleano que indica si el objeto tiene esa propiedad. La diferencia entre asignarle undefined a una propiedad y borrarla de verdad es que, en el primer caso, el objeto aún tiene la propiedad (simplemente no tiene un valor muy interesante), mientras que en el segundo caso, la propiedad no está presente e in devolverá false.

Los arrays son solamente un tipo de objeto especializado en almacenar secuencias de cosas. Si evaluas typeof [1, 2], se prodcue "object". Puedes verlos como pulpos largos y planos con todos sus tentáculos en una fila limpia, etiquetados con números.

Artist's representation of an array

Así que podemos representar el diario de Jacques coomo un array de objetos.

var diario = [
  {eventos: ["trabajo", "tocar un arbol", "pizza",
            "correr", "televisión"],
   ardilla: false},
  {eventos: ["trabajo", "helado", "coliflor",
            "lasagna", "tocar un arbol", "lavarse los dientes"],
   ardilla: false},
  {eventos: ["fin de seamana", "bicicleta", "descanso",
            "cacahuates", "cerveza"],
   ardilla: true},
  /* y continúa... */
];

Mutabilidad

Nos meteremos en la programación de verdad pronto. Pero primero, hay una última pieza de teoría que entender.

Hemos visto que los valores objeto pueden ser modificados. Los tipos de valores de los que platicamos en capítulos anteriores, como números, cadenas, Booleanos son todos inmutables; es imposible cambiar un valor existente de esos tipos. Puedes combinarlos y derivar nuevos valores de ellos, pero cuando tomas un valor cadena específico, ese valor siempre permanecerá igual. El texto que está adentro no puede ser cambiado. Si tienes una referencia a una cadena que contiene "cat", no se posible para el código cambiar un caráctes en esa cadena para hacerlo decir "rat".

Con los objeto, por otro lado, el contenido de un valor puede ser modificado al cambiar sus propiedades.

Cuando tenemos dos números,, 120 y 120, podemos considerar que son precisamente el mismo número independientemente si se refieren o no a los mismos bits físicos. Pero con los objetos, hay una diferencia entre tener la dos referencias al mismo objeto y tener dos objetos que contienen las mismas propiedades. Considera el siguiente código:

var objeto1 = {valor: 10};
var objeto2 = objeto1;
var objeto3 = {valor: 10};

console.log(objeto1 == objeto2);
// → true
console.log(objeto1 == objeto3);
// → false

objeto1.valor = 15;
console.log(objeto2.valor);
// → 15
console.log(objeto3.valor);
// → 10

Las variables objeto1 y objeto2 agarran el mismo objeto, ésta es la razón de que al cambiar objeto1 también se cambia el valor del objeto2. La variable objeto3 apunta a un objeto diferente, que inicialmente contiene las mismas propiedades que el objeto1 pero vive una vida separada.

El operador == de JavaScript, cuando compara objetos regresará true sólo si los dos objetos son precisamente el mismo valor. Comparar diferentes objetos regresará false, incluso si tienen contenidos idénticos. No existe comparación "profunda" construida en JavaScript, la cual se basa en el contenido de los objetos, pero puedes escribirla tú mismo (que será uno de los ejercicios al final de este capítulo).

El registro del licántropo

Así, Jacques inicia su intérprete de JavaScript y configura el entorno que necesita para llevar su diario.

var diario = [];

function agregarEntrada(eventos, meVolviArdilla) {
  diario.push({
    eventos: eventos,
    ardilla: meVolviArdilla
  });
}

Y después, cada noche a las 10, o algunas veces la mañana siguiente, después de haber bajado de la parte superior de su librero, registra el día.

agregarEntrada(["trabajo", "toqué un árbol", "pizza", "correr",
          "televisión"], false);
agregarEntrada(["trabajo", "helado", "coliflor", "lasagna",
          "toqué un árbol", "me lavé los dientes"], false);
agregarEntrada(["fin de semana", "bicicleta", "descanso", "cacachuates",
          "cerveza"], true);

Una vez que tiene suficientes datos, quiere calcular la correlación entre su ardillamiento y cada uno de los eventos e, idealmente, aprender algo útil de esas correlaciones.

La Correlación es una medida de dependencia entre variables (“variables” en el sentido de la estadística, no en el de JavaScript). Es expresada usualmente como un coeficiente que va del -1 al 1. Una correlación de 0 significa que las variables no están relacionadas, mientras que una correlación de uno indica que están perfectamente relacionadas: si conoces una, entonces conoces la otra. El uno negativo también significa que están perfectamente relacionadas pero que son opuestas, cuando una es verdadera, la otra es falsa.

Para variables binarias (Booleanas), el coeficiente phi (ϕ) da una buena medida de correlación y es relativamente fácil de calcular. Para calcular ϕ necesitamos una tabla n que contine el número de veces que varias combinaciones de variables fueron observadas. Por ejemplo, podríamos tomar el evento de comer pizza y ponerlo en la tabla de la siguiente manera:

Comer pizza vs convertirse en ardilla.

ϕ puede ser calculado usando la siguiente fórmula, en donde n se refiere a la tabla:

ϕ =
n11n00 - n10n01
n1•n0•n•1n•0

La notación n01 indica el número de medidas en el que la primer vairiable (ardillificación) es falsa (0) y la segunda variable (pizza) es verdadera (1). En este ejemplo, n01 es 9.

El valor n1• se refiere a la suma de todas las medidas en donde la primera variable es verdadera, que es 5 en la tabla de ejemplo. De la misma manera, n•0 se refiere a la suma de medidas en donde la segunda variable es falsa.

Así que para la tabla de la pizza, la parte de arriba de la línea de división (el dividendo) sería 1×76 - 4×9 = 40, y la parte de debajo de la línea (el divisor) sería la raíz cuadrada de 5×85×10×80, o √340000. Esto da como resultado ϕ ≈ 0.069, que es muy pequeño. Comer pizza no parece tener influencia en las transformaciones.

Calculando correlaciones

Podemos representar una tabla de dos por dos en JavaScript con un array de 4 elementos ([76, 9, 4, 1]). Podríamos también usar otras representaciones, como un array que contenga dos arrays de dos elementos cada uno ([[76, 9], [4, 1]]) o como un objeto con nombre de propiedades como "11" y "01", pero el array plano es simple y hace que las expresiones de acceso a la tabla sean convenientemente cortas. Interpretaremos los índices del array como un número binario de dos bits, en donde el dígito más a la izquierda (el más siginificativo) se refiere a la variable de la ardilla y el más a la derecha (menos significativo) se refiere a la variable del evento. Por ejemplo, el número binario 10 se refiere al caso en que Jacques se convirtió en ardilla, pero el evento (digamos, "pizza"), no ocurrió. Esto pasó 4 veces. Y como el binario 10 es 2 en notación decimal, guardaremos ese número en el índice 2 del array.

Esta es la función que calcula el coeficiente ϕ del ese array:

function phi(tabla) {
  return (tabla[3] * tabla[0] - tabla[2] * tabla[1]) /
    Math.sqrt((tabla[2] + tabla[3]) *
              (tabla[0] + tabla[1]) *
              (tabla[1] + tabla[3]) *
              (tabla[0] + tabla[2]));
}

console.log(phi([76, 9, 4, 1]));
// → 0.068599434

Esto es simplemente una traducción directa de la fómula de la ϕ a JavaScript. Math.sqrt es la función raíz cuadrada, provista por el objeto Math en un entorno de JavaScript estándar. Tenemos que sumar los dos campos de la tabla para obtener campos como n1• porque la suma de las filas o columnas no están guardadas directamente en nuestra estructura de datos.

Jacques mantuvo su diario por tres meses. El set de datos resultante está disponible en el área de código para este capítulo, en donde está guardada la variable DIARIO, y como descarga en file.

Para extraer una tabla de 2 x 2 po un evento específico de este diario, tenemos que iterar sobre todas las entradas y contar cuántas veces el evento ocurre en relación con las transformaciones a ardilla.

function tieneEvento(evento, entrada) {
  return entrada.eventos.indexOf(evento) != -1;
}

function tablaPara(evento, diario) {
  var tabla = [0, 0, 0, 0];
  for (var i = 0; i < diario.length; i++) {
    var entrada = diario[i], index = 0;
    if (tieneEvento(evento, entrada)) index += 1;
    if (entrada.ardilla) index += 2;
    tabla[index] += 1;
  }
  return tabla;
}

console.log(tabalaPara("pizza", DIARIO));
// → [76, 9, 4, 1]

La función tieneEvento verifica si una entrada tiene una entrada dada. Los arrays tienen un método indexOf que intenta encontrar un valor dado (en este caso, el nombre del evento) en el array y regresan el índice en el cuál fue encontrado o -1 si no se encontró. Así que si la llamada a indexOf no regresa -1, entonces sabemos que el evento fue encontrado en la entrada.

El cuerpo del loop en tablaPara encuentra en qué celda de la tabla cae cada entrada del diario mediante verificar si la entrada contiene el evento que está buscando y si el evento ocurre junto con un incidente de ardilla. Entonces, el loop agrega uno al número en el array que corresponde con esta categoría en la tabla.

Ahora tenemos las herramientas que necesitamos para calcular las correlaciones individuales. El único paso que queda es encontrar la correlación para cada tipo de evento registrado y ver si algo sobresale. Pero, ¿cómo debereiamos guardar esas correlaciones una vez que las calculamos?

Objetos como mapas

Una camino posible es guardar todas las correlaciones en un array, usando objetos con propiedades nombre y valor. Pero eso hace que buscar la correlación por un evnto dado sea un poco difícil: tienes que iterar sobre el array completo para buscar el objeto con el nombre correcto. Podemos poner este código en una función, pero seguiríamos escribiendo más código, y la computadora estaría haciendo más trabajo del necesario.

Una mejor forma es usar propiedades de un objeto nombradas como los tipos de eventos. Podemos usar la notación de acceso de corchetes (paréntesis cuadrados) para crear y leer las propiedades y el operador in para verificar si una propiedad existe.

var mapa = {};
function guardarPhi(evento, phi) {
  mapa[evento] = phi;
}

guardarPhi("pizza", 0.069);
guardarPhi("toqué un árbol", -0.081);
console.log("pizza" in mapa);
// → true
console.log(mapa["touched tree"]);
// → -0.081

Un mapa es una manera de ir de valores en un dominio (en este caso nombres de eventos) a valores correspondientes en otro dominio (en este caso coeficientes ϕ).

Existen algunos problemas potenciales al usar objetos como este, que discutiremos en el Capítulo 6, pero por ahora, no nos preocupemos de eso.

¿Y si queremos hallar todos los eventos para los que tenemos guardados un coeficiente? Las propiedades no forman una serie predecible, como lo harían en un array, así que no podemos usar un for normal. JavaScript tiene un construcción iterativa específicamente para funcionar sobre las propiedades de un objeto. Luce un poco como un loop for normal pero se distingue por el uso de la palabra in.

for (var evento in mapa)
  console.log("La correlación para '" + evento +
              "' es " + mapa[evento]);
// → La correlación para 'pizza' is 0.069
// → La correlación para 'toqué un arbol' es -0.081

Para encontrar todos los tipos de eventos que están presentes en el set de datos, simplemente procesamos cada entrada en turno y después iteramos en los eventos de esa entrada. Mantenemos un objeto phis que tiene los coeficientes de correlación para todos los tipos de eventos que hemos visto hasta ahora. Cuando encontramos un tipo de evento que no está en el objeto phis todavía, calculamos la correlación y la añadimos al objeto.

function juntarCorrelaciones(diario) {
  var phis = {};
  for (var entrada = 0; entrada < diario.length; entrada++) {
    var eventos = diario[entrada].eventos;
    for (var i = 0; i < eventos.length; i++) {
      var evento = eventos[i];
      if (!(evento in phis))
        phis[evento] = phi(tablaPara(evento, diario));
    }
  }
  return phis;
}

var correlaciones = juntarCorrelaciones(DIARIO);
console.log(correlaciones.pizza);
// → 0.068599434

Veamos lo que resulta.

for (var eventos in correlaciones)
  console.log(eventos + ": " + correlaciones[eventos]);
// → zanahoria:   0.0140970969
// → ejercicio: 0.0685994341
// → fin de semana:  0.1371988681
// → pan:   -0.0757554019
// → pudding: -0.0648203724
// y así...

La mayoría de las correlaciones están cerca de cero. Comer zanahorias, pan o pudding aparentemente no desencadenan la licantropía de la ardilla. Sin embargo, parece que ocurre más frecuentemente los fines de semana de alguna manera. Filtremos los resultados para mostrar sólo las correlaciones mayores que 0.1 o menores que -0.1.

for (var event in correlations) {
  var correlation = correlations[event];
  if (correlation > 0.1 || correlation < -0.1)
    console.log(event + ": " + correlation);
}
// → weekend:        0.1371988681
// → brushed teeth: -0.3805211953
// → candy:          0.1296407447
// → work:          -0.1371988681
// → spaghetti:      0.2425356250
// → reading:        0.1106828054
// → peanuts:        0.5902679812

A-ha! There are two factors whose correlation is clearly stronger than the others. Eating peanuts has a strong positive effect on the chance of turning into a squirrel, whereas brushing his teeth has a significant negative effect.

Interesting. Let’s try something.

for (var i = 0; i < JOURNAL.length; i++) {
  var entrada = JOURNAL[i];
  if (hasEvent("peanuts", entrada) &&
     !hasEvent("brushed teeth", entrada))
    entrada.events.push("peanut teeth");
}
console.log(phi(tableFor("peanut teeth", JOURNAL)));
// → 1

Well, that’s unmistakable! The phenomenon occurs precisely when Jacques eats peanuts and fails to brush his teeth. If only he weren’t such a slob about dental hygiene, he’d have never even noticed his affliction.

Knowing this, Jacques simply stops eating peanuts altogether and finds that this completely puts an end to his transformations.

All is well with Jacques for a while. But a few years later, he loses his job and is eventually forced to take employment with a circus, where he performs as The Incredible Squirrelman by stuffing his mouth with peanut butter before every show. One day, fed up with this pitiful existence, Jacques fails to change back into his human form, hops through a crack in the circus tent, and vanishes into the forest. He is never seen again.

Further arrayology

Before finishing up this chapter, I want to introduce you to a few more object-related concepts. We’ll start by introducing some generally useful array methods.

We saw push and pop, which add and remove elements at the end of an array, earlier in this chapter. The corresponding methods for adding and removing things at the start of an array are called unshift and shift.

var todoList = [];
function rememberTo(task) {
  todoList.push(task);
}
function whatIsNext() {
  return todoList.shift();
}
function urgentlyRememberTo(task) {
  todoList.unshift(task);
}

The previous program manages lists of tasks. You add tasks to the end of the list by calling rememberTo("eat"), and when you’re ready to do something, you call whatIsNext() to get (and remove) the front item from the list. The urgentlyRememberTo function also adds a task but adds it to the front instead of the back of the list.

The indexOf method has a sibling called lastIndexOf, which starts searching for the given element at the end of the array instead of the front.

console.log([1, 2, 3, 2, 1].indexOf(2));
// → 1
console.log([1, 2, 3, 2, 1].lastIndexOf(2));
// → 3

Both indexOf and lastIndexOf take an optional second argument that indicates where to start searching from.

Another fundamental method is slice, which takes a start index and an end index and returns an array that has only the elements between those indices. The start index is inclusive, the end index exclusive.

console.log([0, 1, 2, 3, 4].slice(2, 4));
// → [2, 3]
console.log([0, 1, 2, 3, 4].slice(2));
// → [2, 3, 4]

When the end index is not given, slice will take all of the elements after the start index. Strings also have a slice method, which has a similar effect.

The concat method can be used to glue arrays together, similar to what the + operator does for strings. The following example shows both concat and slice in action. It takes an array and an index, and it returns a new array that is a copy of the original array with the element at the given index removed.

function remove(array, index) {
  return array.slice(0, index)
    .concat(array.slice(index + 1));
}
console.log(remove(["a", "b", "c", "d", "e"], 2));
// → ["a", "b", "d", "e"]

Strings and their properties

We can read properties like length and toUpperCase from string values. But if you try to add a new property, it doesn’t stick.

var myString = "Fido";
myString.myProperty = "value";
console.log(myString.myProperty);
// → undefined

Values of type string, number, and Boolean are not objects, and though the language doesn’t complain if you try to set new properties on them, it doesn’t actually store those properties. The values are immutable and cannot be changed.

But these types do have some built-in properties. Every string value has a number of methods. The most useful ones are probably slice and indexOf, which resemble the array methods of the same name.

console.log("coconuts".slice(4, 7));
// → nut
console.log("coconut".indexOf("u"));
// → 5

One difference is that a string’s indexOf can take a string containing more than one character, whereas the corresponding array method looks only for a single element.

console.log("one two three".indexOf("ee"));
// → 11

The trim method removes whitespace (spaces, newlines, tabs, and similar characters) from the start and end of a string.

console.log("  okay \n ".trim());
// → okay

We have already seen the string type’s length property. Accessing the individual characters in a string can be done with the charAt method but also by simply reading numeric properties, like you’d do for an array.

var string = "abc";
console.log(string.length);
// → 3
console.log(string.charAt(0));
// → a
console.log(string[1]);
// → b

The arguments object

Whenever a function is called, a special variable named arguments is added to the environment in which the function body runs. This variable refers to an object that holds all of the arguments passed to the function. Remember that in JavaScript you are allowed to pass more (or fewer) arguments to a function than the number of parameters the function itself declares.

function noArguments() {}
noArguments(1, 2, 3); // This is okay
function threeArguments(a, b, c) {}
threeArguments(); // And so is this

The arguments object has a length property that tells us the number of arguments that were really passed to the function. It also has a property for each argument, named 0, 1, 2, and so on.

If that sounds a lot like an array to you, you’re right, it is a lot like an array. But this object, unfortunately, does not have any array methods (like slice or indexOf), so it is a little harder to use than a real array.

function argumentCounter() {
  console.log("You gave me", arguments.length, "arguments.");
}
argumentCounter("Straw man", "Tautology", "Ad hominem");
// → You gave me 3 arguments.

Some functions can take any number of arguments, like console.log. These typically loop over the values in their arguments object. They can be used to create very pleasant interfaces. For example, remember how we created the entries to Jacques’ journal.

addEntry(["work", "touched tree", "pizza", "correr",
          "television"], false);

Since he is going to be calling this function a lot, we could create an alternative that is easier to call.

function addEntry(squirrel) {
  var entry = {events: [], squirrel: squirrel};
  for (var i = 1; i < arguments.length; i++)
    entry.events.push(arguments[i]);
  journal.push(entry);
}
addEntry(true, "work", "touched tree", "pizza",
         "running", "television");

This version reads its first argument (squirrel) in the normal way and then goes over the rest of the arguments (the loop starts at index 1, skipping the first) to gather them into an array.

The Math object

As we’ve seen, Math is a grab-bag of number-related utility functions, such as Math.max (maximum), Math.min (minimum), and Math.sqrt (square root).

The Math object is used simply as a container to group a bunch of related functionality. There is only one Math object, and it is almost never useful as a value. Rather, it provides a namespace so that all these functions and values do not have to be global variables.

Having too many global variables “pollutes” the namespace. The more names that have been taken, the more likely you are to accidentally overwrite the value of some variable. For example, it’s not unlikely that you’ll want to name something max in one of your programs. Since JavaScript’s built-in max function is tucked safely inside the Math object, we don’t have to worry about overwriting it.

Many languages will stop you, or at least warn you, when you are defining a variable with a name that is already taken. JavaScript does neither, so be careful.

Back to the Math object. If you need to do trigonometry, Math can help. It contains cos (cosine), sin (sine), and tan (tangent), as well as their inverse functions, acos, asin, and atan, respectively. The number π (pi)—or at least the closest approximation that fits in a JavaScript number—is available as Math.PI. (There is an old programming tradition of writing the names of constant values in all caps.)

function randomPointOnCircle(radius) {
  var angle = Math.random() * 2 * Math.PI;
  return {x: radius * Math.cos(angle),
          y: radius * Math.sin(angle)};
}
console.log(randomPointOnCircle(2));
// → {x: 0.3667, y: 1.966}

If sines and cosines are not something you are very familiar with, don’t worry. When they are used in this book, in Chapter 13, I’ll explain them.

The previous example uses Math.random. This is a function that returns a new pseudorandom number between zero (inclusive) and one (exclusive) every time you call it.

console.log(Math.random());
// → 0.36993729369714856
console.log(Math.random());
// → 0.727367032552138
console.log(Math.random());
// → 0.40180766698904335

Though computers are deterministic machines—they always react the same way if given the same input—it is possible to have them produce numbers that appear random. To do this, the machine keeps a number (or a bunch of numbers) in its internal state. Then, every time a random number is requested, it performs some complicated deterministic computations on this internal state and returns part of the result of those computations. The machine also uses the outcome to change its own internal state so that the next “random” number produced will be different.

If we want a whole random number instead of a fractional one, we can use Math.floor (which rounds down to the nearest whole number) on the result of Math.random.

console.log(Math.floor(Math.random() * 10));
// → 2

Multiplying the random number by 10 gives us a number greater than or equal to zero, and below 10. Since Math.floor rounds down, this expression will produce, with equal chance, any number from 0 through 9.

There are also the functions Math.ceil (for “ceiling”, which rounds up to a whole number) and Math.round (to the nearest whole number).

The global object

The global scope, the space in which global variables live, can also be approached as an object in JavaScript. Each global variable is present as a property of this object. In browsers, the global scope object is stored in the window variable.

var myVar = 10;
console.log("myVar" in window);
// → true
console.log(window.myVar);
// → 10

Summary

Objects and arrays (which are a specific kind of object) provide ways to group several values into a single value. Conceptually, this allows us to put a bunch of related things in a bag and run around with the bag, instead of trying to wrap our arms around all of the individual things and trying to hold on to them separately.

Most values in JavaScript have properties, the exceptions being null and undefined. Properties are accessed using value.propName or value["propName"]. Objects tend to use names for their properties and store more or less a fixed set of them. Arrays, on the other hand, usually contain varying numbers of conceptually identical values and use numbers (starting from 0) as the names of their properties.

There are some named properties in arrays, such as length and a number of methods. Methods are functions that live in properties and (usually) act on the value they are a property of.

Objects can also serve as maps, associating values with names. The in operator can be used to find out whether an object contains a property with a given name. The same keyword can also be used in a for loop (for (var name in object)) to loop over an object’s properties.

Exercises

The sum of a range

The introduction of this book alluded to the following as a nice way to compute the sum of a range of numbers:

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

Write a range function that takes two arguments, start and end, and returns an array containing all the numbers from start up to (and including) end.

Next, write a sum function that takes an array of numbers and returns the sum of these numbers. Run the previous program and see whether it does indeed return 55.

As a bonus assignment, modify your range function to take an optional third argument that indicates the “step” value used to build up the array. If no step is given, the array elements go up by increments of one, corresponding to the old behavior. The function call range(1, 10, 2) should return [1, 3, 5, 7, 9]. Make sure it also works with negative step values so that range(5, 2, -1) produces [5, 4, 3, 2].

// Your code here.

console.log(range(1, 10));
// → [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
console.log(range(5, 2, -1));
// → [5, 4, 3, 2]
console.log(sum(range(1, 10)));
// → 55

Building up an array is most easily done by first initializing a variable to [] (a fresh, empty array) and repeatedly calling its push method to add a value. Don’t forget to return the array at the end of the function.

Since the end boundary is inclusive, you’ll need to use the <= operator rather than simply < to check for the end of your loop.

To check whether the optional step argument was given, either check arguments.length or compare the value of the argument to undefined. If it wasn’t given, simply set it to its default value (1) at the top of the function.

Having range understand negative step values is probably best done by writing two separate loops—one for counting up and one for counting down—because the comparison that checks whether the loop is finished needs to be >= rather than <= when counting downward.

It might also be worthwhile to use a different default step, namely, -1, when the end of the range is smaller than the start. That way, range(5, 2) returns something meaningful, rather than getting stuck in an infinite loop.

Reversing an array

Arrays have a method reverse, which changes the array by inverting the order in which its elements appear. For this exercise, write two functions, reverseArray and reverseArrayInPlace. The first, reverseArray, takes an array as argument and produces a new array that has the same elements in the inverse order. The second, reverseArrayInPlace, does what the reverse method does: it modifies the array given as argument in order to reverse its elements. Neither may use the standard reverse method.

Thinking back to the notes about side effects and pure functions in the previous chapter, which variant do you expect to be useful in more situations? Which one is more efficient?

// Your code here.

console.log(reverseArray(["A", "B", "C"]));
// → ["C", "B", "A"];
var arrayValue = [1, 2, 3, 4, 5];
reverseArrayInPlace(arrayValue);
console.log(arrayValue);
// → [5, 4, 3, 2, 1]

There are two obvious ways to implement reverseArray. The first is to simply go over the input array from front to back and use the unshift method on the new array to insert each element at its start. The second is to loop over the input array backward and use the push method. Iterating over an array backward requires a (somewhat awkward) for specification like (var i = array.length - 1; i >= 0; i--).

Reversing the array in place is harder. You have to be careful not to overwrite elements that you will later need. Using reverseArray or otherwise copying the whole array (array.slice(0) is a good way to copy an array) works but is cheating.

The trick is to swap the first and last elements, then the second and second-to-last, and so on. You can do this by looping over half the length of the array (use Math.floor to round down—you don’t need to touch the middle element in an array with an odd length) and swapping the element at position i with the one at position array.length - 1 - i. You can use a local variable to briefly hold on to one of the elements, overwrite that one with its mirror image, and then put the value from the local variable in the place where the mirror image used to be.

A list

Objects, as generic blobs of values, can be used to build all sorts of data structures. A common data structure is the list (not to be confused with the array). A list is a nested set of objects, with the first object holding a reference to the second, the second to the third, and so on.

var list = {
  value: 1,
  rest: {
    value: 2,
    rest: {
      value: 3,
      rest: null
    }
  }
};

The resulting objects form a chain, like this:

A linked list

A nice thing about lists is that they can share parts of their structure. For example, if I create two new values {value: 0, rest: list} and {value: -1, rest: list} (with list referring to the variable defined earlier), they are both independent lists, but they share the structure that makes up their last three elements. In addition, the original list is also still a valid three-element list.

Write a function arrayToList that builds up a data structure like the previous one when given [1, 2, 3] as argument, and write a listToArray function that produces an array from a list. Also write the helper functions prepend, which takes an element and a list and creates a new list that adds the element to the front of the input list, and nth, which takes a list and a number and returns the element at the given position in the list, or undefined when there is no such element.

If you haven’t already, also write a recursive version of nth.

// Your code here.

console.log(arrayToList([10, 20]));
// → {value: 10, rest: {value: 20, rest: null}}
console.log(listToArray(arrayToList([10, 20, 30])));
// → [10, 20, 30]
console.log(prepend(10, prepend(20, null)));
// → {value: 10, rest: {value: 20, rest: null}}
console.log(nth(arrayToList([10, 20, 30]), 1));
// → 20

Building up a list is best done back to front. So arrayToList could iterate over the array backward (see previous exercise) and, for each element, add an object to the list. You can use a local variable to hold the part of the list that was built so far and use a pattern like list = {value: X, rest: list} to add an element.

To run over a list (in listToArray and nth), a for loop specification like this can be used:

for (var node = list; node; node = node.rest) {}

Can you see how that works? Every iteration of the loop, node points to the current sublist, and the body can read its value property to get the current element. At the end of an iteration, node moves to the next sublist. When that is null, we have reached the end of the list and the loop is finished.

The recursive version of nth will, similarly, look at an ever smaller part of the “tail” of the list and at the same time count down the index until it reaches zero, at which point it can return the value property of the node it is looking at. To get the zeroeth element of a list, you simply take the value property of its head node. To get element N + 1, you take the Nth element of the list that’s in this list’s rest property.

Deep comparison

The == operator compares objects by identity. But sometimes, you would prefer to compare the values of their actual properties.

Write a function, deepEqual, that takes two values and returns true only if they are the same value or are objects with the same properties whose values are also equal when compared with a recursive call to deepEqual.

To find out whether to compare two things by identity (use the === operator for that) or by looking at their properties, you can use the typeof operator. If it produces "object" for both values, you should do a deep comparison. But you have to take one silly exception into account: by a historical accident, typeof null also produces "object".

// Your code here.

var obj = {here: {is: "an"}, object: 2};
console.log(deepEqual(obj, obj));
// → true
console.log(deepEqual(obj, {here: 1, object: 2}));
// → false
console.log(deepEqual(obj, {here: {is: "an"}, object: 2}));
// → true

Your test for whether you are dealing with a real object will look something like typeof x == "object" && x != null. Be careful to compare properties only when both arguments are objects. In all other cases you can just immediately return the result of applying ===.

Use a for/in loop to go over the properties. You need to test whether both objects have the same set of property names and whether those properties have identical values. The first test can be done by counting the properties in both objects and returning false if the numbers of properties are different. If they’re the same, then go over the properties of one object, and for each of them, verify that the other object also has the property. The values of the properties are compared by a recursive call to deepEqual.

Returning the correct value from the function is best done by immediately returning false when a mismatch is noticed and returning true at the end of the function.