Filter-Reduce Optimization

This must be well-know amongst functional programming researchers, but I kind of stumbled upon it by accident when studying Joy.

Consider the following program to count even numbers:

define count_evens = [2 mod 0 neq] filter 0 [inc] reduce

So for those new to Joy, every program/function takes it parameter on the stack, and pushes its results onto the stack.

Here is a brief explanation of the operators:

2 = push the value two onto the stack
[] = push the contents onto the stack without evaluating them
mod = modulo
inc = increment the top item of the stack
neq = not equals

The program I showed takes a list on the stack, filters the list for only even numbers, and then counts them using a reduce function.

Assuming you are following me so far, this program can be rewritten as follows (caveat: I'm doing this off the top of my head so I could have made a mistake in syntax):

  def count_evens_1 = 0 [2 mod 0 eq [inc] [] if] reduce

What I've done here is eliminate the unneccessary filter operation and "folded" it (pun intended) into the reduce operation.

My observation when working with Joy is that this optimization is trivial to automate.

So my question to the group is: is this a well known optimization, and if so, is it as easily applied in other functional languages?

For those whose curiosity has been piqued, I'm researching the viability of using a Joy dialect as an intermediate language.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.


Fusion is the term I think you're looking for. See A tutorial on the universality and expressiveness of fold. You might also be interested in Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire along with the list of references in both papers.

Great Links

Thanks a lot for the links, and the terminology. I really appreciate it.