---
title: 'Derive #inject for a better understanding'
teaser:
tags: web,ruby,good code
author: Mike Burns
published_on: 2012-02-17
---

Let's talk about `Enumerable#inject`. It's special to me. In other cultures it's
called
[foldl](http://hackage.haskell.org/packages/archive/base/latest/doc/html/Data-List.html#v:foldl-39-),
[foldLeft](http://www.scala-lang.org/api/current/scala/collection/Map.html#scala.collection.TraversableOnce#foldLeft),
[reduce](http://docs.python.org/library/functions.html#reduce),
[catamorphism](http://en.wikipedia.org/wiki/Catamorphism), or
[bananas](http://wwwhome.cs.utwente.nl/~fokkinga/mmf91m.pdf) (PDF). We got our
name from Smalltalk, which got it from, I dunno, [a folk
song](http://smalltalkzen.wordpress.com/2011/02/02/arlo-guthrie-and-the-origins-of-the-collection-protocol/)?

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

[structural recursion]: http://en.wikipedia.org/wiki/Recursion_(computer_science)#Structural_versus_generative_recursion

```ruby
    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:

```ruby
    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:

```ruby
    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:

```ruby
    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:

```ruby
    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](http://rubydoc.info/gems/method_missing/0.0.1/file/README.md#usage-composing))

… and so on. These are called
[monoids](http://mathworld.wolfram.com/Monoid.html), 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:

```ruby
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!