Tag: Enumerating Enumerable

The next method I’m going to cover in Enumerating Enumerable — the series of articles in which I try to do a better job of documenting Ruby’s Enumerable module than Ruby-Doc.org does — is inject, a.k.a. reduce. Not only is it one of the trickiest methods to explain, it’s also one of the cornerstones of functional programming. I thought that I’d take a little time to explain what the function does.

inject

The term inject comes from Smalltalk and isn’t terribly descriptive. I remember reading the documentation for it and being all confused until I saw some examples. I then realized that I’d seen this function before, but under two different names.

reduce

Burning Man 1999: gratuitous nudity and even more gratuitous accordion!

The second name by which I encountered this function is reduce, and it was at Burning Man 1999. I was to start a new job the week after Burning Man, and I had to learn at least some basic Python by then. So along with my camping gear, accordion and a kilo of candy for barter, I also brought my laptop (a 233Mhz Toshiba Sattelite with a whopping 96MB of RAM) and O’Reilly’s Learning Python and noodled during the downtime (early morning and afternoon) on Python 1.6. When I got to covering the reduce function, I was confused until I saw some examples, after which I realized that I’d seen that function before, but under a different name.

(You may have also heard of reduce through Google’s much-vaunted MapReduce programming model.)

fold

The first name by which I encountered this function is fold, or more specifically, “fold left” or “foldl”, and it was at the “Programming Paradigms” course I took at Crazy Go Nuts University. “Programming Paradigms” was a second-year course and had the reputation of being the most difficult course in the computer science curriculum. The intended purpose of this course was to provide students with an introduction to functional programming (these days, they use Haskell and Prolog, back then, it was Miranda). Its actual effect was to make most of the students swear off functional programming for the rest of their lives.

In spite of the trauma from this course, I ended up remembering a lot from it that I was able to apply, first to Python and now to Ruby. One of these things is a cute little trick for cememnting in your mind what fold does.

What Ruby-doc.org Says

Before I cover that cute little trick, let’s take a look at what Ruby-doc.org’s documentation has to say about Enumerable‘s inject method.

One thing you’ll find at Ruby-doc.org is that as of Ruby 1.8.7 and later, inject gained a synonym: the more familiar term reduce.

As for the description of the inject/reduce method, I don’t find it terribly helpful:

Combines all elements of enum by applying a binary operation, specified by a block or a symbol that names a method or operator.

If you specify a block, then for each element in enum<i> the block is passed an accumulator value (<i>memo) and the element. If you specify a symbol instead, then each element in the collection will be passed to the named method of memo. In either case, the result becomes the new value for memo. At the end of the iteration, the final value of memo is the return value fo the method.

If you do not explicitly specify an initial value for memo, then uses the first element of collection is used as the initial value of memo.

(Yes, those stray <i> tags are part of the text of the description for inject. Hopefully they’ll fix that soon.)

This confusing text becomes a little clearer with some examples. The most typical example of inject/reduce/fold in action is the classic “compute the sum of the numbers in this range or array” problem. There are a number of approaches you can take in Ruby, all of which use inject/reduce:

(1..8).reduce(:+)
=> 36

(1..8).reduce {|sum, number| sum += number}
=> 36

(1..8).reduce(0) {|sum, number| sum += number}
=> 36

The reduce method takes some kind of operation and applies it across the enumerable to yield a single result. In this case, the operation is addition.

Explaining how that operation is applied is a little trickier, but I do just that in the next section.

Demonstrating inject / reduce / fold With a Piece of Paper and Literal Folding

To explain what’s happening in the code above, I’m going to do use a piece of paper. I’ve folded it into 8 even sections and then numbered each section, as shown in the photo below:

Think of the paper as the range (1..8). We’re now going to compute the sum of the numbers in this range, step by step, using a literal fold — that is, by folding the paper. I’m going to start folding from the left side of the paper, and when I do, I’m going to add the numbers that I’m folding into each other.

In the first fold, I’m folding the number 1 onto the number 2. Adding these two numbers yields 3, which I write on the back of the fold:

For the second fold, I fold the first number 3 onto the second number 3. The sum of these two numbers is 6, and I write that on the back of the resulting fold:

I fold again: this time, it’s the number 6 onto the number 4, the sum of which is 10. I write that number down on the resulting fold:

Next, I fold 10 onto 5, yielding the number 15:

I then fold 15 onto 6, which gives me 21:

Next comes 21 folded onto 7, which makes for a sum of 28:

