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!

author image
Mike Burns
upcase

Sharpen your programming skills by completing coding exercises that are reviewed by other developers at Upcase today.