I teach Ruby and Python to a lot of people — in formal courses, and in one-on-one pairing sessions, both online and in person.  I’ve found that for many people, the whole notion of functional programming seems strange and difficult, as well as something of a waste of time.  After all, if you have objects, why would you need functional programming?

The answer, of course, is that no single paradigm has all of the answers; each has its strengths and weaknesses.  Understanding how to use them together can provide great benefits.  As a result, I spend time when teaching both Ruby and Python on the basics of functional programming, and then the various functions and methods that each language provides in this area.

Of these, the function that most often causes people to wrinkle their noses and/or get confused is “reduce”.  And to be honest, I often tell students in my classes that “reduce” is one of those functions that is incredibly powerful and clever, but for which you sometimes need to wait in order to find a use case.  I decided to explore some use cases, and ways in which “reduce” could be used — and I hope that these have been useful.

To summarize, here are the posts that I wrote on this topic:

• Introduction to “reduce”
• Calculating Scrabble scores with “reduce”
• Implementing “min” and “max” with “reduce”
• Creating collections with “reduce”
• Python dictionaries with “reduce”
• Ruby hashes with “reduce”
• Implementing “map” with “reduce”
• Implementing “filter” with “reduce”

I hope that this series has been useful and interesting, and would appreciate hearing ideas for additional deep-dives into areas of Python, Ruby, or programming in general.  What subjects do you find confusing?  What methods do you think are somewhat useless?  Let me know, and I’ll try to address them in future blog posts!

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!

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.

In the first few parts of this series (first, second, and third), I introduced the “reduce” function, and showed how it can be used in a number of ways. However, in all of the examples we have seen so far, the output from our invocations of “reduce” were integers or strings. If we reduce with a “sum” function, then we get an integer representing the sum of all integers.  If we reduce over a measurement, such as the size of an integer or the length of a string, we can implement “min” or “max”.

Another interesting and clever thing that we can do with “reduce” is to create an array (in Ruby) or list (in Python).  Think of it this way: The output of each iteration of “reduce”, which is then passed to the next iteration, can be any data structure we wish. If the output from the iteration is an array, then that’s what will be passed to the next iteration.

In other words, we can use “reduce” to build up an array, with each iteration emitting that same array, perhaps with additional elements added to it.  For example, I can create a new array whose contents are identical to the original one on which “reduce” was invoked:

['a', 'b', 'c'].reduce([]) {|output, current| output << current }

By adding each element to the beginning, I can reverse the array:

['a', 'b', 'c'].reduce([]) {|output, current| output.unshift(current) }

I can create a nested array, too:

['a', 'b', 'c'].reduce([]) {|output, current| output << [current, current] }

“reduce” is thus a great way to create an array, building it up piece by piece.  True, we need to pass “reduce” an empty array as a parameter, and then each iteration needs to return the current value of the array.  But other than that, we can add whatever we want to the array, and modify it in whatever ways we want.  If I want to do something more complex than the above, or if I want to be able to debug individual lines of my block, I can even use do-end, thus spreading the block across multiple lines.  (And yes, I know about the late Jim Weirich’s great suggestion, to use curly braces for returning values.  But if you’re going to have multiple lines in your block, then do-end still rings truer for me.)

Let’s see how we can do the same thing in Python.  First, we can return a list:

reduce(lambda output, current: output + [current], 'abc', [])

We start (using the optional final argument) with an empty list.  Then, in each iteration, we take the current element, turn it into a one-element list, and then append it to the existing list.  Note that we cannot use list.append to add the current element, because list.append returns None, like many other methods that change mutable objects in Python.

Using “reduce” to reverse the list is just as easy, by reversing the order in which we add things to the list:

reduce(lambda output, current: [current] + output, 'abc', [])

Finally, if we want to return a list of lists, we can do that fairly easily, just add a list of lists:

reduce(lambda output, current: output + [[current, current]], 'abc', [])