And finally, 28 folded onto 8, which gives us a final total of 36.

And there you have it: a paper-based explanation of inject/reduce/fold, as well as why I often refer to the operation as “folding”.

Once again, it’s Enumerating Enumerable time! This is the latest in my series of articles where I set out to make better documentation for Ruby’s Enumerable module than Ruby-Doc.org’s. In this installment — the seventeenth in the series — I cover the group_by method.

In case you missed any of the previous articles, they’re listed and linked below:

1. all?
2. any?
3. collect / map
4. count
5. cycle
6. detect / find
7. drop
8. drop_while
9. each_cons
10. each_slice
11. each_with_index
12. entries / to_a
13. find_all / select
14. find_index
15. first
16. grep

Enumerable#group_by Quick Summary

Enumerable#group_by and Arrays

When used on an array, group_by iterates through the array, passing each element to to the block. The result value of the block is the group into which the element will be placed.

Example 1

For the first example, I’ll use some code similar to the example given in Ruby-doc.org’s writeup of group_by:

(0..15).group_by {|number| number % 3}
=> {0=>[0, 3, 6, 9, 12, 15], 1=>[1, 4, 7, 10, 13], 2=>[2, 5, 8, 11, 14]}

In the code above, the numbers 0 through 15 are passed to the block, which receives each number as the parameter number. The group that each number is placed into is determined by the result value of the block, number % 3, whose result can be one of 0, 1 or 2. This means that:

