August 31, 2015 by Marco Cecconi
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.
In bold the current part, links point to the other available parts, in italics the parts not yet available.
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 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++;
}
}
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.
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 (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);
}
});
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
. fold
s 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.
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.
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
}
};
node.js
(link)https://github.com/sklivvz/andela-data-structures
on githubnpm install
restores the test packagnpm start 2
runs the codeYou should get something like
Edit the file ./parts/02-iterators.js
with your solution and run again until all tests pass.
External links:
Hi, I'm Marco Cecconi. I am the founder of Intelligent Hack, developer, hacker, blogger, conference lecturer. Bio: ex Stack Overflow core team, ex Toptal EM.
Read moreMarch 12, 2023 by Marco Cecconi
Stack Overflow could benefit from adopting a using conversational AI to provide specific answers
Read moreOctober 15, 2021 by Marco Cecconi
Multiple people with my name use my email address and I can read their email, chaos ensues!
Read moreSeptember 29, 2021 by Marco Cecconi
After years of building, our top-notch consultancy to help start-ups and scale-ups create great, scalable products, I think it is high time I added an update to how it is going and what's next for us.
Read moreFebruary 03, 2021 by Marco Cecconi
A lesson in building communities by Stack Overflow's most prominent community manager emeritus, Shog9
Read moreDecember 02, 2020 by Marco Cecconi
Some lessons learned over the past 8 years of remote work in some of the best remote companies on the planet
Read moreSoftware engineers go crazy for the most ridiculous things. We like to think that we’re hyper-rational, but when we have to choose a technology, we end up in a kind of frenzy
Read more…