0

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.

19
  • 2
    What language is this? Furthermore, note that "why doesn't this code work" or "how do I do this in some language" are typically questions for Stack Overflow rather than Programmers.SE. – user40980 Oct 15 '15 at 16:25
  • It's ECMAScript, but I'm interested in the general concept within functional programming. – dalgard Oct 15 '15 at 16:26
  • stackoverflow.com/q/21506025 – Robert Harvey Oct 15 '15 at 16:35
  • 2
    Eh, I think that original post is suitably canonical. – Robert Harvey Oct 15 '15 at 16:41
  • 1
    I should point out that in Scala or Clojure, one would do a different approach as there are different language built-ins. A variation on this for Scala. There is no universal 'how to do this in functional programming' as each language has a slightly different dialect of tools available. – user40980 Oct 15 '15 at 16:45
10

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)
3
  • Side note: ECMAScript 2015 looks pretty nice, even to this Rubyist and Haskell aficionado! – Jörg W Mittag Oct 15 '15 at 21:39
  • It really, really is. – dalgard Oct 16 '15 at 12:05
  • 1
    In ES2017 or whatever it will be called, the entire first line of the last example collapses to [for (a of someArray) for (b of someArray) [a, b]] – Jörg W Mittag Oct 16 '15 at 12:13
4

Well, I have over 10 years of functional programming experience, and here's how I would do it:

  1. If the sequence is empty, return true
  2. Otherwise, return true if and only if all of the elements of the sequence are equal to the first one.

In Haskell, that starts out like this:

-- | Return false if and only if there is a pair of unequal elements
-- in the list.
allEqual :: Eq a => [a] -> a
allEqual [] = True
allEqual (first:rest) = all (\elem -> elem == first) rest

The all function tests whether all elements of a list satisfy a specified condition. In this case, the condition is (\elem -> elem == first)—a function that tests whether the given elem is equal to first.

The all function is provided in the Data.List library module, but let's implement it ourselves:

-- | Apply the given test to every element in the list, and return
-- false if and only if at least one element tests false.
all :: (a -> Bool) -> [a] -> Bool
all test items = and (map test items)

To implement all I used two other standard functions—map and and. But let's just go and implement them ourselves:

-- | Return true if and only if there are no `False` elements in the list
and :: [Bool] -> Bool
and bools = foldr (&&) True bools

-- | Apply the given function to all elements of the list, collecting
-- the results in a list.
map :: (a -> b) -> [a] -> [b]
map f = foldr go []
  where go item rest = f item : rest

And those two functions I wrote in terms of foldr ("fold right"), which is one such "reduce" operation that you're interested in. For completeness, let's write that function:

foldr :: (a -> r -> r) -> r -> [a] -> r
foldr _ z [] = z
foldr f z (a:as) = f a (foldr f z as)

And now let me point out something very important that I did: I wrote the function you wanted in terms of an utility function, that I then wrote in terms of two more utility functions, that I then wrote in terms of foldr, which I then wrote. And also, since the library provides all those utility functions, I could have just stopped at the first definition.

That's a key thing that newcomers to functional programming often overlook—reduce/fold is a low level operation that you use to write a large library of easier to use, auxiliary operations, and you break down your problems in terms of those. Look for example at the large number of functions in Haskell's Data.List library module.

The way you get good a functional-style list processing is to:

  1. Learn how to break down problems in terms of library functions like those;
  2. Learn how to write those library functions or new, similar ones that are missing from the library.

If you're always reaching for reduce right away you're going to end up with code that's harder to write and to read. Whereas the reusable utility functions routinely cure this problem—the last line of my definition of allEqual basically reads like this: "test whether all elements after the first one in the list are equal to it."

2
  • It looks like you are missing a use of items in the definition of map. Should it not be map f items = foldr go [] items? – Caleth Dec 5 '17 at 14:11
  • @Caleth: Well spotted. Fixed, but in a different manner than your suggestion (you can fix this either your way, or removing the use of items from the left hand side). – sacundim Dec 5 '17 at 21:00
2

Most FP languages I've seen have an implementation of fold/reduce which takes in a starting value for an accumulator, e.g. in Haskell:

pairs = zipWith (,) xs ys
foldl (\accum (x,y) -> (x == y) && accum) True pairs
---------------------------- initial value ^

There are also usually other functions which take care of calculations like this, such as and:

and [True,False,True,True,False] == False
2
  • ecmascript for and appears to be every – jk. Oct 15 '15 at 18:11
  • @jk it does indeed appear to be every, thanks. – paul Oct 15 '15 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.