Functional Programming – How to Compare All Items in an Array

comparisonfunctional programminglist

In functional programming, how do I do an equality comparison of all items in an array?

I have an array of items that I want to compare, for example for equality. Is it possible to use a fold (also known as reduce) operation for this?

This code won't work, because after the first iteration, memo is a boolean:

[a, b, c].reduce((memo, item) => memo === item)

I've tried this variant, which returns the last item if they are equal, but this is no good, since I need a boolean as the result:

[a, b, c].reduce((memo, item) => (memo === item) && item)

Forcing a boolean !! is no good either, since the item itself may be falsy and so give the wrong result.

I would like to have a functional solution to this problem – saving the result outside of the fold is much more verbose.

Best Answer

I want to answer a small part of your question, that is nonetheless very interesting:

Is it possible to use a fold (also known as reduce) operation for this?

Yes, it is.

In fact, it is always possible to use a fold for anything! Fold is a general operation for iteration, anything you can do with iteration, you can do with fold!

The Wikipedia page for fold has a sketch of a proof for this, but I want to give another intuition thanks to a talk by Rúnar Óli Bjarnason on Functional Programming for Beginners which unfortunately seems to have vanished from the interwebs.

A collection can be either empty or not empty. The two arguments to fold tell it what to do when the collection is empty, and what to do with the next element when the collection is not empty. That covers all the cases, so it should be intuitively clear, that fold can do anything.

Another view, thanks to that same talk, is of fold as an interpreter. Think of a collection as a series of instructions. There are two kinds of instructions: the HALT instruction (which has no operands), and the NEXT instruction, which has one operand. The two arguments you supply to fold, are the two implementations of the interpreter functions for HALT and NEXT. Again, since there are only two instructions, and you supply the code for both of them, it comes as no surprise, that fold can do anything.

I actually put this to the test, and re-implemented many of the methods from Ruby's collection framework (the Enumerable module), which normally rely solely on the each method (a foreach-style iterator which simply yields each element), so that they instead all rely on the inject method (which is how Ruby spells "fold").

So, what does it look like with a fold in ECMAScript?

someArray.reduce((memo, el, i, ary) => memo && ary[0] === el, true)

However, just because fold can do everything, it shouldn't be used for everything. When there are more appropriate, more specialized operations, these should be used instead:

someArray.every((el, i, ary) => ary[0] === el)

Note: technically speaking, these two implementations do not check whether every element is equal to every other element, they only check whether every element is equal to the first element. Thus, it relies on === being transitive and symmetric (as a well-behaved equality should be). If you cannot rely on that, you should first build the Cartesian Product of the array with itself, map it to whether the two elements are equal, and then ask if everything is true:

someArray.reduce((memo, el, _, ary) => memo.concat(ary.map(ell => [el, ell])), []).
map(([a, b]) => a === b).
every(el => el)
Related Topic