[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.

I’m teaching myself functional programming (FP). I first noticed it in Ruby, even though it’s been in JavaScript all along. I’m working my way through Structure and Interpretation of Computer Programs (SICP), and The Little Schemer books, so I’m learning Scheme and Lisp too.

When studying FP, I generally use JavaScript and Scheme. My FP examples here are usually in JavaScript:

• It’s available everywhere, and most programmers are comfortable reading it.
• It’s closer to Scheme than Ruby is, so the examples translate better. In fact, Douglas Crockford notes: “JavaScript has much in common with Scheme. It is a dynamic language. It has a flexible datatype (arrays) that can easily simulate s-expressions. And most importantly, functions are lambdas. Because of this deep similarity, all of the functions in The Little Schemer can be written in JavaScript.”

I include Ruby or Scheme, though, if it seems appropriate.

I often use the JavaScript Shell, or its big brother, the JavaScript Development environment, because I haven’t found or built a JavaScript REPL as nice as Dr. Scheme.

Performance

Most current JavaScript implementations are slow with recursion and closures…two cornerstones of functional programming.

I don’t worry about this, because my examples are not meant to be dropped into production systems without thought and testing. I write production-ready code at work; here, I play and explore. We do use some functional JavaScript where I work, but it’s where the performance is acceptable, and the imperative alternative would be too unwieldly.

History seems to show that performance is a short-term concern, and better programming techniques are a long-term concern. It also seems that there are no inherent reasons JavaScript is slow; more performant implementations may be in our future.

Why not Haskell or Erlang?

…or OCaml, Scala, F#, Clojure? I’m getting there. SICP and The Little Schemer books are more than enough for me right now.

Continuations and continuation-passing style (CPS) are introduced in The Little Schemer, chapter 8, using collectors: functions that collect values, through being repeatedly redefined. It was a tough chapter for me, but the idea is simple once you get it, so I’d like to leave some help for others. I’ll use Ruby for the examples, with some JavaScript and Scheme at the end.

In languages with first-class functions, you can assign functions to variables, and re-assign those variables. Consider this Ruby example:

func = lambda { |x| puts x }

['a', 'b', 'c'].each { |ch|
    old_func = func
    func = lambda { |x| old_func[x + ch] }
}

func['d']  #=> prints 'dcba'

By re-defining func in terms of old_func, we’re building up a recursive computation. It’s like normal recursion, but approached from the other side — without explicit definitions. Since a Ruby function is a closure, it remembers the value of the variables in scope when it was created; each layer of this recursion holds its own value for ch and old_func. When we call the last func, it sees ch = ‘c’ and x = ‘d’. It concatenates them, and calls its version of old_func…which sees x = ‘dc’ and ch = ‘b’, concatenates them, and passes it to its old_func, and so on.In fact, if we wrote it like this, the execution of all those lambdas would be exactly the same:

func_puts = lambda { |x| puts x }
func_add_a = lambda { |x| func_puts[x + 'a'] }
func_add_b = lambda { |x| func_add_a[x + 'b'] }
func_add_c = lambda { |x| func_add_b[x + 'c'] }
func_add_c['d']  #=> prints 'dcba'

We could calculate factorials this way:

def factorial(n, func)
    if n == 1
        func[1]
    else
        factorial(n - 1, lambda { |i| func[i * n] })
    end
end
factorial(3, lambda { |fact| puts fact })  #=> prints 6

1. On the first call to factorial, n = 3, and func just prints its argument. But func isn’t called yet…since n isn’t 1, we recurse with n - 1 = 2, and a new function that calls func with its argument i times 3.
2. On the recurse, n = 2, and func calls the original printer func with its argument i times 3. Since n still isn’t 1, we recurse again, with n - 1 = 1, and a new function that calls our func with its argument i times 2.
3. On the final round, n = 1, so we (finally!) call func with 1, which…
4. …calls the previous func with 1 * 2, which…
5. …calls the original func with (1 * 2) * 3, which…
6. prints 6.

As factorial recurses, it builds up a recursive tower of func calls. In factorial’s base case, the last (and outermost) func is called, and we begin to climb down the func tower, to its bottom floor, the original func. It’s recursion in two directions.

In case Ruby isn’t your favorite language, here are versions in JavaScript and Scheme:

function factorial(n, func) {
    if (n == 1)
        func(1)
    else
        factorial(n - 1, function(i) {
            func(n * i)
        });
}

factorial(3, function(fact) { print(fact) })

; Too bad WordPress doesn't format Scheme or Lisp!
(define factorial
  (lambda (n func)
    (cond ((= n 1) (func 1))
          (else (factorial (- n 1)
                           (lambda (i) (func (* n i))))))))

; Here, the original func is just an identity function.
(factorial 4 (lambda (fact) fact))

Once this is clear, you can see many other applications:

• You could find all the even numbers in a list: instead of passing a number to func, pass the list of even numbers, and add each even number in.
• You could separate the numbers into evens and odds: instead of passing just one list to func, pass two lists, for evens and odds, and add each number to the correct list.
• You could separate any list of items by any criteria: instead of hard-coding “is even?” into the function, pass a predicate function. (Maybe you want to extract all occurrences of ‘tuna’ from a list of words.)

That should be enough of a warm-up for chapter 8. See you in chapter 9, when they derive the Y-combinator!

One pretty well-know idiom in Ruby, and Facets, is Symbol.to_proc. It lets you turn these:

[1, 2, 3].map { |num| num.next }  #=> [2, 3, 4]

%w[alpha beta gamma].map { |word| word.upcase }
#=> ["ALPHA", "BETA", "GAMMA"]

…into these:

[1, 2, 3].map(&:next)
%w[alpha beta gamma].map(&:upcase)

It’s a nice little trick, though it’s not to everyone’s taste. If you’re already comfortable with Symbol.to_proc, you can skip down to the Class.to_proc section. But if you’re not, it’s worth a minute of your attention to learn it. Read on…

How it’s done

When a method takes a block, you can call yield, to run the block.

def with_a_block(a_param)
    yield
end
with_a_block('param') {
    puts 'in the block'
}

Or, you can name the block as the last parameter to the method, and put an ampersand in front of it. The ampersand makes ruby convert the block to a procedure, by calling to_proc on it. (So any object with a to_proc method can work this way, if you want.) This example works just like the last one:

def named_block(a_param, &blk)
    blk.call
end
named_block('my_param') {
    puts 'in the named block'
}

Symbol’s to_proc method creates a procedure that takes one argument, and sends the symbol to it. Sending a symbol to an object is the same as calling a method on it: object.send(:method) works the same as object.method. In the earlier upcase example, each word is passed to a procedure that calls upcase on it, giving us a list of uppercased strings.

&:upcase
# becomes...
lambda { |obj|
    obj.send(:upcase)
}
# or...
lambda { |obj|
    obj.upcase
}

Class.to_proc

So Symbol.to_proc creates a function that takes an argument, and calls that method on it. Class.to_proc creates a function that passes its argument to its constructor, yielding an instance of itself. This is a welcome addition to the to_proc family.

require 'facets'

class Person
    def initialize(name)
        @name = name
    end
end
names = %w[mickey minney goofy]
characters = names.map(&Person)

puts characters.inspect

&Person
# becomes...
lambda { |obj|
    Person.new(obj)
}

Why it’s nice

• It’s fewer characters — it semantically compresses your code.
• It lets you think, makes you think, on a higher level. You think about operations on your data, rather than handling one item at a time. It raises your level of thinking.
• It works with first-class functions, which are worth understanding. They give you new ways to elegantly solve some problems (well, new to some audiences). They’re not fringe anymore — they’ve been in C# since v2.0.

Recently, I talked about a faster, cheaper way to calculate Fibonacci numbers. One of the optimizations I made was to remember the value of each Fibonacci number: since F(7) is always 13, instead of recalculating it each time N=7, we can stuff 7 -> 13 into a look-up table for future reference. The function builds up a cheat-sheet, to avoid doing the re-work. It remembers.

This is called memoization, and it’s a nice way to trade memory for performance. But it only works when the function always returns the same answer for a given set of arguments — otherwise it’s first-in wins, forever. This property of a function, returning the same answer for the same args, is called referential transparency.

A Sample Implementation

There are lots of ways you could memoize a function. Hash tables are a natural choice, since they map a key to a value, just like functions map arguments to a value. Even if you implement it differently, a hash table is a good working model for memoization.

Let’s briefly consider factorials. The regular version:

class Unmemoized
    def factorial(n)
        puts n
        if n < 1
            1
        else
            n * factorial(n-1)
        end
    end
end

unmemoized = Unmemoized.new

5.downto(1) { |i| puts "\t#{unmemoized.factorial(i)}" }

…and the memoized version:

class Memoized
    attr_reader :factorial_memo
    def initialize
        @factorial_memo = {}
    end

    def factorial(n)
        puts n
        unless @factorial_memo.has_key? n
            if n < 1
                @factorial_memo[n] = 1
            else
                @factorial_memo[n] = n * factorial(n-1)
            end
        end

        @factorial_memo[n]
    end
end

memoized = Memoized.new

5.downto(1) { |i| puts "\t#{memoized.factorial(i)}" }

puts memoized.factorial_memo.inspect

Printing the hashtable is especially telling: {5=>120, 0=>1, 1=>1, 2=>2, 3=>6, 4=>24} It reads like a look-up table for factorials.

Memoization in Facets

As relatively easy as that example is, it has its drawbacks: we need to track our previous results in a separate variable, the memoization code is mixed up with the actual calculation (the part we care about), we can’t easily use it with other functions, and the pattern only works for functions of one argument. Facets makes memoization trivial, and removes all these issues.

require 'facets/memoize'

class FacetsMemoized
    def factorial(n)
        puts n
        if n < 1
            1
        else
            n * factorial(n-1)
        end
    end

    memoize :factorial # <= HINT
end

facets_memoized = FacetsMemoized.new

5.downto(1) { |i| puts "\t#{facets_memoized.factorial(i)}" }

In case you missed it, this is just like Unmemoized above, except we added line 13, memoize :factorial…that’s it. Just like attr_reader and friends, you can pass a list of symbols to memoize, and it’ll work on functions with any number of arguments:

require 'facets/memoize'

class MemoizedMath
    def add(n, m)
        n + m
    end
    def mult(n, m)
        n * m
    end
    memoize :add, :mult
end

When You Might Use Memoization, and What to Avoid

There are a number of places where this is useful: calculating a value by successive approximation, finding the path to the root node in an immutable tree structure, finding the Nth number in a recursively-defined series, even simple derived values (like ‘abc’.upcase). In general, a function is a good candidate if it only looks at its arguments (no global, class, or member variables, no files or databases) — especially if those arguments are immutable.

Relying on side-effects (printing to standard out, writing to a database or file, or updating a variable) in memoized methods is a bad idea: they’ll only happen the first time your method is called with those arguments, which is probably not what you intend. (Unless you’re printing the arguments to illustrate how memoizing works.) On the other hand, relying on side-effects is generally a bad idea anyway. Even if you don’t use a functional programming language, you can still benefit from minimizing state changes.

Further Reading

If memoization sounds interesting to you, you might like Oliver Steele’s article about memoizing JavaScript functions. If you’re curious about immutability, you might like this Joshua Bloch interview. If you’re interested in functional programming, there are worse places to start than the excellent Structure and Interpretation of Computer Programs. And of course, there’s more where that came from, in Ruby Facets.