haskell - 如何在 haskell 中有效地找到值列表列表的并集？

Question

由于代码示例值得一千字，我将从以下开始:

testList = [1,2,2,3,4,5]
testSet = map sumMapper $ tails testList
          where sumMapper [] = []
                sumMapper (a:b) = sumMap a b
                sumMap a b = map (+ a) b

这段代码采用一个列表并将所有元素相加以获得所有元素的总和(我也对其效率感兴趣)。 testSet的输出是:

[[3,3,4,5,6],[4,5,6,7],[5,6,7],[7,8],[9],[],[]]

我想找到这些列表的并集(使其成为一个集合)，但我觉得:

whatIWant = foldl1 union testSet

性能会很差(真正的列表将有数千个元素长)。

这是正确的解决方案还是我遗漏了一些明显的东西？

Answer 1

你可能想尝试

nub $ concat theListOfLists

在使用union的版本中，删除重复项的代码将运行多次。这里它只运行一次。

它只会执行一次提取唯一值的代码。

还有一个 Data.Set 库，您也可以使用

import Data.Set
S.fromList $ concat theListOfLists

重要的一点是，提取重复项的代码(此处和上面)仅在完整列表上运行一次，而不是一遍又一遍。

<小时/>

编辑- Rein 在下面提到 nub 的复杂度是 O(n^2)，因此您应该避免使用上面的第一个解决方案，而选择 O(n log n)，正如 Data.Set.fromList 应该是的那样。正如其他人在评论中提到的，您需要强制 Ord a 以获得适当的复杂性 O(n log n)，Data.Set 可以，nub 则不需要.

我将保留两个解决方案(性能差和性能好)，因为我认为由此产生的讨论是有用的。