javascript - 换能器展平和独特

Question

我想知道是否有一种方法可以使用转换器来展平列表并过滤唯一值？

通过链接，很容易:

import {uniq, flattenDeep} from 'lodash';|

const arr = [1, 2, [2, 3], [1, [4, 5]]];

uniq(flattendDeep(arr)); // ->  [1, 2, 3, 4, 5]

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.10/lodash.core.min.js"></script>

但是这里我们在列表上循环两次(+ n 深度层)。不理想。

我想要实现的是在这种情况下使用传感器。 我已经阅读了关于它的 Ramda 文档 https://ramdajs.com/docs/#transduce , 但我仍然找不到正确编写它的方法。

目前，我使用一个带有递归函数的reduce函数:

import {isArray} from 'lodash';

const arr = [1, 2, [2, 3], [1, [4, 5]]];

const flattenDeepUniq = (p, c) => {
    if (isArray(c)) {
        c.forEach(o => p = flattenDeepUniq(p, o));
    }
    else {
        p = !p.includes(c) ? [...p, c] : p;
    }

    return p;
};

arr.reduce(flattenDeepUniq, []) // -> [1, 2, 3, 4, 5]

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.10/lodash.core.min.js"></script>

我们对元素进行了一次循环(+ n 层深度循环)，这看起来更好、更优化。

在这种情况下甚至可以使用转换器和迭代器吗？ 有关 Ramda 转换功能的更多信息:https://gist.github.com/craigdallimore/8b5b9d9e445bfa1e383c569e458c3e26

Answer 1

传感器在这里没有多大意义。您的数据结构是递归的。处理递归结构的最佳代码通常需要递归算法。

传感器的工作原理

(Roman Liutikov 写了一个 nice introduction 给传感器。)

Transducers 都是关于将通过相同数据的多次行程替换为一次行程，将步骤的原子操作组合成一个操作。

换能器非常适合转换此代码:

xs.map(x => x * 7).map(x => x + 3).filter(isOdd(x)).take(5)
//  ^               ^                 ^               ^
//   \               \                 \               `------ Iteration 4
//    \               \                 `--------------------- Iteration 3
//     \               `-------------------------------------- Iteration 2
//      `----------------------------------------------------- Iteration 1

像这样:

xs.reduce((r, x) => r.length >= 5 ? res : isOdd(x * 7 + 3) ? res.concat(x * 7 - 3) : res, [])
//    ^
//     `------------------------------------------------------- Just one iteration

在 Ramda 中，因为 map、filter 和 take 启用了转换器，我们可以转换

const foo = pipe(
  map(multiply(7)), 
  map(add(3)), 
  filter(isOdd), 
  take(3)
)

foo([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) //=> [17, 31, 45]

(对数据进行四次迭代)

const bar = compose(
  map(multiply(7)), 
  map(add(3)), 
  filter(isOdd), 
  take(3)
)

into([], bar, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])  //=> [17, 31, 45]

只迭代一次。 (注意从 pipe 到 compose 的切换。Transducers 的组合顺序与普通函数相反。)

请注意，此类换能器的关键在于它们的工作原理都相似。 map 将一个列表转换为另一个列表，filter 和 take 也是如此。虽然您可以拥有对不同类型进行操作的转换器，并且 map 和 filter 也可能以多态方式对这些类型进行操作，但只有当您组合操作的函数时，它们才会一起工作在同一类型上。

Flatten 不太适合换能器

你的结构更复杂。虽然我们当然可以创建一个函数，以某种方式(前序、后序)抓取它，因此可能会用它开始一个传感器管道，处理递归结构的逻辑方法是使用递归算法。

展平这种嵌套结构的简单方法是这样的:

const flatten = xs => xs.reduce(
  (a, x) => concat(a, isArray(x) ? flatten(x) : [x]), 
  []
);

(由于各种技术原因，Ramda 的代码要复杂得多。)

不过，此递归版本不太适合与换能器一起使用，换能器基本上必须按部就类地工作。

Uniq 不太适合换能器

另一方面，

uniq 对此类传感器意义不大。问题是 uniq 使用的容器，如果你想从转换器中获得任何好处，必须是一个具有快速插入和快速查找的容器，一个 Set或者最有可能是 Object。假设我们使用一个 Set。然后我们遇到了问题，因为我们的 flatten 对列表进行操作。

不同的方法

由于我们无法轻松地将现有函数折叠成一个可以满足您的需求的函数，因此我们可能需要编写一个一次性函数。

早期解决方案的结构使得添加唯一性约束变得相当容易。同样，那是:

const flatten = xs => xs.reduce(
  (a, x) => concat(a, isArray(x) ? flatten(x) : [x]), 
  []
);

使用辅助函数将所有元素添加到 Set:

const addAll = (set, xs) => xs.reduce((s, x) => s.add(x), set)

我们可以编写一个函数来展平，只保留唯一值:

const flattenUniq = xs => xs.reduce(
  (s, x) => addAll(s, isArray(x) ? flattenUniq(x) : [x]), 
  new Set()
)

请注意，这有很多上面的结构，仅切换到使用 Set，因此从 concat 切换到我们的 addAll。

当然你可能想要一个数组，在最后。我们可以通过用 Set -> Array 函数包装它来做到这一点，如下所示:

const flattenUniq = xs => Array.from(xs.reduce(
  (s, x) => addAll(s, isArray(x) ? flattenUniq(x) : [x]), 
  new Set()
))

您也可以考虑将此结果保留为 Set。如果您真的想要一组唯一值，Set 是合乎逻辑的选择。

这样的函数没有无点转换函数的优雅，但它可以工作，并且暴露的管道使得与原始数据结构和普通 flatten 函数的关系更加紧密清楚。

---

我想您可以将整个冗长的答案视为指出 user633183 在评论中所说的内容的冗长方式:“flatten 和 uniq 都不是转换器的好用例。”