Haskell中的聯合函數

Question

我一直在圍繞Haskell進行編碼，但無法掌握實現聯合函數的想法。 我也發現了一些嵌入Haskell平臺的函數定義。但問題是我需要一個簡潔易懂的方式才能使它工作。 任何人都可以幫助我嗎？

Answer 1

假設你正在談論union :: Eq a => [a] -> [a] -> [a]這需要兩個輸入列表，並返回一個包含了所有每個參數列表元素的第三列表，那麼它在Data.List這是在base包中定義。

在它分成兩個函數的源，廣義功能unionBy這需要平等且然後（類型等於(==) :: a -> a -> Bool的函數）的一個自定義的定義定義了通過在(==)傳遞作爲具體使用Eq類型類的一個實行平等。

union     :: (Eq a) => [a] -> [a] -> [a] 
union     = unionBy (==) 

我們可以替代(==)到unionBy代碼，但是，作爲Haskell允許我們用等式推理。

union = unionBy (==) 

-- so... 

union  :: Eq a => [a] -> [a] -> [a] 
union xs ys = xs ++ foldl (flip (deleteBy (==))) (nubBy (==) ys) xs 

此相同的圖案在deleteBy和nubBy，這兩者遵循相同的慣例，unionBy定義發生兩次以上。 delete從列表中移除一個元素，nub返回一個唯一元素列表。我們將再次簡化定義以消除(==)的所有痕跡，並簡單地假定元素a已定義Eq。

union xs ys = xs ++ foldl (flip delete) (nub ys) xs 

現在定義可能更具可讀性。 xs和ys的union是xs附加到已由foldl (flip delete) _ xs處理的ys的唯一（「nub牀」）值。 foldl的最終結果就是一個一個嘗試到delete的每個元素xs從(nub ys)。這意味着union xs ys是xs附加到ys中的每個獨特元素少於xs中的那些元素。

---

順便說一句，與此源在手，我們可以看到的union一些古怪的行爲，例如如何在第一個參數從所述第二參數

union [1,1,2] [2] == [1,1,2] 
union [2] [1,1,2] == [2,1] 

這是有點對待重複不同的結果是使用[]來表示Set類似union的概念。但是，如果我們使用Set.fromList查看結果，那麼我們很好。

xs, ys :: Eq a => [a] 
Set.fromList (xs `union` ys) == Set.fromList xs `Set.union` Set.fromList ys 

這也給我們的union

union xs ys = Set.toList (Set.fromList xs `Set.union` Set.fromList ys) 

---

那麼另一個定義請問是怎麼foldl伎倆工作？讓我們解開foldl的定義來查看，再次濫用等式推理。

union xs ys = xs ++ (case xs of 
    []  -> nub ys 
    (x:xs') -> foldl (flip delete) (delete x (nub ys)) xs' 
) 

這將使超過xs元素特技更加明顯，它的循環，從(nub ys)刪除它們一個接一個。

---

雖然希望這有助於使代碼union更清晰一點，真正帶回家應該是均分的推理是解剖Haskell代碼的強大工具。不要害怕通過手動內嵌函數的定義來直接簡化代碼。