[UPDATE: I’ve been lucky enough to have some commenters who know much more about functional programming than I do. There’s some good reading in the comments, and you especially should read them before using this stuff in production.]
I’ve been playing with functional JavaScript tonight. It’s not the greatest of OO-functional hybrid languages, but it’s good to supplant my fledgling functional skills with something besides Ruby. Plus, I’m not the only one doing it, so I can compare notes. And who doesn’t love JavaScript, right? …right?
Before I get much farther, I should thank Adam Turoff for his post What’s Wrong with the For Loop. It gets at the root of the why we’d use a functional programming language instead of an OO or procedural one, and (bonus!) it helped me grok Ruby’s inject method (it’s the same as my new friend fold). Go read his post, it’s good for you. And if you like it, we recommend the 1981 SICP lectures. Robusto!
Here we go!
Introductions to functional programming usually discuss three methods: map, find, and fold. The names aren’t always the same, but those are the three amigos of functional programming. They all do something different to arrays (or lists, or collections, or whatever you want to call them):
find does what it says. You give it some criteria, it returns all the matching elements. The criteria is expressed as a function, a little bit of code that says “yes, I want this one,” or “no, skip it.” If we’re picking out the red gumballs, you could say (in Ruby) gumballs.find_all { |ball| ball.isRed? } find is also known as filter. [Ruby only calls it find_all because it uses find for returning just the first match.] Po-tay-to, po-tah-to.fold takes each element, and “folds” it into a running total. Think of summation—you’re folding each new number into a running tally. In Haskell (and, it seems, many functional languages), it comes in two varietes, fold_left and fold_right, which just mean “start from the left” and “start from the right”. Ruby calls it inject, which confuses some people (like me).map is the mathiest of them (don’t be scared, it’s easy!). In English, we’d say “change each item like this, and give me the new results.” Let’s down-case a list of words. “Change each word to lowercase, and give me the downcased words.” words.map { |word| word.downcase }. The name “map” comes from functions in math (surprise), where you map each input to one output. The whole y = f(x) thing…f is for “function”. Ruby also calls this collect.
Now, none of these comes predefined in JavaScript. How can this be? Well, all the JavaScript engines out there are in browsers, and we know that “when browser elephants battle, it is the JavaScript grass that suffers.” The browser developers are busy with other things. But this oversight means we have some easy examples to write. It’s boring to re-implement existing stuff, just for the exercise. So here we go—I’ll compare examples in JavaScript and Ruby.
A quick word about JavaScript’s open classes
JavaScript has open classes, just like Ruby. In other words, you can re-open a class definition, give it a method, and then start using that method on instances of that class. JavaScript’s OO is prototype-based, not class-based, so it looks a little weird:
Array.prototype.first = function() {
return this[0];
}
[1, 2, 3].first(); >> 1
Array.prototype.rest = function() {
return this.slice(1);
}
[1, 2, 3].rest(); >> [2, 3]
Array.prototype.isEmpty = function() {
return this.length == 0;
}
[].isEmpty(); >> true
[1].isEmpty(); >> false
“For the prototypical Array, the Array from which all other Arrays spring forth, create a property called ‘first’, which shall be this function, which returns the first element of the Array…” Just a Biblical way of defining a method for a class.
Open classes is good news, because it’ll make our job of adding map, find, and fold possible, since they’ll be going into the Array class.
Find
find is the easiest, so we’ll start there. Let’s take a look:
Array.prototype.find = function(isAMatch) {
var matches = [];
for (i = 0; i < this.length; i++) {
if (isAMatch(this[i])) {
matches.push(this[i]);
}
}
return matches;
}
find is a function, and it takes the function isAMatch as a parameter. One of the hallmarks of the functional programming style is that functions are first-class citizens in the language: they can be treated like any other variable, so they can be passed around as parameters, and returned from other functions. [Closures and anonymous functions are also major features.] isAMatch is a function that tells you whether we should include any given element of the Array. Use find like this:
var evens = [1, 2, 3, 4, 5].find(
function(i) {
return i % 2 == 0;
}
);
function isOdd(i) {
return i % 2 != 0;
}
var odds = [1, 2, 3, 4, 5].find(isOdd);
The first example uses an in-line, anonymous function; the second uses a named function. Both work fine, but here is where we start to see JavaScript’s awkward syntax get in the way. Consider the Ruby version:
# find_all comes pre-defined in Array, via the Enumerable module,
# but this is what it would look like...
class Array
def find_all
matches = []
self.each do |item| # Ruby says 'self', not 'this'.
if yield(item) # yield says "Call the block we were given"
matches << item # Stuff item into matches
end
end
return matches
end
end
evens = [1, 2, 3, 4, 5].find_all { |i|
i % 2 == 0
}
def isOdd(i)
i % 2 != 0
end
odds = [1, 2, 3, 4, 5].find_all { |i|
isOdd(i)
}
In Ruby, every expression returns a value, so return disappears. And Ruby’s blocks mean we don’t need to wrap our match condition inside function(i) { ... }. But Ruby’s find_all won’t take a reference to a method as a parameter:
def isOdd(i)
i % 2 != 0
end
odds = [1, 2, 3, 4, 5].find_all(isOdd) >> `isOdd': wrong number of arguments (0 for 1) (ArgumentError)
Once you’ve defined a function in JavaScript, you can pass it around by name, like any other variable, but you need that function(i) { ... } syntax around your test. In Ruby, find_all takes a block instead of parameters, so you can’t pass a reference. Given how nice blocks are in Ruby, I guess this can be forgiven, but it’s a little weird.
Fold
Now we’ll get into the recursive guys. find is a pain to implement recursively in JavaScript, so I did it iteratively, but recursion works well for fold and map. Since recursion seems to be more idiomatic in functional languages, we’ll use it here.
I took two shots at fold in JavaScript (I’m learning). Here they are:
Array.prototype.fold_recursive = function(combineFunc, base) {
if (this.isEmpty()) { // I added isEmpty, first, and rest, as above
return base;
}
else {
return combineFunc(
this.first(),
this.rest().fold_recursive(combineFunc, base));
}
}
Array.prototype.fold_iterative = function(combineFunc, tally) {
if (this.isEmpty()) {
return tally;
}
else {
return this.rest().fold_iterative(
combineFunc,
combineFunc(this.first(),
tally));
}
}
The first is straightforward recursion. If the list is empty, we’re done, so return the base value (zero, if we’re adding). Otherwise, combine the first value with whatever the rest of the items fold up to. [If you have trouble writing recursively, this is the canonical pattern you should probably follow: if done, do base case; else, do this element, then the rest of them.]
The second is a little different. You’ve got a starting base, the tally so far, and a combineFunc that folds each value into the tally. If the list is empty, we’re done, so return the tally. Otherwise, fold the first item into the tally for the rest of the list.
It the first, you hang around, waiting for the answer to the rest of the problem, before you add in your part of the sum. In the second, you push your part of the sum down into the next round of processing, so you don’t have to remember anything. When the answer comes back from the recursive call, it’ll already have your part of the sum in it.
[The first one is a “linear recursive process”, the second is “linear iterative process”, even though both are recursive procedures. If your interest is piqued, check out this SICP page, but it’s not needed for this article. For the rest of this post, I’ll be using the linear recursive version, because it’s conceptually clearer. Thanks to mfp for keeping me honest.]
Here’s how fold is used:
function add(a, b) { return a + b; } // A handy adding function
Array.prototype.sum_recursive = function() {
return this.fold_recursive(add, 0);
}
[1, 2, 3].sum_recursive(); >> 6
To sum the elements of an array, we want to fold the numbers together by add-ing them, starting at 0. Easy, isn’t it?
Here are two Ruby versions, based on fold_recursive…one that takes a function (called a “procedure object” in Ruby) as a parameter, one that takes a block:
class Array
def rest # We'll define rest, to keep the examples similar
self[1..-1]
end
def fold_w_proc(combineFunc, base)
if self.empty?
base
else
combineFunc.call( # "func.call(args)" instead of JavaScript's "func(args)"
self.first,
self.rest.fold_w_proc(
combineFunc,
base)
)
end
end
def fold_w_block(base, &combineFunc)
if self.empty?
base
else
combineFunc.call(
self.first,
self.rest.fold_w_block(
base,
&combineFunc)
)
end
end
def sum_w_proc
fold_w_proc(lambda { |a, b| a + b }, 0)
end
def sum_w_block
fold_w_block(0) { |a, b| a + b }
end
end
[1, 2, 3].sum_w_proc >> 6
[1, 2, 3].sum_w_block >> 6
Notice how similar fold_w_block and fold_w_proc are to the JavaScript fold_recursive. The thing that differentiates fold_w_block and fold_w_proc is how they’re used. The definitions themselves are nearly identical, except for the order of the parameters. Look at sum_w_proc and sum_w_block…sum_w_block is a bit clearer, isn’t it? But if you use blocks, you lose the ability to pass a function reference as a parameter.
Map
map looks a lot like fold.
Array.prototype.map = function(mapFunc) {
if (this.isEmpty()) {
return this;
}
else {
return [mapFunc(this.first())].concat(
this.rest().map(mapFunc));
}
}
function cube(i) { return i * i * i; }
[1, 2, 3].map(function(i) { return i * i; }); >> [1, 4, 9]
[1, 2, 3].map(cube); >> [1, 8, 18]
Again, it’s basic recursion…if we’re out of items, return the empty list (ie, this). Otherwise, make an array of the first mapped item, and concatenate it with the rest of the mapped items. Again, with JavaScript, you can pass your function in-line, or by reference.
Here’s a recursive definition of map in Ruby:
class Array
def map(&mapFunc)
if self.empty?
self
else
[mapFunc.call(self.first)] + self.rest.map(&mapFunc)
end
end
end
[1, 2, 3].map { |i| i * i } >> [1, 4, 9]
As before, calling map with a block certainly looks nicer than by passing in functions, but you lose the ability to define a function somewhere, and pass it in by name, like we did with cube in JavaScript.
Wrap-up
If you want to explore functional programming, both JavaScript and Ruby are good candidates. They both have their goods and bads. Up to now, I’ve only used Ruby, but JavaScript certainly has its benefits, and exposure to both balances out my understanding.
I hope that, if you were curious about functional programming before, this was a helpful read. If you’re a functional programmer, and I got something wrong, please let me know…I’m still learning. For instance, I now better understand how recursive processes differ from linear recursive processes.
