你如何有效地找到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 则不需要。

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

Answer 2

如果您正在使用属于Ord类型类的成员的元素(如示例中所示),则可以使用Data.Set:

import qualified Data.Set as Set

whatYouWant = foldl' (Set.union . Set.fromList) Set.empty testSet

这具有以下优点:占用与最大子列表的大小成比例的空间,而不是与Set.fromList . concat解决方案一样的整个连接列表的大小.严格foldl'还可以防止未评估的thunk堆积,防止O(n)堆栈和堆空间使用.

一般来说,Ord约束允许比约束更有效的算法,Eq因为它允许您构建树.这也是其原因nub是O(n^2):更高效的算法要求Ord,而不仅仅是Eq.