JavaScript: Refer to remaining Array in the reduce method (fold)?

Question

I want to test wether an Array consists only of unique elements and my solution is the following:

function uniqueElements(a) {
  var r = true;
  while (a) {
    var [el, a] = [a.slice(0,1), a.slice(1)];
    r &= !a.includes(el);
  };
  return !!r;
}

This method works. However, since I am adopting a more functional style, and because folds are awesome, I would like to implement a function which looks somewhat like this:

function uniqueElements(a) {
  var isUnique = (acc, el) => acc &= !remainingArray.includes(el);
  return a.reduce(isUnique, true);
}

I can't figure out how to get to that remainingArray variable. Does anybody know how to get it? Is this even possible in JS, and if not, how could that function be expressed through a fold?

Answer 1

Remember not to get stuck in a pattern of thinking. Folds are great but in JavaScript there's no way to stop folding early if our result can be computed before traversing the entire array

In other words, what is the answer of the following? true or false?

uniqueElements ( [ 1 , 1 , 2 , 3 , ... thousands more items ] )
// => true or false ?

We can determine the answer to be false immediately after processing the second 1. There's no need to keeping folding in 2, or 3, or the rest of the array as they will not affect the false outcome

A possible solution is a simple recursive procedure

const isUnique = ([ x, ... xs ], set = new Set ()) =>
  x === undefined
    ? true
    : set.has (x)
      ? false // we already found a non-unique, stop recurring
      : isUnique (xs, set.add (x))
      
console.log (isUnique ([]))
// true

console.log (isUnique ([ 1, 2, 3 ]))
// true

console.log (isUnique ([ 1, 1, 2, 3 ]))
// false

Or a stack-safe solution that still maintains a pure functional interface – if I had to guess, this is probably 10x faster than the above program and doesn't expose private API

const isUnique = xs =>
  {
    const set = new Set ()
    for (const x of xs)
      if (set.has (x))
        return false
      else
        set.add (x)
    return true
  }

console.log (isUnique ([]))
// true

console.log (isUnique ([ 1, 2, 3 ]))
// true

console.log (isUnique ([ 1, 1, 2, 3 ]))
// false

Or make up your own solution – either way, just don't get cornered into thinking folds need to be used wherever your touch a traversable data structure.

And in a more general sense, you need to practice imagining what the process of your function looks like. I recommend that you play compiler/evaluator with a pencil and paper while you're first getting the hang of it. Eventually you will be able to envision simple processes in your head; and then more complex ones with practice over time – I say this because you probably wouldn't have reached for a fold to complete this task if you could see how silly it looks to continue folding after the result can be returned

On that note, that is why I used Set to check for uniques as opposed to .includes. Sets can do binary search whereas array searches are linear – looking for your item in an array one-by-one just seems silly once you can see what that process would look like for a significantly large input. Only when you're envisioning process can you see how alternative data structures like Set can dramatically lower the time complexity of your function