UNB/ CS/ David Bremner/ teaching/ cs2613/ labs/ CS2613 Lab 11

# Array methods

Time
10 minutes
Activity
Demo

In Lab 10 we used a few Array methods like `length`. It turns out that JavaScript arrays have some useful higher order methods, i.e. methods that take functions as arguments.

• `map` and `filter` behaves similary to Racket list functions of the same name. It turns out that most places one would use lists in Racket, one uses arrays in Javascript.

• `reduce` is similar to `foldl`. We used the related Racket macro `for/fold` in Lab 5. In Eloquent JavaScript Chapter 5, the author impliments `average` using reduce. The use of an anonymous function here is a matter of taste.

```    function average (array) {
return array.reduce(function (a,b) {__________}, 0)/array.length;
}
console.log(average([1,2,3]));
```
• `forEach` gives a way to iterate over a list with an arbitrary action (with side effects), without fussing with loop indices and bounds. Note that this is different than `map` in that it doesn't construct a list.
```    function average2 (array) {
var sum=0;
array.forEach(function (a) { __________ });
return sum/array.length;
}
```

# Flatten

Time
25 minutes
Activity
Small groups

Solve the Flatten Exercise using `reduce` and `concat` methods. Your solution should pass the following test suite. Notice that one of the specs is disabled ("pending"); that's because this solution only works for one level of nesting. This motivates the task of implimenting `flatten` recursively in A3

```flatten=require("./flatten.js").flatten;
describe("flatten",
function () {
it("base case",
function () {
expect(flatten([])).toEqual([]);
});
it("single element",
function () {
expect(flatten([1])).toEqual([1]);
expect(flatten(["foo"])).toEqual(["foo"]);
expect(flatten([{foo: 1}])).toEqual([{foo: 1}]);
});
it("longer list, no mutation",
function () {
var data = [[1],2,[3],4,[5,6]];
var orig_data = data;
expect(flatten(data)).toEqual([1,2,3,4,5,6]);
expect(data).toEqual(orig_data);
});
xit("deeper nesting",
function () {
var data = [[[1],2,[3]],4,[5,6]];
var orig_data = data;
expect(flatten(data)).toEqual([1,2,3,4,5,6]);
expect(data).toEqual(orig_data);
});

});
```

# JSON

Time
15 minutes
Activity
Demo/Group discussion

Like Assignment 2, Assignment 3 includes a question about parsing JSON. The syntax should look more familiar now that we have studied JavaScript a bit. The book embeds ancestry.json in a JavaScript string, which feels a bit fake, because we start out with a perfectly good data structure and then squash it into a string. Since we're using node.js, we can reasonably simply read the JSON from a file.

```var fs = require('fs');

return JSON.parse(contents);
}
```

Here we consider another way simulate "object-like" behaviour, by using a closure. The way that by_name is defined is a bit complicated, but it allows us to keep the variable `data` between calls. Which of `for` or `forEach` makes the most sense here?

```var read_json_file=require("./read_json_file.js").read_json_file;

var by_name = (function () {
var data = null;
var real_by_name= function(name){
if (data===null)
// simple linear scan

return null;
};
return real_by_name;
})();

exports.by_name=by_name;
```

Here are some tests that our function should pass.

```by_name=require("./ancestry.js").by_name;
describe("by_name", function() {
it("not-present", function() {
expect(by_name("ronald mcdonald")).toBe(null);
expect(by_name("Captain Ahab")).toBe(null);
});
it("first", function () {
expect(by_name("Carolus Haverbeke")).toEqual({"name": "Carolus Haverbeke", "sex": "m", "born": 1832, "died": 1905, "father": "Carel Haverbeke", "mother": "Maria van Brussel"});
});
it("last", function () {
expect(by_name("Jacobus Bernardus van Brussel")).toEqual({"name": "Jacobus Bernardus van Brussel", "sex": "m", "born": 1736, "died": 1809, "father": "Jan van Brussel", "mother": "Elisabeth Haverbeke"});
});
it("middle", function () {
expect(by_name("Joanna de Pape")).toEqual(  {"name": "Joanna de Pape", "sex": "f", "born": 1654, "died": 1723, "father": "Vincent de Pape", "mother": "Petronella Wauters"});
});

});
```

# Methods

Time
25 minutes
Activity
Group discussion / Demo

We know about objects in JavaScript, and we can use them in a simple way by e.g. naming conventions for functions.

