Background

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');

function read_json_file(filename) {
    var contents = fs.readFileSync(filename);

    return JSON.parse(contents);
}
exports.read_json_file=read_json_file;

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)
            data=read_json_file("big.json");
        // 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 data=read_json_file("ancestry.json");

    var names = [];

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

    exports.names=names;

Here's an algorithm, roughly the Fisher-Yates shuffle that shuffles an array in place.

    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)
                data=read_json_file("big.json");
            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?