04_data.txt

:chap_num: 4
:prev_link: 03_functions
:next_link: 05_higher_order
:load_files: ["js/code/jaques_journal.js", "js/04_data.js"]

= Data Structures: Objects and Arrays =

[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.
____

(((data)))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 only operating 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 programming to start writing
significant 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::tex_target[]

The online coding sandbox for the book (`eloquentjavascript.net/code`)
will automatically load the needed code when you are running a
specific example. If you decide to work through the examples in
another environment, be sure to start from the full code for this
chapter (`04_data.js`, available from the website).

endif::tex_target[]

== The weresquirrel ==

Every now and then, usually between eight and ten in the evening,
Jaques finds himself transforming into a small furry rodent with a
bushy tail.

On the one hand, Jaques 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.svg[alt="The weresquirrel"]

That takes care of the cat and oak problems. But Jaques 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 only happened on days when he
had touched trees. So he stopped touching trees entirely, and even
avoided going near them. But the problem persisted anyway.

Switching to a more scientific approach, Jaques 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 ==

In order 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 very
simple example, that we want to represent a collection of numbers: 2, 3, 5, 7, and 11.

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 type)))((([] (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))))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.

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 very
well.

== Properties ==

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

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

// test: no

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

((([] (subscript))))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 “0” or “John Doe”,
you must use square brackets: `value[0]` or
`value["John Doe"]`. 
This is the case even though you know the precise name of the
property in advance, because netiher "0" nor "John Doe" is a valid
variable name, and so cannot be accessed through dot notation.

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 its length. 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 it is easier to write than `array["length"]`.

== Methods ==

(((method)))(((String type)))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
----

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

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 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”.

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"]
----

(((Array type)))(((array,methods)))(((push method)))(((pop
method)))(((join method)))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 ==

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 Jaques 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.

(((Object type)))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
----

Inside of 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 example above
improves readability. Properties whose names are
not valid variable names or valid numbers have to be quoted.


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

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

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

To briefly come back 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 leg from an 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 very common thing to do in practice, but it is allowed.)

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

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)))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"]

So we can represent Jaques’ 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)))We've seen that object values can be
modified. The types of values discussed in earlier chapters 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)))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
----

`object1` and `object2` are two variables grasping 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)))JavaScript's `==` operator, when comparing objects,
will return `true` only if both values 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, but it is possible to write it yourself.
(Which will be one of the exercises at the end of this chapter.)

== The lycanthrope's log ==

So Jaques 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 hopefully learn something useful from those correlations.

_Correlation_ is a measure of dependence between variables (“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"]

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

ifdef::html_target[]

++++
<style>sub { font-size: 60%; }</style>
<table style="border-collapse: collapse; margin-left: 1em;"><tr>
  <td>ϕ =&nbsp;</td>
  <td>
    <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>
++++

endif::html_target[]

ifdef::tex_target[]

latexmath:[\phi = \frac{n_{11}n_{00}-n_{10}n_{01}}{\sqrt{n_{1\bullet}n_{0\bullet}n_{\bullet1}n_{\bullet0}}}]

endif::tex_target[]

The notation _n_~01~ indicates the number of measurements where the first
measurement (pizza) is false (0) and the second measurement (squirrelness) is
true (1). In this example, _n_~01 is 4.

The value _n_~1•~ refers to the sum of all
measurements where the first variable is true, which is 10 in the
above table. Likewise, _n_~•0~ refers to the sum of the measurements where
the squirrel variable is false.

So for the pizza table, the part above the division line (the dividend)
would be 1×76 - 9×4 = 40, and the part below it (the divisor) would be the
square root of 10×80×5×85, or √340000. This comes out to _ϕ_ ≈ 0.069. This
is tiny. Eating pizza does not appear to have influence on the
transformations.

== Computing correlation ==

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 numbers, where the first digit refers
to the squirrel variable and the second digit
refers to event variable. 
For example, the binary number `10`
refers to the case where the event (say, "pizza") is true, but
Jaques didn't turn into a squirrel.
And since binary `10` is 2 in decimal notation, we will store this 
value in the array at index 2.

(((phi coefficient)))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)))(((sqrt function)))This is simply a direct translation
of the _phi_ 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 n~1•~,
because the sums of rows or columns are not stored directly in our
data structure.

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

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]
----

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.

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 correlations. The
only step remaining is to find a correlation for every type of
event that was recorded, and see if anything stands out. But how 
should we store these correlations once we compute them?

