JavaScript: 引用reduce方法中剩余的Array(fold)？

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

您可以对数组进行切片：

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

不过，如评论中所述，如果数组中有字符串或数字，您也可以使用散列来提高性能。

Answer 2

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

也就是说，下面的答案是什么？ true 或 false?

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

我们可以在处理完第二个1后立即确定答案为false。没有必要在 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

或者制定你自己的解决方案——无论哪种方式，只是不要陷入困境，只要你接触可遍历的数据结构，就需要使用折叠。

从更一般的意义上讲，您需要练习想象您的函数的过程是什么样子的。我建议您在刚开始掌握窍门时，用铅笔和纸玩 compiler/evaluator。最终你将能够在脑海中想象出简单的过程；然后随着时间的推移练习更复杂的——我这么说是因为如果你能看到继续折叠看起来多么愚蠢after，你可能不会达到折叠来完成这个任务可以返回结果

关于这一点，这就是我使用 Set 而不是 .includes 检查唯一性的原因。集合可以进行二进制搜索，而数组搜索是线性的——在数组中一个一个地寻找你的项目看起来很愚蠢，一旦你看到这个过程对于一个非常大的输入来说会是什么样子。只有当您设想过程时，您才能看到像 Set 这样的替代数据结构如何显着降低函数的时间复杂度

JavaScript: 引用reduce方法中剩余的Array(fold)？

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

javascript

functional-programming

fold