04_data.txt

:chap_num: 4
:prev_link: 03_functions
:next_link: 05_higher_order
:load_files: ["code/jacques_journal.js", "code/chapter/04_data.js"]
:zip: node/html

= Data Structures: Objects and Arrays =

[chapterquote="true"]
[quote, Charles Babbage, Passages from the Life of a Philosopher (1864)]
____
On two occasions I have been asked, ‘Pray,
Mr. Babbage, if you put into the machine wrong figures, will the right
answers come out?’ [...] I am not able rightly to apprehend the kind
of confusion of ideas that could provoke such a question.
____

(((Babbage+++,+++ Charles)))(((object)))(((data structure)))Numbers, Booleans, and strings are the
bricks that ((data)) structures are built from. But you can't make
much of a house out of a single brick. _Objects_ allow us to group
values—including other objects—together and thus build more complex
structures.

The programs we have built so far have been seriously hampered by the
fact that they were operating only on simple data types. This chapter
will add a basic understanding of data structures to your toolkit. By
the end of it, you'll know enough to start writing some useful
programs.

The chapter will work through a more or less realistic programming
example, introducing concepts as they apply to the problem at hand.
The example code will often build on functions and variables that were
introduced earlier in the text.

ifdef::book_target[]

(((sandbox)))The online coding sandbox for the book
(http://eloquentjavascript.net/code[_eloquentjavascript.net/code_])
provides a way to run code in the context of a specific chapter. If
you decide to work through the examples in another environment, be
sure to first download the full code for this chapter from the
sandbox page.

endif::book_target[]

== The weresquirrel ==

(((weresquirrel example)))(((lycanthropy)))Every now and then, usually
between eight and ten in the evening, ((Jacques)) finds himself
transforming into a small furry rodent with a bushy tail.

On one hand, Jacques is quite glad that he doesn't have classic
lycanthropy. Turning into a squirrel tends to cause fewer problems
than turning into a wolf. Instead of having to worry about
accidentally eating the neighbor (_that_ would be awkward), he worries
about being eaten by the neighbor's cat. After two occasions where he
woke up on a precariously thin branch in the crown of an oak, naked
and disoriented, he has taken to locking the doors and windows of his
room at night and putting a few walnuts on the floor to keep himself
busy.

image::img/weresquirrel.png[alt="The weresquirrel"]

That takes care of the cat and oak problems. But Jacques still suffers
from his condition. The irregular occurrences of the transformation
make him suspect that they might be triggered by something.
For a while, he believed that it happened only on days when he
had touched trees. So he stopped touching trees entirely and even
avoided going near them. But the problem persisted.

(((journal)))Switching to a more scientific approach, Jacques intends
to start keeping a daily log of everything he did that day and whether
he changed form. With this data he hopes to narrow down the conditions
that trigger the transformations.

The first thing he does is design a data structure to store this
information.

== Data sets ==

(((data structure)))To work with a chunk of digital data, we'll first
have to find a way to represent it in our machine's ((memory)). Say,
as a simple example, that we want to represent a ((collection)) of
numbers: 2, 3, 5, 7, and 11.

(((string)))We could get creative with strings—after all, strings
can be any length, so we can put a lot of data into them—and use `"2 3
5 7 11"` as our representation. But this is awkward. You'd have to
somehow extract the digits and convert them back to numbers to access
them.

(((array,creation)))((([] (array))))Fortunately, JavaScript
provides a data type specifically for storing sequences of values. It
is called an _array_ and is written as a list of values between
((square brackets)), separated by commas.

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

((([] (subscript))))(((array,indexing)))The notation for getting
at the elements inside an array also uses ((square brackets)). A pair
of square brackets immediately after an expression, with another
expression inside of them, will look up the element in the left-hand
expression that corresponds to the _((index))_ given by the expression
in the brackets.

[[array_indexing]]
The first index of an array is zero, not one. So the first element can
be read with `listOfNumbers[0]`. If you don't have a programming
background, this convention might take some getting used to. But
((zero-based counting)) has a long tradition in technology, and as
long as this convention is followed consistently (which it is, in
JavaScript), it works well.

[[properties]]
== Properties ==

(((Math object)))(((Math.max function)))(((length property,for
string)))(((object,property)))(((period character)))We've seen a few
suspicious-looking expressions like `myString.length` (to get the
length of a string) and `Math.max` (the maximum function) in past
examples. These are expressions that access a _((property))_ of some
value. In the first case, we access the `length` property of the value
in `myString`. In the second, we access the property named `max` in
the `Math` object (which is a collection of mathematics-related values
and functions).

(((property)))(((null)))(((undefined)))Almost all JavaScript values
have properties. The exceptions are `null` and `undefined`. If you try
to access a property on one of these nonvalues, you get an error.

// test: no

[source,javascript]
----
null.length;
// → TypeError: Cannot read property 'length' of null
----

indexsee:[dot character,period character]
((([] (subscript))))(((period character)))(((square
brackets)))(((computed property)))The two most common ways to access
properties in JavaScript are with a dot and with square brackets. Both
`value.x` and `value[x]` access a ((property)) on ++value++—but not
necessarily the same property. The difference is in how `x` is
interpreted. When using a dot, the part after the dot must be a valid
variable name, and it directly names the property. When using square
brackets, the expression between the brackets is _evaluated_ to get
the property name. Whereas `value.x` fetches the property of `value`
named “x”, `value[x]` tries to evaluate the expression `x` and uses
the result as the property name.

So if you know that the property you are interested in is called
“length”, you say `value.length`. If you want to extract the property
named by the value held in the variable `i`, you say `value[i]`. And
because property names can be any string, if you want to access a
property named “2” or “John Doe”, you must use square brackets:
`value[2]` or `value["John Doe"]`. This is the case even though you
know the precise name of the property in advance, because neither “2”
nor “John Doe” is a valid variable name and so cannot be accessed
through dot notation.

(((array)))(((length property,for array)))(((array,length
of)))The elements in an array are stored in properties. Because the
names of these properties are numbers and we often need to get their
name from a variable, we have to use the bracket syntax to access
them. The `length` property of an array tells us how many elements it
contains. This property name is a valid variable name, and we know its
name in advance, so to find the length of an array, you typically
write `array.length` because that is easier to write than
`array["length"]`.

[[methods]]
== Methods ==

(((function,as property)))(((method)))(((string)))Both string and
array objects contain, in addition to the `length` property, a number
of properties that refer to function values.

[source,javascript]
----
var doh = "Doh";
console.log(typeof doh.toUpperCase);
// → function
console.log(doh.toUpperCase());
// → DOH
----

(((case conversion)))(((toUpperCase method)))(((toLowerCase
method)))Every string has a `toUpperCase` property. When called, it
will return a copy of the string, in which all letters have been
converted to uppercase. There is also `toLowerCase`. You can guess
what that does.

(((this)))Interestingly, even though the call to `toUpperCase` does
not pass any arguments, the function somehow has access to the string
`"Doh"`, the value whose property we called. How this works is
described in link:06_object.html#obj_methods[Chapter 6].

Properties that contain functions are generally called _methods_ of
the value they belong to. As in, “++toUpperCase++ is a method of a
string”.

[[array_methods]]
(((collection)))(((array)))(((string)))(((push
method)))(((pop method)))(((join method)))This example demonstrates
some methods that array objects have:

[source,javascript]
----
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"]
----

The `push` method can be used to add values to the end of an array.
The `pop` method does the opposite: it removes the value at the end of
the array and returns it. An array of strings can be flattened to a
single string with the `join` method. The argument given to `join`
determines the text that is glued between the array's elements.

== Objects ==

(((journal)))(((weresquirrel example)))(((array)))(((record)))Back to the weresquirrel. A set of daily log
entries can be represented as an array. But the entries do not consist
of just a number or a string—each entry needs to store a list of
activities and a Boolean value that indicates whether Jacques turned
into a squirrel. Ideally, we would like to group these values together
into a single value and then put these grouped values into an array of
log entries.

(((syntax)))(((object)))(((property)))(((curly braces)))((({}
(object))))Values of the type _object_ are arbitrary collections of
properties, and we can add or remove these properties as we please.
One way to create an object is by using a curly brace notation.

[source,javascript]
----
var day1 = {
  squirrel: false,
  events: ["work", "touched tree", "pizza", "running",
           "television"]
};
console.log(day1.squirrel);
// → false
console.log(day1.wolf);
// → undefined
day1.wolf = false;
console.log(day1.wolf);
// → false
----

(((quoting,of object properties)))(((colon character)))Inside the
curly braces, we can give a list of properties separated by commas.
Each property is written as a name, followed by a colon, followed by
an expression that provides a value for the property. Spaces and line
breaks are not significant. When an object spans multiple lines,
indenting it like in the previous example improves readability.
Properties whose names are not valid variable names or valid numbers
have to be quoted.

[source,javascript]
----
var descriptions = {
  work: "Went to work",
  "touched tree": "Touched a tree"
};
----

This means that ((curly braces)) have _two_ meanings in JavaScript. At
the start of a statement, they start a block of statements. In any
other position, they describe an object. Fortunately, it is almost
never useful to start a statement with a curly-brace object, and in
typical programs, there is no ambiguity between these two uses.

(((undefined)))Reading a property that doesn't exist will produce the
value `undefined`, which happens the first time we try to read the `wolf`
property in the previous example.

(((property,assignment)))(((mutability)))(((= operator)))It is
possible to assign a value to a property expression with the `=`
operator. This will replace the property's value if it already existed
or create a new property on the object if it didn't.

(((tentacle (analogy))))(((property,model of)))To briefly return to
our tentacle model of ((variable)) bindings—property bindings are
similar. They _grasp_ values, but other variables and properties might
be holding onto those same values. You may think of objects as
octopuses with any number of tentacles, each of which has a name
inscribed on it.

image::img/octopus-object.jpg[alt="Artist's representation of an object"]

(((delete operator)))(((property,deletion)))The `delete` operator cuts
off a tentacle from such an octopus. It is a unary operator that, when
applied to a property access expression, will remove the named
property from the object. This is not a common thing to do, but it is
possible.

[source,javascript]
----
var anObject = {left: 1, right: 2};
console.log(anObject.left);
// → 1
delete anObject.left;
console.log(anObject.left);
// → undefined
console.log("left" in anObject);
// → false
console.log("right" in anObject);
// → true
----

(((in operator)))(((property,testing for)))(((object)))The binary
`in` operator, when applied to a string and an object, returns a
Boolean value that indicates whether that object has that property.
The difference between setting a property to `undefined` and actually
deleting it is that, in the first case, the object still _has_ the
property (it just doesn't have a very interesting value), whereas in
the second case the property is no longer present and `in` will return
`false`.

(((array)))(((collection)))Arrays, then, are just a kind of
object specialized for storing sequences of things. If you evaluate
`typeof [1, 2]`, this produces `"object"`. You can see them as long,
flat octopuses with all their arms in a neat row, labeled with
numbers.

image::img/octopus-array.jpg[alt="Artist's representation of an array"]

(((journal)))(((weresquirrel example)))So we can represent Jacques’
journal as an array of objects.

[source,javascript]
----
var journal = [
  {events: ["work", "touched tree", "pizza",
            "running", "television"],
   squirrel: false},
  {events: ["work", "ice cream", "cauliflower",
            "lasagna", "touched tree", "brushed teeth"],
   squirrel: false},
  {events: ["weekend", "cycling", "break",
            "peanuts", "beer"],
   squirrel: true},
  /* and so on... */
];
----

== Mutability ==

We will get to actual programming _real_ soon now. But first, there's
one last piece of theory to understand.

(((mutability)))(((side effect)))(((number)))(((string)))(((Boolean)))(((object)))We've seen that object
values can be modified. The types of values discussed in earlier
chapters, such as numbers, strings, and Booleans, are all
__immutable__—it is impossible to change an existing value of those
types. You can combine them and derive new values from them, but when
you take a specific string value, that value will always remain the
same. The text inside it cannot be changed. If you have reference to a
string that contains `"cat"`, it is not possible for other code to
change a character in _that_ string to make it spell `"rat"`.

With objects, on the other hand, the content of a value _can_ be
modified by changing its properties.

(((object,identity)))(((identitiy)))(((memory)))When we have two
numbers, 120 and 120, we can consider them precisely the same number,
whether or not they refer to the same physical bits. But with objects,
there is a difference between having two references to the same object
and having two different objects that contain the same properties.
Consider the following code:

[source,javascript]
----
var object1 = {value: 10};
var object2 = object1;
var object3 = {value: 10};

console.log(object1 == object2);
// → true
console.log(object1 == object3);
// → false

object1.value = 15;
console.log(object2.value);
// → 15
console.log(object3.value);
// → 10
----

(((tentacle (analogy))))(((variable,model of)))The `object1` and
`object2` variables grasp the _same_ object, which is why changing
`object1` also changes the value of `object2`. The variable `object3`
points to a different object, which initially contains the same
properties as `object1` but lives a separate life.

(((== operator)))(((comparison,of objects)))(((deep
comparison)))JavaScript's `==` operator, when comparing objects, will
return `true` only if both objects are precisely the same value.
Comparing different objects will return `false`, even if they have
identical contents. There is no “deep” comparison operation built into
JavaScript, which looks at object's contents, but it is possible to
write it yourself (which will be one of the
link:04_data.html#exercise_deep_compare[exercises] at the end of this
chapter).

== The lycanthrope's log ==

(((weresquirrel example)))(((lycanthropy)))(((addEntry function)))So
Jacques starts up his JavaScript interpreter and sets up the
environment he needs to keep his ((journal)).

// include_code

[source,javascript]
----
var journal = [];

function addEntry(events, didITurnIntoASquirrel) {
  journal.push({
    events: events,
    squirrel: didITurnIntoASquirrel
  });
}
----

And then, every evening at ten—or sometimes the next morning, after
climbing down from the top shelf of his bookcase—he records the day.

[source,javascript]
----
addEntry(["work", "touched tree", "pizza", "running",
          "television"], false);
addEntry(["work", "ice cream", "cauliflower", "lasagna",
          "touched tree", "brushed teeth"], false);
addEntry(["weekend", "cycling", "break", "peanuts",
          "beer"], true);
----

Once he has enough data points, he intends to compute the
((correlation)) between his squirrelification and each of the day's
events and ideally learn something useful from those correlations.

(((correlation)))_Correlation_ is a measure of ((dependence)) between
((variable))s (“variables” in the statistical sense, not the
JavaScript sense). It is usually expressed as a coefficient that
ranges from -1 to 1. Zero correlation means the variables are not
related, whereas a correlation of one indicates that the two are
perfectly related—if you know one, you also know the other. Negative
one also means that the variables are perfectly related but that they
are opposites—when one is true, the other is false.

(((phi coefficient)))For binary (Boolean) variables, the _phi_
coefficient (_ϕ_) provides a good measure of correlation and is
relatively easy to compute. To compute _ϕ_, we need a ((table)) _n_
that contains the number of times the various combinations of the two
variables were observed. For example, we could take the event of
eating ((pizza)) and put that in a table like this:

image::img/pizza-squirrel.svg[alt="Eating pizza versus turning into a squirrel",width="7cm"]

_ϕ_ can be computed using the following formula, where _n_ refers to the table:

ifdef::html_target[]

++++
<div>
<style scoped="scoped">sub { font-size: 60%; }</style>
<table style="border-collapse: collapse; margin-left: 1em;"><tr>
  <td style="vertical-align: middle"><em>ϕ</em> =</td>
  <td style="padding-left: .5em">
    <div style="border-bottom: 1px solid black; padding: 0 7px;">n<sub>11</sub>n<sub>00</sub> - n<sub>10</sub>n<sub>01</sub></div>
    <div style="padding: 0 7px;">√<span style="border-top: 1px solid black; position: relative; top: 2px;">
      <span style="position: relative; top: -4px">n<sub>1•</sub>n<sub>0•</sub>n<sub>•1</sub>n<sub>•0</sub></span>
    </span></div>
  </td>
</tr></table>
</div>
++++

endif::html_target[]

ifdef::tex_target[]

pass:[\begin{equation}\varphi = \frac{n_{11}n_{00}-n_{10}n_{01}}{\sqrt{n_{1\bullet}n_{0\bullet}n_{\bullet1}n_{\bullet0}}}\end{equation}]

endif::tex_target[]

The notation (!html _n_~01~!)(!tex pass:[$n_{01}$]!) indicates the
number of measurements where the first variable (squirrelness) is false
(0) and the second variable (pizza) is true (1). In this
example, (!html _n_~01~!)(!tex pass:[$n_{01}$]!) is 9.

The value (!html _n_~1•~!)(!tex pass:[$n_{1\bullet}$]!) refers to the
sum of all measurements where the first variable is true, which is 5
in the example table. Likewise, (!html _n_~•0~!)(!tex pass:[$n_{\bullet0}$]!)
refers to the sum of the measurements where the second variable is false.

(((correlation)))(((phi coefficient)))So for the pizza table, the part
above the division line (the dividend) would be 1×76 - 4×9 = 40, and
the part below it (the divisor) would be the square root of
5×85×10×80, or (!html √340000!)(!tex pass:[$\sqrt{340000}$]!). This
comes out to _ϕ_ ≈ 0.069, which is tiny. Eating ((pizza)) does not
appear to have influence on the transformations.

== Computing correlation ==

(((array,as table)))(((nesting,of arrays)))We can represent a
two-by-two ((table)) in JavaScript with a four-element array (`[76, 9,
4, 1]`). We could also use other representations, such as an array
containing two two-element arrays (`[[76, 9], [4, 1]]`) or an object
with property names like `"11"` and `"01"`, but the flat array is
simple and makes the expressions that access the table pleasantly
short. We'll interpret the indices to the array as two-((bit))
((binary number)), where the leftmost (most significant) digit refers
to the squirrel variable and the rightmost (least significant) digit
refers to the event variable. For example, the binary number `10`
refers to the case where Jacques did turn into a squirrel, but the
event (say, "pizza") didn't occur. This happened four times. And since
binary `10` is 2 in decimal notation, we will store this number at
index 2 of the array.

(((phi coefficient)))(((phi function)))This is the function that
computes the _ϕ_ coefficient from such an array:

// test: clip
// include_code strip_log

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

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

(((square root)))(((Math.sqrt function)))This is simply a direct
translation of the _ϕ_ formula into JavaScript. `Math.sqrt` is the
square root function, as provided by the `Math` object in a standard
JavaScript environment. We have to sum two fields from the table to
get fields like (!html n~1•~!)(!tex pass:[$n_{1\bullet}$]!) because
the sums of rows or columns are not stored directly in our data
structure.

(((JOURNAL data set)))Jacques kept his journal for three months. The
resulting ((data set)) is available in the coding sandbox for this
chapter(!book (http://eloquentjavascript.net/code#4[_eloquentjavascript.net/code#4_])!),
where it is stored in the `JOURNAL` variable, and in a downloadable
http://eloquentjavascript.net/code/jacques_journal.js[file].

(((tableFor function)))(((hasEvent function)))To extract a two-by-two
((table)) for a specific event from this journal, we must loop over
all the entries and tally up how many times the event occurs in
relation to squirrel transformations.

// include_code strip_log

[source,javascript]
----
function hasEvent(event, entry) {
  return entry.events.indexOf(event) != -1;
}

function tableFor(event, journal) {
  var table = [0, 0, 0, 0];
  for (var i = 0; i < journal.length; i++) {
    var entry = journal[i], index = 0;
    if (hasEvent(event, entry)) index += 1;
    if (entry.squirrel) index += 2;
    table[index] += 1;
  }
  return table;
}

console.log(tableFor("pizza", JOURNAL));
// → [76, 9, 4, 1]
----

(((array,searching)))(((indexOf method)))The `hasEvent` function tests
whether an entry contains a given event. Arrays have an `indexOf`
method that tries to find a given value (in this case, the event name)
in the array and returns the index at which it was found or -1 if it
wasn't found. So if the call to `indexOf` doesn't return -1, then we
know the event was found in the entry.

(((array,indexing)))The body of the loop in `tableFor` figures
out which box in the table each journal entry falls into by checking
whether the entry contains the specific event it's interested in and
whether the event happens alongside a squirrel incident. The loop then
adds one to the number in the array that corresponds to this box on
the table.

We now have the tools we need to compute individual ((correlation))s.
The only step remaining is to find a correlation for every type of
event that was recorded and see whether anything stands out. But how
should we store these correlations once we compute them?

== Objects as maps ==

(((weresquirrel example)))(((array)))One possible way is to store
all the ((correlation))s in an array, using objects with `name` and
`value` properties. But that makes looking up the correlation for a
given event somewhat cumbersome: you'd have to loop over the whole
array to find the object with the right `name`. We could wrap this
lookup process in a function, but we would still be writing more code,
and the computer would be doing more work than necessary.

[[object_map]]
(((object)))(((square brackets)))(((object,as map)))(((in
operator)))A better way is to use object properties named after the
event types. We can use the square bracket access notation to create
and read the properties and can use the `in` operator to test whether
a given property exists.

[source,javascript]
----
var map = {};
function storePhi(event, phi) {
  map[event] = phi;
}

storePhi("pizza", 0.069);
storePhi("touched tree", -0.081);
console.log("pizza" in map);
// → true
console.log(map["touched tree"]);
// → -0.081
----

(((data structure)))A _((map))_ is a way to go from values in one
domain (in this case, event names) to corresponding values in another
domain (in this case, _ϕ_ coefficients).

There are a few potential problems with using objects like this, which
we will discuss in link:06_object.html#prototypes[Chapter 6], but for
the time being, we won't worry about those.

(((for/in loop)))(((for loop)))(((object,looping over)))What if
we want to find all the events for which we have stored a coefficient?
The properties don't form a predictable series, like they would in an
array, so we cannot use a normal `for` loop. JavaScript provides a
loop construct specifically for going over the properties of an
object. It looks a little like a normal `for` loop but distinguishes
itself by the use of the word `in`.

[source,javascript]
----
for (var event in map)
  console.log("The correlation for '" + event +
              "' is " + map[event]);
// → The correlation for 'pizza' is 0.069
// → The correlation for 'touched tree' is -0.081
----

[[analysis]]
== The final analysis ==

(((journal)))(((weresquirrel example)))(((gatherCorrelations
function)))To find all the types of events that are present in the
data set, we simply process each entry in turn and then loop over the
events in that entry. We keep an object `phis` that has correlation
coefficients for all the event types we have seen so far. Whenever we
run across a type that isn't in the `phis` object yet, we compute its
correlation and add it to the object.

// test: clip
// include_code strip_log

[source,javascript]
----
function gatherCorrelations(journal) {
  var phis = {};
  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 phis))
        phis[event] = phi(tableFor(event, journal));
    }
  }
  return phis;
}

