How can I perform an idiomatic non-recursive flatten in ruby?

Question

I have a method that returns an array of arrays. For convenience I use collect on a collection to gather them together.

arr = collection.collect {|item| item.get_array_of_arrays}

Now I would like to have a single array that contains all the arrays. Of course I can loop over the array and use the + operator to do that.

newarr = []    
arr.each {|item| newarr += item}

But this is kind of ugly, is there a better way?

Answer 1

There is a method for flattening an array in Ruby: Array#flatten:

newarr = arr.flatten(1)

From your description it actually looks like you don't care about arr anymore, so there is no need to keep the old value of arr around, we can just modify it:

arr.flatten!(1)

(There is a rule in Ruby that says that if you have two methods that do basically the same thing, but one does it in a somewhat surprising way, you name that method the same as the other method but with an exlamation point at the end. In this case, both methods flatten an array, but the version with the exclamation point does it by destroying the original array.)

However, while in this particular case there actually is a method which does exactly what you want, there is a more general principle at work in your code: you have a sequence of things and you iterate over it and try to "reduce" it down into a single thing. In this case, it is hard to see, because you start out with an array and you end up with an array. But by changing just a couple of small details in your code, it all of the sudden becomes blindingly obvious:

sum = 0
arr.each {|item| sum += item } # assume arr is an array of numbers

This is exactly the same pattern.

What you are trying to do is known as a catamorphism in category theory, a fold in mathematics, a reduce in functional programming, inject:into: in Smalltalk and is implemented by Enumerable#inject and its alias Enumerable#reduce (or in this case actually Array#inject and Array#reduce) in Ruby.

It is very easy to spot: whenever you initialize an accumulator variable outside of a loop and then assign to it or modify the object it references during every iteration of the loop, then you have a case for reduce.

In this particular case, your accumulator is newarr and the operation is adding an array to it.

So, your loop could be more idiomatically rewritten like this:

newarr = arr.reduce(:+)

An experienced Rubyist would of course see this right away. However, even a newbie would eventually get there, by following some simple refactoring steps, probably similar to this:

First, you realize that it actually is a fold:

newarr = arr.reduce([]) {|acc, el| acc += el }

Next, you realize that assigning to acc is completely unnecessary, because reduce overwrites the contents of acc anyway with the result value of each iteration:

newarr = arr.reduce([]) {|acc, el| acc + el }

Thirdly, there is no need to inject an empty array as the starting value for the first iteration, since all the elements of arr are already arrays anyway:

newarr = arr.reduce {|acc, el| acc + el }

This can, of course, be further simplified by using Symbol#to_proc:

newarr = arr.reduce(&:+)

And actually, we don't need Symbol#to_proc here, because reduce and inject already accept a symbol parameter for the operation:

newarr = arr.reduce(:+)

This really is a general pattern. If you remember the sum example above, it would look like this:

sum = arr.reduce(:+)

There is no change in the code, except for the variable name.