换能器展平和独特
Transducer flatten and uniq
我想知道是否有一种方法可以使用转换器来展平列表并过滤唯一值?
通过链接,非常简单:
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
换能器在这里没有多大意义。您的数据结构是递归的。处理递归结构的最佳代码通常需要递归算法。
换能器的工作原理
(Roman Liutikov 写了一篇 nice introduction to transducers。)
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
是transducer-enabled,我们可以转换
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 都不是转换器的好用例。”
我想知道是否有一种方法可以使用转换器来展平列表并过滤唯一值?
通过链接,非常简单:
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
换能器在这里没有多大意义。您的数据结构是递归的。处理递归结构的最佳代码通常需要递归算法。
换能器的工作原理
(Roman Liutikov 写了一篇 nice introduction to transducers。)
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
是transducer-enabled,我们可以转换
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 都不是转换器的好用例。”