X-Combinator

Ever since I came across ruby’s Enumerable inject function, I have been curious about its applications, and how to best think of it in its most general mathematical form.

As an example, say we have a list of numbers that we want to sum:

[ 2, 3, 5, 7 ]

We can do this in a traditional iterative loop:

sum = 0 [2,3,5,7].each { |x| sum += x } sum

=> 17
(=> 17 is the output of copying and pasting this code into irb for those who are following along at home.)

Using inject, we can do this in 1 line:

[2,3,5,7].inject(0) { |x,y| x+y }

=> 17
To see what is going on here, it will be helpful to abstract out the addition function:

def f(x,y) x + y end

Let’s redo the previous inject call, and just replace “x+y” with “f(x,y)”:

[2,3,5,7].inject(0) { |x,y| f(x,y) }

=> 17
Let’s expand out what inject is really doing. This is inferred directly from the Ruby documentation:

f(f(f(f(0,2),3),5),7)

=> 17
That is illuminating. It seems that inject allows us to iteratively apply a 2-parameter function to itself, where the output of each step in the iteration is fed back into the first parameter, and the second parameter is read in from the list it is called on. The first time it is called, it needs a value for the first parameter, and this single value is the parameter given to the inject call itself.

That’s quite a mouthful. But let’s test our understanding at least on the inject parameter. If we give it 1,000,000 in the previous examples instead of 0, we should have 1,000,000 added to the result:

[2,3,5,7].inject(1000000) { |x,y| f(x,y) }

=> 1000017
So it feels like we have a better understanding of ruby’s inject now. Another way to think of it is in terms of the f(f(f(...f(f(f(a,b),c),d)...,x),y),z) pattern.

As a final test of our ability to wield the inject method, let’s try to print out the Mandelbrot set onto the console using it as the main iterator.

If you’re not familiar with the Mandelbrot set, I recommend spending some time on that page either before or after reading this.

Let’s start with defining the iterated function:

def m(z,c) z*z + c end

For a given complex number a, to see whether it is included in the Mandelbrot set or not, we start by squaring it and adding the result back to itself:

a*a + a

(set a=0.1 if you are typing this into irb and don’t like to see the NameErrors.)
Or in other words,

m(a,a)

We take the result of that, square it, and add it back to a:

m(a,a)*m(a,a) + a

or in other words,

m(m(a,a),a)

Let’s do it two more times just to be sure we see the pattern:

m(m(m(a,a),a),a) m(m(m(m(a,a),a),a),a)

This looks like a job for inject! The last line above is equivalent to:

[a,a,a,a].inject(a) { |z,c| m(z,c) }

The number of times the iteration is done is simply the size of the given array. Fortunately, ruby makes it easy to create arrays with repeated elements:

Array.new(4,a).inject(a) { |z,c| m(z,c) }

For the resolution we are aiming for, 50 iterations should be enough. Also, let’s replace m(z,c) with z*z+c since it doesn’t really save us space, and everything we are doing is Mandelbrot-specific so there is no need to abstract it out.

Array.new(50,a).inject(a) { |z,c| z*z+c }

The only free variable here is a, so let’s wrap this into a function called mandelbrot:

def mandelbrot(a) Array.new(50,a).inject(a) { |z,c| z*z+c } end

As I started saying earlier, to test whether a given complex number a belongs to the Mandelbrot set or not, or rather for our purposes to approximate these points since we are only doing 50 iterations instead of an infinite amount, we check the absolute value of mandelbrot(a). If it is less than 2, we will print an asterisk on the screen. Otherwise we will leave it blank.
We’ll have y go from 1.0 to -1.0 in the vertical direction, and x go from -2.0 to 0.5 in the horizontal:

require 'complex' def mandelbrot(a) Array.new(50,a).inject(a) { |z,c| z*z + c } end (1.0).step(-1,-0.05) do |y| (-2.0).step(0.5,0.0315) do |x| print mandelbrot(Complex(x,y)).abs < 2 ? '*' : ' ' end puts end

The double-nested loop at the bottom simply iterates through the rows and columns of the screen, printing out the Mandelbrot set line by line. The numerical step values are chosen so as to have 40 rows and 79 columns. The body of the loop creates the complex number Complex(x,y) and calls the mandelbrot(a) function we constructed above with it, and compares the absolute value of its output to 2. If less than 2, display an asterisk, otherwise display a space. After each horizontal line, the call to puts just goes to the beginning of the next line.

I won’t give away the surprise ending! Try it!