haskell - 如果条件为真，则合并多个列表

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 in X, y in 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是关系的分区(陪集)数量。

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