Lazy Logic: Efficiently Reduce An Array To A Boolean

Posted on November 12, 2015 by Carsten Zimmermann

Robin and I have been playing around with reducing a list using the to_proc‘ed version of the logical AND operator. It started out whether something like my_list.reduce(:'&&') would make it through the Ruby interpreter (spoiler alert: it doesn’t, it returns NoMethodError: undefined method ‘&&’ for true:TrueClass instead).

Since we were dealing with a list of booleans, the next best thing is:

[true, false, true].reduce(:&)
=> false

[true, true, true].reduce(:&)
=> true

By the way, there’s an alternative way of calling reduce/inject with an initial value and a block in the form of my_list.reduce(false) { |memo, obj| memo && obj } that I wasn’t aware of:

[true, true, true].reduce(false, :&)
=> false

Reduce using a logical AND can be done with the Enumerable#all? and for me, reading a predicate method is far less cognitive load than passed Procs / Symbols.

What we wanted to know is how clever Enumerable#all? is in terms of lazy boolean evaluation. Will it stop iterating when the result is already clear?

Quick recap: if you && three expressions and the first two already evaluate to false, Ruby instantly breaks the evaluation: there is no way that an already falsy statement will return true when &&‘ed. A good way to take advantage of this smart feature is putting the cheap calculations first and the more expensive ones on the right side of the expression.

Our irb test scenario looked like this:

a = -> { true }
b = -> { false }
c = -> { fail 'Iteration should have stopped before :(' }

[a, b, c].all? { |ƛ| ƛ.call }

We didn’t see the exception, meaning that Enumerable#all? indeed stopped after evaluating the first two elements. Good!

The use of lambdas as elements instead of eagerly evaluated objects was for our quick test, but it also allows taking the concept of evaluating the most expensive expressions last (see recap above) one step further: When an array is instantiated, all elements will be evaluated. Having lambdas/procs as elements will defer their evaluation and we can iterate over “cheap” items when reducing them with logical operators.

Imagine this example:

cheap1 = -> { true }
cheap2 = -> { [true, false].sample }
expensive1 =  -> { sleep(10); false }
expensive2 =  -> { sleep(20); true }

[cheap1, cheap2, expensive1, expensive2].all? &:call

There is .5 chance that expensive1 will never have to be called (in this case: eliminating a 10 second wait-time) and it will never run expensive2.

Lazy Logic: Efficiently Reduce An Array To A Boolean

Related Posts