如果condition为true,则合并多个列表

Question

我一直试图绕过这一段时间,但似乎我缺乏Haskell经验只是不能让我通过它.我在Stackoverflow上找不到类似的问题(大多数都与合并所有子列表有关,没有任何条件)

所以这就是它.假设我有一个这样的列表列表:

[[1, 2, 3], [3, 5, 6], [20, 21, 22]]

如果某种条件成立,是否存在合并列表的有效方法？假设我需要合并至少共享一个元素的列表.例如,结果将是:

[[1, 2, 3, 3, 5, 6], [20, 21, 22]]

另一个例子(当所有列表都可以合并时):

[[1, 2], [2, 3], [3, 4]]

结果如下:

[[1, 2, 2, 3, 3, 4]]

谢谢你的帮助!

Answer 1

我不知道如何评价效率，但我们可以分解正在发生的事情并至少获得几种不同的功能。特定的功能可能是可以优化的，但重要的是弄清楚到底需要什么。

让我重新表述一下这个问题：对于某些集合 X、某些二元关系 R 和某些二元运算 +，产生一个集合 Q = {x+y | x在X中，y在X中，xRy}。因此，对于您的示例，我们可能将 X 视为一组列表，R 为“xRy 当且仅当 x 和 y 中至少有一个元素”，而 + 为++。

幼稚的实现可能只是复制集合构建器符号本身

shareElement :: Eq a => [a] -> [a] -> Bool
shareElement xs ys = or [x == y | x <- xs, y <- ys]

v1 :: (a -> a -> Bool) -> (a -> a -> b) -> [a] -> [b]
v1 (?) (<>) xs = [x <> y | x <- xs, y <- xs, x ? y]

那么p = v1 shareElement (++) :: Eq a => [[a]] -> [[a]]可能会实现你想要的。但它可能不会。

Prelude> p [[1], [1]]
[[1,1],[1,1],[1,1],[1,1]]

最明显的问题是我们得到四个副本：两个来自将列表与自身合并，两个来自“双向”彼此合并列表。出现问题是因为List与不同，Set所以我们无法杀死唯一值。当然，这是一个简单的解决方案，我们将Set在任何地方使用

import Data.Set as Set

v2 :: (a -> a -> Bool) -> (a -> a -> b) -> Set.Set a -> Set.Set b
v2 (?) (<>) = Set.fromList . v1 (?) (<>) . Set.toList

所以我们可以再试p = v2 (shareElement一次Set.toList) Set.union

Prelude Set> p $ Set.fromList $ map Set.fromList [[1,2], [2,1]]
fromList [fromList [1,2]]

这似乎有效。请注意，我们必须“遍历”，List因为Set无法成为其实例Monad或Applicative由于其Ord约束。

我还注意到，有很多丢失的行为Set。例如，当我们的关系是对称的时，我们要么丢弃列表中的订单信息，要么必须处理x <> y两者y <> x。

一些更方便的版本可以写成

v3 :: Monoid a => (a -> a -> Bool) -> [a] -> [a]
v3 r = v2 r mappend

如果我们假设关系是等式关系，则可以建立更有效的关系，因为从那时起，O(n^2)我们可以在其中进行操作，而不是进行操作O(nd)，其中d是关系的分区（陪集）的数量。

一般来说，这是一个非常有趣的问题。