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

# Discussion

Time
5 minutes
Activity
Group discussion
• Discussion about individual work time.

# 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` behave 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.

```    function average (array) {
return array.reduce((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) {
let sum=0;
array.forEach( (a) =>       );
return sum/array.length;
}
```

# Flatten

Time
20 minutes
Activity
Exercise from book.

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

```let 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 () {
let data = [[1],2,[3],4,[5,6]];
let orig_data = data;
expect(flatten(data)).toEqual([1,2,3,4,5,6]);
expect(data).toEqual(orig_data);
});
xit("deeper nesting",
function () {
let data = [[[1],2,[3]],4,[5,6]];
let 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

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.

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

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

The use of a module local variable here to cache data is roughly equivalent to a class variable in Java. It's not particularly flexible, and real code would likely use an object to cache data for a given file.

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

let data = null;

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

return null;

}
exports.by_name=by_name;
```

Here are some tests that our function should pass.

```let 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) {
let mins = (time1.mins + time2.mins) % 60;
let 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){
let plus=function (other) {
let raw=timePlus(this,other);
return ______________________________
};

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

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

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

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

function timeNew(hours, mins) {
let 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) {
let 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) {
let 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
Individual

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.
```    let read_json_file=require("./read_json_file.js").read_json_file;

let names = [];

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

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

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

let source = Math.floor(Math.random() * dest);
let 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
``````
```    let by_name=require("./ancestry.js").by_name;
let names=require("./names.js").names;
let shuffle=require("./shuffle.js").shuffle;

let reps = 3;

for (let i=0; i< reps; i++){
shuffle (names);
for (let j=0; j<names.length; j++) {
let test_name=i+","+j;
console.time(test_name);
let 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.

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

let cache = {};
let data = null;

function by_name(name){
if (data===null)
if (cache[name] != undefined)
return cache[name];
// loop goes here

return null;
};

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?