Come Correct with Inject and Collect

Here’s a refactoring example for a simple Ruby math problem using the inject method.

The goal is to generate an n by n multiplication matrix. Pretty straightforward. Let’s make a first pass:

def multiplication_table(n)
  results = []

  (1..n).each do |row_index|
    row = []
    (1..n).each { |column_index| row << row_index * column_index }
    results << row
  end

  results.each do |row|
    header = '%-3s ' * row.length
    puts header % row
  end
end

multiplication_table(7)
1   2   3   4   5   6   7
2   4   6   8   10  12  14
3   6   9   12  15  18  21
4   8   12  16  20  24  28
5   10  15  20  25  30  35
6   12  18  24  30  36  42
7   14  21  28  35  42  49

It does the job, but it’s nothing to look at. We can condense using in-line blocks and fancy curly braces, but first let’s try using inject.

Quick background: Inject iterates over a set using a block with a collector, which is a variable whose value is passed back each round, making it good for iterative uses. The block’s return value is passed into the collector (make sure you return something or you’ll get a nil). Also, the return value of the whole inject block is the final collector value.

Simple example from the docs:

(5..10).inject {|sum, n| sum + n }            #=> 45

The inject method takes a parameter, which initializes the collector value (default is to set to the first value). You can pass in an empty array and add values:

def multiplication_table(n)
  results = (1..n).map do |row_index|
    (1..n).inject([]) { |row, n| row + [row_index * n] }
  end

  results.each { |row| puts '%-3s ' * row.length % row }
end

So that’s inject with the iterative collect (Whoo-aaaa - got you all in check)

Note: For a more in-depth discussion of inject, read Mike Burns’ recent post.

Derive #inject for a better understanding

Let’s talk about Enumerable#inject. It’s special to me. In other cultures it’s called foldl, foldLeft, reduce, catamorphism, or bananas (PDF). We got our name from Smalltalk, which got it from, I dunno, a folk song?

Inject is an abstraction over structural recursion. For examples, imagine a list were defined like this:

class EmptyList
end

class ConsList
  def initialize(first, rest)
    @first = first
    @rest = rest
  end
end

factorials = ConsList.new(1,
               ConsList.new(2,
                 ConsList.new(6,
                   ConsList.new(24,
                     ConsList.new(120, EmptyList.new)))))

Computing the length of the list is simple:

class EmptyList
  def length
    0
  end
end

class ConsList
  def length
    1 + @rest.length
  end
end

Computing the product of the list is simple, too:

class EmptyList
  def product
    1
  end
end

class ConsList
  def product
    @first * @rest.product
  end
end

There’s a common pattern here: we have a base case (0 and 1), an enumerable (EmptyList and ConsList), and a combining method (lambda {|x,xs| 1 + xs} and Fixnum#*). Let’s write a method to abstract over this:

class EmptyList
  def inject(base, &block)
    base
  end
end

class ConsList
  def inject(base, &block)
    block.call(@first, @rest.inject(base, &block))
  end
end

Now that we’ve abstracted this out (in 2009 we said “DRYed this up”, and then immediately punched ourselves in the face) we can use it:

class ConsList
  def length
    inject(0){|_, count| 1 + count}
  end

  def product
    inject(1){|number, running_product| number * running_product}
  end
end

(Note that Ruby got the arguments backward. Oh well.)

An underlying theme to inject is that there exists a class with a base case and a combining method. Some other examples are:

• 0 and Fixnum#+
• 1 and Fixnum#*
• [] and Array#push
• true and &&
• lambda{|x|x} and lambda{|f, g| lambda{|x| f(g(x))}} (the identity method and method composition)

… and so on. These are called monoids, and that’s awesome because now we have a name for them.

“Oh sure, just inject over the method monoid,” you say to your coworker, and she’s like, “oh, duh” and types it out:

class Composition
  def initialize(f, g)
    @f = f
    @g = g
  end

  def compose(g)
    Composition.new(self, g)
  end

  def call(x)
    @f.call(@g.call(x))
  end
end

id = lambda{|x| x}
twice_the_sine_plus_one = [lambda{|x| x+1}, lambda{|x| x*2}, lambda{|x| Math.sin(x)}]

new_method = twice_the_sine_plus_one.inject(Composition.new(id, id)) do |result, f|
  result.compose(f)
end

Join me next time when I talk about monoids closed over the category of endofunctors!