As you can see, “reduce” makes it possible for us to, in a single line, create a collection based on another set of inputs.  The output can contain any types that we want; in these simple examples, we created lists of strings.  But we could create lists of dictionaries, or of more complex objects, just as easily.

In the next installment, we’ll see how to create hashes/dictionaries using reduce.

This is the third installment of my “reduce” series of blog posts.  For the first, see here, and for the second, see here.

If you have been reading this series, then you know that “reduce” can be used to sum numbers, or to calculate scores.  In that sense, “reduce” justifies its name; we’re invoking a function repeatedly on each element of a collection, boiling the collection down to its essense, as defined by our function.

But “reduce” can also be used to to other, more interesting things.  One of them, mentioned in the Ruby documentation, isn’t an obvious candidate for beginners with “reduce”, namely implementing “min” and “max”.

In a world without functional programming or reduce, we could implement a “min” function as follows in Ruby:

def mymin(items)
  output = items[0]           # Assume the first item is the smallest
  items[1..-1].each do |item| # Iterate through all remaining items
    if item < output
      output = item           # This item is smaller, so keep it
    end
  end
  output                      # So far, this is the smallest we've seen
end

The definition, if you’re somewhat new to Ruby, works as follows: The “min” function takes an enumerable sequence of items. We assume that the first item is the smallest one, simply to make life easier for ourselves.  We then iterate over the remaining items, checking to see if the current one is smaller than the current winner.  Each iteration thus leaves “output” with its existing value, or replaces it with something smaller.

Now, the above code works just fine — but it’s a bit long and inelegant just to find the minimum value in an enumerable.  After all, it should be possible to implement the same algorithm we we used above in the implementation of “mymin”, but somehow more elegantly and concisely.

That’s where “reduce” comes in.  We saw in an earlier blog post that when we use “reduce” to sum the numbers in a collection, is sort of like saying ((((1+2)+3)+4)+5).  Well, let’s say that we had a function “smaller” that would return the smaller of two numbers.  Then, we could use “reduce” in the following way:

smaller(smaller(smaller(smaller(1,2),3),4),5)

Oh, is that hard to read?  Yeah, I thought so.  So instead, we can do the following:

items.reduce {|smallest, current| smaller(smallest, current) }

Each time “reduce” invokes our block, it keeps the smaller of its two parameters.  The first parameter, which I’ve here called “smallest”, contains the smallest value that we’ve seen so far. The second parameter, “current”, contains the current value from the collection.

That one line certainly looks nicer than our original implementation of “mymin”, I think. There’s just one problem: We haven’t defined any “smaller” method!  Fortunately, we can use Ruby’s ternary operator to have a tiny, one-line if-then-else statement that does the same thing.  In other words:

items.reduce {|smallest, current| smallest < current ? smallest : current }

The moment you realize that “reduce” can be used to hold onto only one of the previous values, you begin to see the opportunities and possibilities that it offers. For example, we can find the shortest or longest word in an array of words:

words = 'This is a sample sentence'.split
words.reduce {|shortest, current| (shortest.size < current.size) ? shortest : current }
=> "a"

words.reduce {|longest, current| (longest.size > current.size) ? longest : current }
=> "sentence"

Now, can we do the same thing in Python?  The builtin “reduce” function works similarly to Ruby’s Enumerate#reduce, as we’ve seen in previous posts I wrote on the subject.  However, the function that we pass to Python’s “reduce” is more limited than a Ruby block, especially if we use a lambda (i.e., anonymous function).

However, we do have a trick up our sleeve: Python provides an analogous version of Ruby’s ternary operator, which is meant for precisely these occasions.  I generally tell people to avoid this operator completely, because it causes more problems and confusion than necessary, and probably means that you’re doing something that you shouldn’t be in Python.  It works as follows:

>>> x = 'a'
>>> is_an_a = "yes" if x == 'a' else "no"

>>> is_an_a
'yes'

The oddest thing for me about this form of “if” in Python is that the condition is in the middle of the line.  It’s not the postfix “if” of Perl and Ruby, and it’s not the prefix “if” that everyone is used to, but something else entirely.  And as such, it’s usually a bad idea to have in your code.  But right now, it fits perfectly.