```function timePlus(time1, time2) {
var mins = (time1.mins + time2.mins) % 60;
var hours = time1.hours + time2.hours + Math.floor((time1.mins+time2.mins)/60);
return {'hours': hours, 'mins': mins};
}

console.log(timePlus({hours: 10, mins:30}, {hours: 17, mins:47}));
```

If we want to have "time" objects with a "plus" method, one way is to add that method manually. In order for that to work, we need to make use of the JavaScript variable this. When the function `method` is called as `object.method()`, the special variable `this` is defined to mean the current object.

```function maketime(hours, mins){
var plus=function (other) {
var raw=timePlus(this,other);
return ______________________________
};

return { 'hours': hours, 'mins': mins, 'plus': plus};
}

var A=maketime(10, 30);
var B=maketime(17, 47);
var C=A.plus(B);
console.log(C);
```

Adding methods manually to newly created objects is a bit painful, so JavaScript has the notion of a 'prototype'

```var protoTime = {
plus: function(other) {
var raw=timePlus(this,other);
return timeNew(raw.hours, raw.mins);
}
};

function timeNew(hours, mins) {
var obj=Object.create(protoTime);
_______________;
_____________;
return obj;
}

D=timeNew(21,42);
E=timeNew(17,37);

F=D.plus(E);
console.log(F);
```

The benefit is not huge here, but you can see how it would help if there were many methods, all creating new objects.

In practice it's not usual to call object.create directly with the prototype object, but rather to use `new` keyword, along with the `prototype` property of a constructor.

```function Time(hours, mins){
this.hours=hours;
this.mins=mins;
}

Time.prototype.plus=function (other) {
var raw=timePlus(this,other);
return ______________________________;
}

G = new Time(20,59);
H = new Time(11,11);

I=G.plus(H);
console.log(I);
```

Finally, ES2015 provides the `class` keyword to concisely generate constructors and prototypes.

```class Time2 {
constructor(hours, mins){
this.hours=hours;
this.mins=mins;
};
plus(other) {
var raw=timePlus(this,other);
______________________________________;
}
}

Time2;

J= new Time2(5,30);
K= new Time2(11,55);

L=J.plus(K);
```

It's important to keep in mind that this is just convenience syntax for the same prototype based system.

# Memoization

Time
25 minutes
Activity
Small Groups

For small data sets, a for loop is fast enough, but for larger data sets, it pays to be a bit smarter. In order to be able to see the difference, here is a larger data file. It contains all the data from before, padded with many copies with slightly changed names.

• To start, here are a couple of simple utility modules to help with our benchmarking. The first just extracts all possible names to query with.
```    var read_json_file=require("./read_json_file.js").read_json_file;

var names = [];

for (var i=0; i<data.length; i++){
names.push(data[i].name);
}

exports.names=names;
```
```    function shuffle (array) {
var dest=array.length;

for (var dest=array.length-1; dest>0; dest--) {

var source = Math.floor(Math.random() * dest);
var tmp = array[dest];
array[dest] = array[source];
array[source]=tmp;
}
}

exports.shuffle=shuffle;
```
• Save the following as `~/fcshome/cs2613/labs/L11/ancestry.times.js`, and run it with

``````\$ node ancestry.times.js
``````
```    var by_name=require("./ancestry.js").by_name;
var names=require("./names.js").names;
var shuffle=require("./shuffle.js").shuffle;

var reps = 3;

for (var i=0; i< reps; i++){
shuffle (names);
for (var j=0; j<names.length; j++) {
var test_name=i+","+j;
console.time(test_name);
var dummy=by_name(names[i]);
console.timeEnd(test_name);
}
}
```
• Now replace "ancestry.json" with "big.json" in ancestry.js, and observe the change in running times. Repeat the run a few times.

• copy `ancestry.js` to `memoize.js`, and fill in the test in the inner loop. Don't forget to update the cache.

```    var read_json_file=require("./read_json_file.js").read_json_file;

var by_name = (function () {
var cache = {};
var data = null;
var real_by_name= function(name){
if (data===null)
if (cache[name] != undefined)
return cache[name];
for (var i=0; i<data.length; i++){

}
return null;
};
return real_by_name;
})();

exports.by_name=by_name;
```
• copy `ancestry.times.js` to `memoize.times.js`, and require `memoize.js` in order to test your new algorithm.

• Finally, how does this memoization code relate the simpler code in the book that builds up the byName cache? When would one approach be better than the other?

• If you have extra time: there are several variations for the memoization algorithm, e.g.

• update cache every query, or only on success
• remove cached elements from data

Try to see if any of these variations make a difference in performance. Why or why not?