• The resulting hash will have three groups, represented by the keys 0, 1 and 2
• The key 0‘s corresponding value is an array containing the numbers in the range (0..15) that are evenly divisible by 3 (i.e. the numbers for which number % 3 is 0.
• The key 1‘s corresponding value is an array containing the numbers in the range (0..15) that when divided by 3 leave a remainder of 1 (i.e. the numbers for which number % 3 is 1.
• The key 2‘s corresponding value is an array containing the numbers in the range (0..15) that when divided by 3 leave a remainder of 2 (i.e. the numbers for which number % 3 is 2.

Example 2

In the first example, the keys in the resulting hash are the same type as the values in the array whose contents we’re grouping. In this example, I’ll show that the keys in the resulting hash don’t have to be the same type as the values in the array.

simpsons = %w(Homer Marge Bart Lisa Abraham Herb)
=> ["Homer", "Marge", "Bart", "Lisa", "Abraham", "Herb"]

simpsons.group_by{|simpson| simpson.length}
=> {5=>["Homer", "Marge"], 4=>["Bart", "Lisa", "Herb"], 7=>["Abraham"]}

In the code above, each Simpson name is passed to the block, which receives it as the parameter simpson. The block’s result is the length of simpson, and this result is the group into which the name will go.

In the resulting hash:

• Note that the keys are integers while the names in the groups are strings.
• The key 5‘s array contains those names in Simpsons that are 5
  characters in length.
• The key 4‘s array contains those names in Simpsons that are 4 characters in length.
• The key 7‘s array contains those names in Simpsons that are 7 characters in length.

Example 3

In the previous two examples, the keys for the resulting array were calculated from the values in the initial array. In this example, I’ll demonstrate that the keys for the groupings can be determined in a completely arbitrary fashion that has nothing to do with the values:

# Put the Simpsons into randomly determined groups
simpsons.group_by{rand(3) + 1}
=> {3=>["Homer", "Bart", "Abraham", "Herb"], 1=>["Marge", "Lisa"]}

# Let's try that again. The results are very likely to be different:
simpsons.group_by{rand(3) + 1}
=> {1=>["Homer", "Bart"], 2=>["Marge", "Lisa", "Herb"], 3=>["Abraham"]}

# One more time!
simpsons.group_by{rand(3) + 1}
=> {2=>["Homer", "Bart", "Lisa"], 3=>["Marge", "Herb"], 1=>["Abraham"]}

Enumerable#group_by and Hashes

When used on a hash, group_by passes each key/value pair in the hash to the block, which you can “catch” as either:

1. A two-element array, with the key as element 0 and its corresponding value as element 1, or
2. Two separate items, with the key as the first item and its corresponding value as the second item.

Example 1

In this example, we’ll group the cast of Family Guy by the item that they’re bringing to a potluck dinner:

potluck = {"Peter" => "lasagna",
           "Lois"  => "potato salad",
           "Chris" => "lasagna",
           "Meg"   => "brownies",
           "Stewie" => "chateaubriand",
           "Brian" => "potato salad",
           "Evil Monkey" => "potato salad"}
=> {"Peter"=>"lasagna", "Lois"=>"potato salad", "Chris"=>"lasagna", "Meg"=>"brownies",
"Stewie"=>"chateaubriand", "Brian"=>"potato salad", "Evil Monkey"=>"potato salad"}

# Here's one way to do it:
potluck.group_by{|person, bringing| bringing}
=> {"lasagna"=>[["Peter", "lasagna"], ["Chris", "lasagna"]], "potato salad"=>[["Lois", "potato salad"],
["Brian", "potato salad"], ["Evil Monkey", "potato salad"]], "brownies"=>[["Meg", "brownies"]],
"chateaubriand"=>[["Stewie", "chateaubriand"]]}

# Here's another way to do it:
potluck.group_by{|person| person[1]}
=> {"lasagna"=>[["Peter", "lasagna"], ["Chris", "lasagna"]], "potato salad"=>[["Lois", "potato salad"],
["Brian", "potato salad"], ["Evil Monkey", "potato salad"]], "brownies"=>[["Meg", "brownies"]],
"chateaubriand"=>[["Stewie", "chateaubriand"]]}

Example 2

In the previous example, the groupings were based on a calculation performed on the objects in the original hash. In this example, the groupings will be random: a random number generator will determine whose car each potluck attendee will ride to the potluck dinner:

potluck.group_by {[:peters_car, :quagmires_car, :clevelands_car][rand(3)]}
=> {:peters_car=>[["Peter", "lasagna"], ["Chris", "lasagna"], ["Evil Monkey", "potato salad"]],
:quagmires_car=>[["Lois", "potato salad"], ["Meg", "brownies"], ["Stewie", "chateaubriand"]],
:clevelands_car=>[["Brian", "potato salad"]]}

# Let's try another random grouping
potluck.group_by {[:peters_car, :quagmires_car, :clevelands_car][rand(3)]}
=> {:peters_car=>[["Peter", "lasagna"], ["Meg", "brownies"]], :quagmires_car=>[["Lois", "potato salad"],
["Stewie", "chateaubriand"], ["Brian", "potato salad"], ["Evil Monkey", "potato salad"]],
:clevelands_car=>[["Chris", "lasagna"]]}

# One more time!
potluck.group_by {[:peters_car, :quagmires_car, :clevelands_car][rand(3)]}
=> {:peters_car=>[["Peter", "lasagna"], ["Chris", "lasagna"], ["Stewie", "chateaubriand"]],
:quagmires_car=>[["Lois", "potato salad"], ["Evil Monkey", "potato salad"]], :clevelands_car=>[["Meg", "brownies"],
["Brian", "potato salad"]]}

Once again, it’s Enumerating Enumerable, my series of articles in which I attempt to outdo Ruby-Doc.org’s documentation of Ruby’s Enumerable module. In this article, I cover the find_index method, which was introduced in Ruby 1.9.

In case you missed any of the previous articles, they’re listed and linked below:

1. all?
2. any?
3. collect / map
4. count
5. cycle
6. detect / find
7. drop
8. drop_while
9. each_cons
10. each_slice
11. each_with_index
12. entries / to_a
13. find_all / select

Enumerable#find_index Quick Summary

Enumerable#find_index and Arrays

When used on an array, find_index passes each item in the array to the given block and either:

• Stops when the current item causes the block to return a value that evaluates to true (that is, anything that isn’t false or nil) and returns the index of that item, or
• Returns nil if there is no item in the array that causes the block to return a value that evaluates to true.

Some examples:

# How about an array of the name of the first cosmonauts and astronauts,
# listed in the chronological order of the missions?
mission_leaders = ["Gagarin", "Shepard", "Grissom", "Titov", "Glenn", "Carpenter",
"Nikolayev", "Popovich"]
=> ["Gagarin", "Shepard", "Grissom", "Titov", "Glenn", "Carpenter", "Nikolayev",
"Popovich"]

# Yuri Gagarin was the first in space
mission_leaders.find_index{|leader| leader == "Gagarin"}
=> 0

# John Glenn was the fifth
mission_leaders.find_index{|leader| leader == "Glenn"}
=> 4

# And James Tiberius Kirk is not listed in the array
kirk_present = mission_leaders.find_index{|leader| leader == "Kirk"}
=> nil

Enumerable#find_index and Hashes

When used on a hash, find_index passes each key/value pair in the hash to the block, which you can “catch” as either:

1. A two-element array, with the key as element 0 and its corresponding value as element 1, or
2. Two separate items, with the key as the first item and its corresponding value as the second item.

As with arrays, find_index:

• Stops when the current item causes the block to return a value that evaluates to true (that is, anything that isn’t false or nil) and returns the index of that item, or
• Returns nil if there is no item in the array that causes the block to return a value that evaluates to true.

Some examples:

require 'date'
=> true

# These are the names of the first manned spaceships and their launch dates
launch_dates = {"Kedr"              => Date.new(1961, 4, 12),
                "Freedom 7"         => Date.new(1961, 5, 5),
                "Liberty Bell 7"    => Date.new(1961, 7, 21),
                "Orel"              => Date.new(1961, 8, 6),
                "Friendship 7"      => Date.new(1962, 2, 20),
                "Aurora 7"          => Date.new(1962, 5, 24),
                "Sokol"             => Date.new(1962, 8, 11),
                "Berkut"            => Date.new(1962, 8, 12)}
=> {"Kedr"=>#<Date: 4874803/2,0,2299161>, "Freedom 7"=>#<Date: 4874849/2,0,2299161>,
"Liberty Bell 7"=>#<Date: 4875003/2,0,2299161>, "Orel"=>#<Date: 4875035/2,0,2299161>,
"Friendship 7"=>#<Date: 4875431/2,0,2299161>, "Aurora 7"=>#<Date: 4875617/2,0,2299161>,
"Sokol"=>#<Date: 4875775/2,0,2299161>, "Berkut"=>#<Date: 4875777/2,0,2299161>}

# Where in the list is John Glenn's ship, the Friendship 7?
launch_dates.find_index{|ship, date| ship == "Friendship 7"}
=> 4

# Where in the list is the first mission launched in August 1962?
launch_dates.find_index{|ship, date| date.year == 1962 && date.month == 8}
=> 6

# The same thing, expressed a little differently
launch_dates.find_index{|launch| launch[1].year == 1962 && launch[1].month == 8}
=> 6

Using find_index as a Membership Test

Although Enumerable has a method for checking whether an item is a member of a collection (the include? method and its synonym, member?), find_index is a more powerful membership test for two reasons:

1. include?/member? only check membership by using the == operator, while find_index lets you define a block to set up all sorts of tests. include?/member? asks “Is there an object X in the collection equal to my object Y?” while find_index can be used to ask “Is there an object X in the collection that matches these criteria?”
2. include?/member? returns true if there is an object X in the collection that is equal to the given object Y. find_index goes one step further: not only can it be used to report the equivalent of true if there is an object X in the collection that is equal to the given object Y, it also reports its location in the collection.

A quick example of this use in action:

# Once again, the mission leaders
mission_leaders = ["Gagarin", "Shepard", "Grissom", "Titov", "Glenn", "Carpenter",
"Nikolayev", "Popovich"]
=> ["Gagarin", "Shepard", "Grissom", "Titov", "Glenn", "Carpenter", "Nikolayev",
 "Popovich"]

# Yuri Gagarin is in the list
gagarin_in_list = mission_leaders.find_index {|leader| leader == "Gagarin"}
=> 0

# Captain James T. Kirk is not
kirk_in_list = mission_leaders.find_index {|leader| leader == "Kirk"}
=> nil

# gagarin_in_list is 0, which as a non-false and non-nil value evaluates as true.
# We can use it as both a membership test *and* as his location in the list.
p "Gagarin's there. He's number #{gagarin_in_list + 1} in the list." if gagarin_in_list
"Gagarin's there. He's number 1 in the list."
=> "Gagarin's there. He's number 1 in the list."

# kirk_in_list is nil, which is one of Ruby's two "false" values.
# Let's use it with the "something OR something else" idiom that
# many Ruby programmers like.
kirk_in_list || (p "You only *think* he wasn't there.")
"You only *think* he wasn't there."
=> "You only *think* he wasn't there."

Parts that Haven’t Been Implemented Yet

Ruby-Doc.org’s documentation is generated from the comments in the C implementation of Ruby. It mentions a way of calling find_index that is just like calling include?/member?:

# What the docs say (does not work yet!)
["Alice", "Bob", "Carol"].find_index("Bob")
=> 1

# What happens with the current version of Ruby 1.9
["Alice", "Bob", "Carol"].find_index("Bob")
ArgumentError: wrong number of arguments(1 for 0)
...

Ruby 1.9 is considered to be a work in progress, so I suppose it’ll get implemented in a later release.