Functional programming is becoming more and more fascinating as I am learning it. It is a very similar feeling to my first “Hello world” or seeing my first HTML rendered in a browser, a completely new world so to speak. Todays exploration is nothing deep, just a little fun with higher order functions similar to my previous posts on reduce/fold1 2. I will express the JavaScript built in array functions [].some and [].every with [].reduce and also present the Haskell equivalents. For now I will try to stick to the term folding for the [].reduce operation in JavaScript because I think that is more language agnostic. And I find the movement associated with folding to be a very nice picture of the abstract operation.

If you already know the concept of folds then I suggest you try to do the exercise yourself because resulting code is simple and does not show the thinking process of converting an abstract operation into a fold.

Every and all elements

The JavaScript array function every takes a predicate and returns true if all elements in the array satisfy it and false otherwise. Predicate is just a fancy name for a function that returns a boolean. So what arr.every(predicate) really computes is predicate(arr[0]) && predicate(arr[1]) ... until the last element. This is exactly what the words “all elements satisfy the predicate” translate to. With this intermediate form the code below should make sense:

function every(arr, predicate) {
	return arr.reduce((acc, item) => acc && predicate(item), true);

The only thing that might not be obvious is why we start with true. I can think of two reasons that justify it:

  1. The only options are true and false, since the start value should always be of the same type as the return value of the fold. If we start with false the result is always false, since false && ... === false. Therefore the only option is to start with true.

  2. A better explanation is that the starting value is the result for the empty list. Now why should [].every(predicate) be true? While it might be tempting to get into a philosophical debate to answer this, I would rather go back to the definitions. The semantics of every are defined in the ECMAScript specification3 and if you run through the evaluation algorithm you will see that it returns true for an empty list. That does not leave much room for discussion, so I will only add this: The statement also true in a mathematical sense in which any statement of the form “for all x in X …” is true if X is empty.

My Haskell version of the JavaScript function above is this:

every p = foldr ((&&) . p) True

Remember, foldr is the same as reduce (for the purposes of this discussion). The function we give it takes as arguments a list item and then the accumulator value. Here this function is (&&) . p which first feeds the list item into p and passes the result to &&. Since && takes two arguments it will now consume the accumulator value as second argument and produce the result of the and operation. The list argument to every does not need to be written down, because the type of foldr tells Haskell that every p should result in a function that takes a list as argument. That is called currying and if that makes no sense to you I refer to my previous post on folds in Haskell1. Note that I flipped the order of arguments to do this, something that could be reverted wrapping everything in a flip call I think.

Some or any elements

I wanted this to be a quick post and already wrote way more than intended, so here is my code for some without further commentary.

function some(arr, predicate) {
	return arr.reduce((acc, item) => acc || predicate(item), false);
some p = foldr ((||) . p) False

Naming is hard

Indeed, Haskell also has these functions built in. They have different names and I find the mapping between the two languages quite funny here: JS [].every is called all in Haskell and [].some is called any. That is it for today, as usual if you find any mistakes, have questions or suggestions for improvement please let me know.