JavaScript:引用Refer (折叠)中的剩余数组？

Question

我想测试数组是否只由唯一的元素组成，我的解决方案如下：

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

这种方法很有效。但是，由于我采用的是一种更实用的风格，而且由于折叠很棒，所以我想实现一个类似于这样的函数：

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

我不知道如何获得那个remainingArray变量。有人知道怎么弄吗？这在JS中是可能的吗?如果没有，如何通过折叠来表达这个功能？

Answer 1

记住不要陷入思维模式。折叠很棒，但是在JavaScript中，如果我们的结果可以在遍历整个数组之前被计算出来，那么就无法提前停止折叠。

换句话说，以下问题的答案是什么？true还是false？

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

在处理第二个false之后，我们可以立即确定答案是1。没有必要将折叠保存在2、3或数组的其余部分，因为它们不会影响false结果

一个可能的解决方案是一个简单的递归过程。

​

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

​

或者一个仍然保持纯功能接口的堆栈安全解决方案--如果我不得不猜测的话，这可能比上面的程序快10倍，而且不公开私有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

​

或者想出你自己的解决方案--不管是哪种方式，只要你触摸一个可遍历的数据结构，就不要陷入思维折叠需要使用的境地。

在更一般的意义上，你需要练习想象你的函数的过程是什么样子的。我建议你在第一次掌握它的窍门时，用铅笔和纸来玩编译器/评估器。最终，你将能够在头脑中想象出简单的过程，然后随着时间的推移，想象出更复杂的过程--我这么说是因为，如果你能看到在结果返回后继续折叠是多么愚蠢的话，你很可能不会去折叠来完成这个任务。

在这一点上，这就是为什么我使用Set来检查uniques而不是.includes。集合可以进行二进制搜索，而数组搜索则是线性的--逐个查找数组中的项--一旦您看到这个过程对于一个显着的大输入会是什么样子，就显得很傻了。只有在设想过程时，才能看到像Set这样的替代数据结构如何显著降低功能的时间复杂度

Answer 2

可以对数组进行切片：

function isUnique(xs) {
  return xs.reduce((acc, x, i) => {
    if (xs.slice(i + 1).includes(x)) {
      return false;
    }
    return acc;
  }, true);
}

虽然，正如注释中提到的，如果数组中有字符串或数字，也可以使用哈希来提高性能。