有條件地合併列表元素

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]]