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

We’re nearly at the end of my tour of the “reduce” function in Ruby and Python.  Just as I showed in the previous installment how we can implement the “map” function using “reduce”, I want to show how we can implement another functional-programming standard, “filter”, using “reduce” as well.  As before, I’ll show examples in both Ruby and Python.

Whereas “map” transforms each element of its input, but returns a value for each one, “filter” doesn’t change its inputs at all — but it does only selectively return them. The combination of “map” and “filter” is a classic and powerful one.  While Python still does include the “map” and “filter” functions, they are more usually expressed using list comprehensions.  The “map” part is the left-hand-side of the list comprehension, defining the transformation.  The “filter” part is the (optional) right-hand side of the comprehension, indicating when a value should be placed in the output.

Here is a use of “filter” to keep only odd numbers (taking advantage of the fact that in Python, 0 is a false value, and % is the modulus operator on integers):

>>> filter(lambda x: x%2, range(10))
[1, 3, 5, 7, 9]

It turns out that we can use “reduce” to implement our own version of “filter”, which does the same thing. Once again, we’ll define a function that takes two parameters, a sequence and a function:

def myfilter(sequence, f):
 return reduce(lambda total, current: total + ([current] if f(current) else []),
               sequence,
               [])

In other words: Our function invokes reduce, initializing it with an empty list ([]). We go over every element of “sequence”; for each element, we invoke the user-supplied function, f, passing “current” as a parameter.  We always return “total”, which is the list that we have created so far.  The question is whether we also want to return “current”, and that depends on whether f(current) returns True or False.  If it returns True, then we add “current” to the accumulated list.  If it returns False, then we add [] (i.e., the empty list) to the list. If we again want to filter a list of numbers, such that we get only the odd ones, we can now say:

>>> myfilter(range(10), lambda x: x%2)
[1, 3, 5, 7, 9]

What can be tricky for many newcomers to Python and functional programming is that the implementation of “myfilter” involves a lambda (i.e., anonymous function) in our invocation of “reduce”, but also a function (often defined as a lambda) that is passed to “myfilter” by the user.  I’ve found in my teaching that “lambda” tends to surprise and confuse many people, and two lambda expressions in the same place can really be a cognitive burden for newcomers.

Now that we’ve implemented a version of “filter” in Python, let’s turn to Ruby.  Here, as with “map”, we’re not going to pass a function (method) as a parameter. Rather, we’ll pass a block to our “myfilter” method, and then yield to the block whenever we want to invoke it.  For example:

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

(By the way, “filter” is traditionally called both “select” and “find_all” in Ruby circles.)  Notice that there are two blocks involved here: Enumerable#reduce invokes a block for each element of “enumerable” over which it iterates.  And then within that block, we yield to the block passed to “myfilter”, to check and see if the current element should be shared.

We can then invoke “myfilter” as follows:

e = (1..10).to_a
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

myfilter(e) {|n| n.even?}
=> [2, 4, 6, 8, 10]

Sure enough, we’ve managed to create our own version of “filter”, just as we were able to do for “map”.

Next time: The exciting conclusion of our tour of the “reduce” function.  Same reduce-time, same reduce-channel!

Leave a Reply

Your email address will not be published. Required fields are marked *

ninety nine − ninety seven =