GIANT ROBOTS SMASHING INTO OTHER GIANT ROBOTS

Written by thoughtbot

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!