Derive #inject for a better understanding

Mike Burns

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))}} (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
hound

Hound automatically reviews Ruby, JavaScript, CoffeeScript, and SCSS code in your GitHub pull requests and comments on style violations. It is free for open source repos and $12/month per private repo.