Here, then, is a version of “min” in Python, using “reduce”:

>>> items = [5,-5,10,1,100,-20,30]
>>> reduce(lambda smallest, current: smallest if (smallest < current) else current, items)
-20

And sure enough, we get the lowest value!  Next time, we’ll produce even more complex outputs, with more complex data structures.

This is the second installment of my series of blog posts on the “reduce” function/method.  For an introduction, see here.

I love to play Scrabble — or more commonly nowadays, I play Words with Friends on my phone. (I often say that the game should instead be called, “Words with people who used to be your friends,” given the competition that can result.)  The game, if you’re not familiar with it, is simple enough to understand: You choose seven English letters at a time from a bag or pool of letters.  Each letter has a different point value.  Your aim is to create, with your seven letters, the highest-scoring word that you can in each turn.

Fine, it’s a bit more complex than that: Your word needs to hook onto an existing word or letter, and you can get bonus points by completing more than one word, and there are squares which multiply your score, by doubling or tripling the value of an individual letter or the entire word.  I’m going to ignore all of these rules for now.

Let’s say that I want to write a Ruby program that will calculate the score of a given word in Scrabble. How can I do that?

Before I can begin, I’m going to need to need a list of the points that you get for each letter.  Because we’re dealing with a mapping between two values — a letter and its points — the easiest solution would be a hash:

points = {'a'=> 1, 'b'=> 3, 'c'=> 3, 'd'=> 2, 'e'=> 1, 'f'=> 4, 'g'=> 2, 'h'=>
 4, 'i'=> 1, 'j'=> 8, 'k'=> 5, 'l'=> 1, 'm'=> 3, 'n'=> 1, 'o'=> 1, 'p'=> 3,
 'q'=> 10, 'r'=> 1, 's'=> 1, 't'=> 1, 'u'=> 1, 'v'=> 4, 'w'=> 4, 'x'=> 8, 'y'=>
 4, 'z'=> 10}

Once we’ve defined our “points” hash, we can start calculating the number of points that we’ll get for a given word.  If you aren’t familiar with “reduce”, but have been programming in Ruby for at least a short while, you’ll probably realize that this is easily accomplished with a loop.  That is, we can iterate over each letter in the string, getting the point value for that letter, and adding it to the total.  For example, we could do something like this:

word = 'encyclopedia'
total = 0 
word.each_char do |letter|
  total += points[letter]
end

After the above loop, we’ll find that the total score is 22 points.  That’s fine, and it’ll work… but by using “reduce”, we can do the same thing in a single line:

word.split('').reduce(0) {|total, current| total + points[current]}

Now, how does the above work? First, it takes the string “word”, and turns it into an array, in which each letter is an element.  Then, we use “reduce” to calculate a score: Since it’s a numeric score, we’ll initialize the total with 0.  Then, for each letter in our word, we add the number of points associated with that word to our total.

To do the same thing in Python will require surprisingly similar code. First, we create a dictionary:

points = {'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4, 'g': 2, 'h':
 4, 'i': 1, 'j': 8, 'k': 5, 'l': 1, 'm': 3, 'n': 1, 'o': 1, 'p': 3,
 'q': 10, 'r': 1, 's': 1, 't': 1, 'u': 1, 'v': 4, 'w': 4, 'x': 8, 'y':
 4, 'z': 10}

Then we run reduce in a similar way. Because strings in Python are sequences, we don’t need to turn our word into an an array before iterating over it; we can invoke “reduce” directly on the string:

>>> word = 'encyclopedia'
>>> reduce(lambda total, current: total + points[current], word, 0)
22

This is a simple demonstration of where “reduce” can be useful. I’m looking to apply the same operation on the elements of a sequence of data, adding the latest value to the total.  When I get to the end, I’d like to see what has accumulated so far.

In the next installment, we’ll see how we can use “reduce” to implement some other functions that we wouldn’t normally associate with functional programming, let alone with something called “reduce”.