有条件地合并列表元素

Question

我仍然是haskell的新手，但我努力学习它。但是现在我明白了，我认为我必须学习haskell的全新章节。

所以这是一个包含这些数字Int的列表的列表：

[[5,6,14],[1,2,9],[11,12,13],[6,13,14],[5,13,14]] 

在开始的时候所有内部列表包含三个数字。目标是将所有重叠列表合并为更大的列表：

[[5,6,14],[1,2,9],[11,12,13],[6,13,14],[5,13,14]] 
merging elements at index 0 and 3 because of the common 6 in both lists. 
[[5,6,14,13],[1,2,9],[11,12,13],[5,13,14]] 
merging elements at index 0 and 2 because of the common 13 in both lists. 
[[5,6,14,13,11,12],[1,2,9],[5,13,14]] 
merging elements at index 0 and 2 because of the common 5,13 & 14 in both lists. 
[[5,6,14,13,11,12],[1,2,9]] 

而这应该是函数的结果。列表内部列表的顺序与最内部列表中元素的顺序无关。

我知道如何在任何其他命令式语言中对其进行编码，但在这里我卡住了。

Answer 1

使用List数据结构来做到这一点的一种方法如下。最初写的谓词功能找出如果两个列表中有它们之间没有任何共同的要素：

hasCommon :: Eq a => [a] -> [a] -> Bool 
hasCommon xs ys = not . null $ intersect xs ys 

λ> hasCommon [1,2,3] [3] 
True 
λ> hasCommon [1,2,3] [4] 
False 

现在，你可以实现一个solve功能，这将给你你想要的功能：

solve :: Eq a => [[a]] -> [[a]] 
solve xs = case xs' of 
      [] -> [] 
      x'@(x:[]) -> x' 
      x'@(x1:x2:[]) -> x' 
      x'@(x1:x2:xs) -> x1:(solve (x2:xs)) 
    where xs' = aux (head xs) (tail xs) [] 
      aux :: Eq a => [a] -> [[a]] -> [[a]] -> [[a]] 
      aux acc [] temp = (acc:temp) 
      aux acc (y:ys) temp = if (acc `hasCommon` y) 
           then aux (union acc y) (ys ++ temp) [] 
           else aux acc ys (y:temp) 

主要部分功能是aux。该函数接受三个参数。该函数的第一个参数是输入列表的首字母，用于将其与输入列表的其余部分进行比较。 aux函数的第二个参数是输入列表的tail。第三个参数是临时变量，用于跟踪已经处理的元素。您可以在函数中处理两种情况：如果输入列表的尾部为空，则返回[acc] ++ temp，这将保留您的结果。这将在现在将要描述的另一种情况下建立起来。在另一种情况下，您检查输入列表的头部是否与输入列表尾部的头部有任何共同元素。如果它有任何共同的元素，那么看看我如何将值传递给aux函数。基本上我用ys ++ temp填充第二个输入，以便我们遍历已遍历的元素。第一个参数是xs和y的联合。在这种情况下的其他部分是不言自明的。

演示在ghci：

λ> solve [[5,6,14],[1,2,9],[11,12,13],[6,13,14],[5,13,14]] 
[[5,6,14,13,11,12],[1,2,9]] 
λ> solve [[5,6,14],[18,19,20],[5,13,14],[1,2,9],[17,18,19],[20,21,22]] 
[[5,6,14,13],[18,19,20,21,22,17],[1,2,9]]