As part of Stack Overflow's pro-diversity initiatives, I have been helping Andela by mentoring one of their fellows, Bosun, in data structures and algorithms. In the Stack Overflow "default open" style, I am putting some of our notes on the internet, in the hope they will be useful to more people. Most of the code is either pseudo-code or JavaScript, which we chose because it's simple and easy to access and everyone pretty much knows the basics of it.

Andela notes index

1. Iterators (part 1)
2. Iterators (part 2)
3. Stacks
4. Queues
5. Implementing a calculator (part 1)
6. Implementing a calculator (part 2)
7. Trees & Graphs
8. Compression: RLE encoding and decoding
9. Compression: Huffman encoding (part 1)
10. Compression: Huffman encoding (part 2) & decoding

In bold the current part, links point to the other available parts, in italics the parts not yet available.

A disclaimer

IANACS! A lot of the following may be wrong, simplistic or offensive to Haskell puritans. That's because I am a self-taught practitioner of silly walks, and not one of those robot overlords. If you encounter any problem, ask your parents if this content is suitable for your programming religion.

Iterators (aka enumerations) part deux

Iterators or enumerations are sets with an order. To know more about them, what's cool about them and their limitations, please visit the first part of this series.

In this blog post I'll focus on the higher-order functions which enumerate the set.

A nice way of implementing a base iterator, which uses JavaScript 6 is using generator functions. These allow us to use the yield keyword which makes building enumerators a breeze. This iterator is finite and returns all natural numbers (ℕ) less than 100. Note that the functions we are presenting here will not work with infinite enumerators -- in fact, they will stall or crash node.

function* numbers() {
    var i = 0;
    while (i<100) {
        yield i++;
    }
}

Eager (enumerating) composable functions

We can start building functions which we can compose upon the above sample. As you will note, all these functions operate on iterators, but none of them are iterators themselves. They all take a function (with a particular signature) and call it by passing it the iterator elements one by one. However, since their value depends on all the items in the enumeration, they will repeat until the iterator returns a done: true element before returning a result.

Sort

The simplest example is a sorting function. The sort_function takes 2 items and returns -1, 0 or 1 depending on whether the first item should be sorted after, at the same time or before the second. We won't be implementing it here, but I though I would mention it.

The sorting function typically returns an array (or list): since it's necessary to enumerate the iterator in order to sort, we already have an array. Since it is cheap to get an iterator out of an array, but expensive to go the other way, the array is usually returned.

For example, if we want to sort flight reservations by landing time we can use a sort as the following.

flightReservations().sort(function(a, b){
    if (a.landing > b.landing) {
        return -1;
    }
    if (a.landing == b.landing){
        return 0;
    }
    return 1;
});

Each

Each (or reduce) are the equivalent of a for each loop. Well, not really the same, since you can break out of a for loop much more easily than an each. It is very similar to a project operation, but it's not lazy: it applies a function to all elements of an enumeration. Also, it doesn't return anything. Here's the signature of each.

Object.prototype.each = function ( each_function ) {}

Each is (typically) used to execute something for each element. Since the return type is void, this "something" is generally so-called "side effects": for example write to disk, log, send stuff somewhere on the net or change each element somehow.

For example, let's say you have an iterator that returns your calendar appointments, and you want to schedule reminders for them. You can pass a function that, given an appointment, contacts your scheduler service and sets the reminder.

calendarAppointments().each(function( item ) { 
    if (item.Reminder === undefined) { 
        setReminder(item); 
    }
});

Fold

Let's say you want to count all the appointments that you have. If you use each to count them, you need to have a variable in the outer scope which keeps count across the applications of the counting function you pass to each. This works, but it's a bit dirty because it relies on the compiler to notice this and "capture" the outer scope variable in the inner function. Doing so has some issues (for example, the function becomes a full fledged object, at least in .NET).

var count = 0;
calendarAppointments().each(function( item ) { 
    count++;
});

A better way is using a fold. folds explicitly pass an object to all inner function calls so state can be kept. Thus, a fold has this signature

Object.prototype.each = function( accumulator, fold_function ) {}

where fold_function looks like

<any> fold_function( accumulator, item ) {}

and accumulator is where we receive our state, and <any> is where we return it for the next item. With this, we can count elements like so

calendarAppointments().fold( 0, function(accumulator, item) {
    return accumulator++;    
});

Fold is implemented on Array.prototype with the name "reduce" in JavaScript 2015.

Derivative higher order functions

We can use these functions to create a number of useful derivatives.

• count returns the number of items and can be implemented as above

  Object.prototype.count = function(item) { if (this.constructor.name=='GeneratorFunctionPrototype') { return this.fold( function( 0, function(accumulator, item) { return accumulator++; } } return null; });

• min, max and sum can also be implemented via fold, but can also take a function that, given an item, returns the value to be summed or minmaxed.

Let's code!

I've put together a project on GitHub which you can clone and complete. It already has tests and solutions if you want to cheat -- but I'd advise you at least try to implement these operators yourself for max enjoy.

The exercise boils down to completing the functions in this file

Object.prototype.each = function (func) {
    if (this.constructor.name=='GeneratorFunctionPrototype') {
        // code here
    }
};

Object.prototype.fold = function (accumulator, func) {
    if (this.constructor.name=='GeneratorFunctionPrototype') {
        // code here
    }
};

Object.prototype.max = function (func) {
    if (this.constructor.name=='GeneratorFunctionPrototype') {
        // code here
    }
};

How to set up your system

1. Install a recent version of node.js (link)
2. Fork https://github.com/sklivvz/andela-data-structures on github
3. Clone in your preferred folder
4. From a terminal npm install restores the test packag
5. npm start 2 runs the code

You should get something like

Edit the file ./parts/02-iterators.js with your solution and run again until all tests pass.

---

External links:

• MDN on iterators
• Wikipedia on iterators