Implementing “map” with “reduce”, in Ruby and Python

This is another installment in my “reduce” series of posts, aimed at helping programmers understand this function, with examples in both Ruby and Python.  So far, we have seen how we can build a number of different types of data structures — integers, strings, arrays, and hashes — using “reduce”.  But the really interesting use of “reduce,” in my mind, is as a way to implement “map” and “filter,” two classic functions from the functional-programming world.  In this post, I show how to implement “map” in both Ruby and Python.

First, let’s remember what “map” does: It takes a sequence, and applies a function to that sequence, one element at a time. The output of applying that function on each element produces a sequence of values, which we then get back from “map”.   In Ruby, we can thus say:

[1,2,3,4,5].map {|n| n*n}

which produces the array:

[1,4,9,16,25]

In Ruby, any block that you want to pass is fair game.  The block takes a single parameter, the current element of the enumerable that should be transformed. Whatever the block returns is put into the output array; because nearly everything in Ruby is an expression, just about anything is fair game.  Moreover, the output array will always consist of the same number of elements the input array.  So if you run Enumerable#map on an array of 15 items, you can be sure that you’ll get a new, anonymous array of 15 items.  The value of each of these items will depend on what the block emits.

If we want to implement “map” using “reduce,” we know that we need to invoke a block once per element of the enumerable.  The block should add one element to the end of an array that we have created.  The element that we add to the array should be the result of invoking a method on the current element.

For example, if we want to use “reduce” to implement the “map” example from above, in which we get the squares of the input numbers, we could do the following:

[1,2,3,4,5].reduce([]) {|total, current| total << current * current}

and sure enough, we get the following output:

[1, 4, 9, 16, 25]

If squaring numbers were the only thing we were interested in doing, we could write a “mymap” method that would do that:

def mymap(enumerable)
  enumerable.reduce([]) {|total, current| total << current * current}
end

mymap([1,2,3,4,5])

And sure enough, we get the array of squared numbers.  But as you can imagine, this implementation of map is somewhat lacking… we would really like to be able to pass a block, just as we can do with the built-in Enumerable#map method.  In Ruby, we can do this very easily by passing a block to our method, and then yielding to it (i.e., invoking it) once per iteration within the “reduce”.  For example:

def mymap(enumerable)
  enumerable.reduce([]) {|total, current| total << yield(current)}
end

mymap([1,2,3,4,5]) {|n| n*n}
=> [1, 4, 9, 16, 25]

mymap([1,2,3,4,5]) {|n| (n * 30).to_s}
=> ["30", "60", "90", "120", "150"]

Not bad!  Using “reduce”, we’ve managed to implement a version of “map”.  That’s pretty snazzy, if you ask me.

We can do almost exactly the same thing in Python.  Python doesn’t have Ruby-style blocks, but it does have functions — both named functions and anonymous ones created with “lambda” — that can be passed easily as parameters, and then invoked using parentheses. The Python version of “mymap” would thus look something like this:

def mymap(sequence, f):
  return reduce(lambda total, current: total + [f(current)], sequence, [])

In other words, our function takes two parameters, a sequence and a function. We then build the resulting list, one element at a time, based on the output from invoking our “f” function on each element in sequence.  It turns out that “map” is not that different from our use of “reduce” to build lists; the only difference, in fact, is that we’re letting the user pass us a function, which we then invoke on the current item.

It turns out, then, that implementing “map” isn’t so hard or mysterious!  In the next installment of this series, we’ll see how to implement the “filter” function (called “select” or “find_all” in Ruby), another staple of functional programming.