== Objects as maps ==

One possible way is to
store all the correlations 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.

A better 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 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
----

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 Chapter 6, but for the time being, we won't worry
about those.

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

== The final analysis ==

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

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...
----

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.

// 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.

[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
Jaques 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, Jaques simply stops eating peanuts
altogether, and finds that this completely puts an end to his
transformations.

All is well with Jaques 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, Jaques 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)))(((Array type)))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, earlier in this chapter. The corresponding methods
for adding and removing things to 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);
}
----

The above 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.

(((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)))Another fundamental method is `slice`, which
takes a start 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]
----

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.

(((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 returns a new array
with the same elements as the input array, but without the element at the given index.

[source,javascript]
----
function remove(array, index) {
  return array.slice(0, index)
    .concat(array.slice(index + 1));
}
console.log(remove([1, 2, 3, 4, 5], 2));
// → [1, 2, 4, 5]
----

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

[source,javascript]
----
var myString = "Fido";
myString.myProperty = "value";
console.log(myString.myProperty);
// → undefined
----

Types like strings, numbers, and booleans 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.

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 only looks for a single element.

[source,javascript]
----
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. To trim only 
one side, the `trimLeft` and `trimRight` methods can be used.

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

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

== The arguments object ==

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

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.

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

(((console.log function)))(((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 Jaques’ 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 a
slightly nicer alternative:

[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");
----

This version reads its first argument (`squirrel`) in the normal way, 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)))(((min function)))(((max function)))(((sqrt
function)))As we've seen, `Math` is a grab-bag of number-related
utility functions, such `Math.max` (maximum), `Math.min` (minimum),
and `Math.sqrt` (square root).

(((namespace)))(((namespace pollution)))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.

(((trigonometry)))(((cos function)))(((sin function)))(((tan
function)))(((acos function)))(((asin function)))(((atan
function)))(((PI constant)))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`. 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, this book won't go into any complicated math.

(((random function)))The example above uses `Math.random`. This is a
function that returns a new pseudo-random 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
----

(((pseudo-random numbers)))(((random numbers)))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 a 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.

(((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 ten gives us a number greater than or
equal to zero, and below ten. Since `Math.floor` rounds down,
this expression will produce, with equal chance, any
number from 0 through 9.

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

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.

// 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 seperately.

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 a more or less 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 ==

Congratulations. You now know enough JavaScript fundamentals to write
useful programs.

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

// test: no

[source,javascript]
----
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 above 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 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::html_target[]

// test: no

[source,javascript]
----
// Your code here.

console.log(sum(range(1, 10)));
// → 55
console.log(range(5, 2, -1));
// → [5, 4, 3, 2]
----
endif::html_target[]

!!solution!!

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, one for
counting down—because the comparison that checks whether the loop is
finished needs to be “>=” rather than “\<=” when counting downwards.

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.

!!solution!!

=== Reversing an array ===

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

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?

ifdef::html_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::html_target[]

!!solution!!

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 backwards and use the
`push` method. Iterating over an array backwards 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 the last element, and then the
one-but-first and one-but-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.

!!solution!!

=== A list ===

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

// 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"]

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 above), 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 one above when given `[1, 2, 3]` as argument, and 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`.

ifdef::html_target[]

// test: no

[source,javascript]
----
// Your code here.

console.log(arrayToList([1, 2]));
// → {value: 1, rest: {value: 2, rest: null}}
console.log(listToArray(arrayToList([1, 2, 3])));
// → [1, 2, 3]
console.log(prepend(1, prepend(2, null)));
// → {value: 1, rest: {value: 2, rest: null}}
console.log(nth(arrayToList([1, 2, 3]), 1));
// → 2
----
endif::html_target[]

!!solution!!

Building up a list is best done back to front. So `arrayToList` could
iterate over the array backwards (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:

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

 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.

!!solution!!

=== 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"`.

ifdef::html_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::html_target[]

!!solution!!

Your test for whether you are dealing with a real object will look
something like `typeof x == "object" && x != null`. Be careful to only
compare properties 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.

!!solution!!