var correlations = gatherCorrelations(JOURNAL);
console.log(correlations.pizza);
// → 0.068599434
----

(((correlation)))Let's see what came out.

// test: no

[source,javascript]
----
for (var event in correlations)
  console.log(event + ": " + correlations[event]);
// → carrot:   0.0140970969
// → exercise: 0.0685994341
// → weekend:  0.1371988681
// → bread:   -0.0757554019
// → pudding: -0.0648203724
// and so on...
----

(((for/in loop)))Most correlations seem to lie close to zero. Eating
carrots, bread, or pudding apparently does not trigger
squirrel-lycanthropy. It _does_ seem to occur somewhat more often on
weekends, however. Let's filter the results to show only correlations
greater than 0.1 or less than -0.1.

// start_code
// test: no

[source,javascript]
----
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.

// include_code strip_log

[source,javascript]
----
for (var i = 0; i < JOURNAL.length; i++) {
  var entry = JOURNAL[i];
  if (hasEvent("peanuts", entry) &&
     !hasEvent("brushed teeth", entry))
    entry.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.

(((weresquirrel example)))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 ==

(((array,methods)))(((method)))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.

(((push method)))(((pop method)))(((shift method)))(((unshift
method)))We saw `push` and `pop`, which add and remove elements at the
end of an array, link:04_data.html#array_methods[earlier] in this
chapter. The corresponding methods for adding and removing things at
the start of an array are called `unshift` and `shift`.

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

(((task management example)))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.

(((array,searching)))(((indexOf method)))(((lastIndexOf
method)))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.

[source,javascript]
----
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.

(((slice method)))(((array,indexing)))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.

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

(((string,indexing)))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.

(((concatenation)))(((concat method)))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.

[source,javascript]
----
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 ==

(((string,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.

[source,javascript]
----
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.

(((string,methods)))(((slice method)))(((indexOf
method)))(((string,searching)))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.

[source,javascript]
----
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.

[source,javascript]
----
console.log("one two three".indexOf("ee"));
// → 11
----

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

[source,javascript]
----
console.log("  okay \n ".trim());
// → okay
----

(((length property,for string)))(((charAt
method)))(((string,indexing)))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.

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

[[arguments_object]]
== The arguments object ==

(((arguments object)))(((length
property)))(((parameter)))(((optional argument)))(((array-like
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.

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

(((length property)))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.

indexsee:[pseudo array,array-like object]
(((array,methods)))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.

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

(((journal)))(((console.log)))(((variadic function)))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.

[source,javascript]
----
addEntry(["work", "touched tree", "pizza", "running",
          "television"], false);
----

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

[source,javascript]
----
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");
----

(((arguments object,indexing)))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 ==

(((Math object)))(((Math.min function)))(((Math.max
function)))(((Math.sqrt function)))(((minimum)))(((maximum)))(((square
root)))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).

[[namespace_pollution]]
(((namespace)))(((namespace pollution)))(((object)))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.

(((variable,naming)))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.

(((Math.cos function)))(((Math.sin function)))(((Math.tan
function)))(((Math.acos function)))(((Math.asin
function)))(((Math.atan function)))(((Math.PI
constant)))(((cosine)))(((sine)))(((tangent)))(((PI constant)))(((pi)))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.)

// test: no

[source,javascript]
----
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
link:13_dom.html#sin_cos[Chapter 13], I'll explain them.

(((Math.random function)))(((random number)))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.

// test: no

[source,javascript]
----
console.log(Math.random());
// → 0.36993729369714856
console.log(Math.random());
// → 0.727367032552138
console.log(Math.random());
// → 0.40180766698904335
----

(((pseudorandom number)))(((random number)))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.

(((rounding)))(((Math.floor function)))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`.

// test: no

[source,javascript]
----
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.

(((Math.ceil function)))(((Math.round function)))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 ==

(((global object)))(((window variable)))(((global
scope)))(((scope)))(((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 ((browser))s, the global scope object is stored in the
`window` variable.

// test: no

[source,javascript]
----
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 ===

(((summing (exercise))))The link:00_intro.html#intro[introduction] of this book alluded to the
following as a nice way to compute the sum of a range of numbers:

// test: no

[source,javascript]
----
console.log(sum(range(1, 10)));
----

(((range function)))(((sum function)))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.

(((optional argument)))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]`.

ifdef::interactive_target[]

// test: no

[source,javascript]
----
// 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
----
endif::interactive_target[]

!!hint!!

(((summing (exercise))))(((array,creation)))(((square
brackets)))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.

(((array,indexing)))(((comparison)))Since the end boundary is
inclusive, you'll need to use the `<=` operator rather than simply `<`
to check for the end of your loop.

(((arguments object)))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.

(((range function)))(((for loop)))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)).

!!hint!!

=== Reversing an array ===

(((reversing (exercise))))(((reverse
method)))(((array,methods)))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.

(((efficiency)))(((pure function)))(((side effect)))Thinking back to
the notes about side effects and pure functions in the
link:03_functions.html#pure[previous chapter], which variant do you
expect to be useful in more situations? Which one is more efficient?

ifdef::interactive_target[]

// test: no

[source,javascript]
----
// 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]
----
endif::interactive_target[]

!!hint!!

(((reversing (exercise))))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.

!!hint!!

[[list]]
=== A list ===

(((data structure)))(((list (exercise))))(((linked
list)))(((object)))(((array)))(((collection)))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.

// include_code

[source,javascript]
----
var list = {
  value: 1,
  rest: {
    value: 2,
    rest: {
      value: 3,
      rest: null
    }
  }
};
----

The resulting objects form a chain, like this:

image::img/linked-list.svg[alt="A linked list",width="6cm"]

(((structure sharing)))(((memory)))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.

(((recursion)))If you haven't already, also write a recursive version
of `nth`.

ifdef::interactive_target[]

// test: no

[source,javascript]
----
// 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
----
endif::interactive_target[]

!!hint!!

(((list (exercise))))(((linked list)))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.

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

[source,javascript]
----
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.

(((recursion)))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 __N__th element of the
list that's in this list's `rest` property.

!!hint!!

[[exercise_deep_compare]]
=== Deep comparison ===

(((deep comparison (exercise))))(((comparison)))(((deep
comparison)))(((== operator)))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`.

(((null)))(((=== operator)))(((typeof operator)))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"`.

ifdef::interactive_target[]

// test: no

[source,javascript]
----
// 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
----
endif::interactive_target[]

!!hint!!

(((deep comparison (exercise))))(((typeof operator)))(((object)))(((=== operator)))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 `===`.

(((for/in loop)))(((in operator)))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`.

(((return value)))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.

!!hint!!