在Haskell中解釋這個'合併'函數

Question

我正在學習Haskell，我無法理解這個函數。我正在執行mergesort。我已經實現了mergesort遞歸函數，但我不明白這個「合併」函數在做什麼。我理解命令式語言中的合併排序，但我不明白這裏的語法。

merge []   ys     = ys 
merge xs   []     = xs 
merge xs@(x:xt) ys@(y:yt) | x <= y = x : merge xt ys 
          | otherwise = y : merge xs yt 

Answer 1

merge []   ys     = ys 

如果第一個參數是空的，給第二個參數。

merge xs   []     = xs 

如果第二個參數爲空，則給第一個參數。

merge xs@(x:xt) ys@(y:yt) | x <= y = x : merge xt ys 
          | otherwise = y : merge xs yt 

如果x小於或等於y，利弊（添加到前）×與ys合併的xs其餘部分（其爲xt）的結果。否則y較小，因此將xs與ys（即yt）的其餘部分合並。

xs@(x:xt)是使用「佔位符」進行參數解構。結果是，xs將引用整個第一個參數，而x是頭部，而xt是尾部。

由於合併是遞歸定義的，它會繼續從X和Y利弊元素，直到至少有一個是空的，然後簡單地返回。

酒吧（|）表示"guards"，它允許您以一種很好和簡潔的方式定義條件。

Answer 2

讓我們通過線打破這行：

1. merge [] ys = ys

   這條線圖案的第一列表相匹配。如果第一個列表是空列表（即[]），則返回第二個列表。

2. merge xs [] = xs

   以前一樣，只有扭轉了列表的作用。

3. merge xs@(x:xt) ys@(y:yt)

   模式匹配像僅當列表元素是非空(x:xt)匹配。如果匹配，則將x設置爲第一個元素，並將xt設置爲列表的其餘部分。請記住:是列表構造函數運算符（即1 : [2, 3] == [1, 2, 3]）。 的xs@...前綴意味着整個列表設置爲xs。如果你需要參考整個列表，以及它的頭部和尾部，在同一時間，這非常有用。

Answer 3

函數模式匹配它的兩個參數。讓我們來看看每個單獨的子句：

merge []   ys     = ys 

所以，合併一個空列表和另一個列表ys會導致ys。

merge xs   []     = xs 

這就像第一個條款，只是另一種方式：合併列表xs和空列表給出xs。

merge xs@(x:xt) ys@(y:yt) | x <= y = x : merge xt ys 
          | otherwise = y : merge xs yt 

這是遞歸子句。這裏的功能圖案上兩者的它的參數相匹配，以使得：

• xs是第一列表，並且被解構（通過作爲圖案）到頭部x和尾部xt
• ys是第二個列表，它被解構成它的頭部y，它的尾部yt。現在

，如果第一列表頭是小於或大於所述第二列表（第一保護）的頭部相等，則結果爲只是隨後通過合併的結果的第一列表y的頭第一個列表的尾部（這是xt）和第二個列表ys。如果y小於x，我們做相反的事情。