合併Haskell中的兩個排序列表 - 這些算法有什麼區別

Question

我試圖理解，後面兩種算法有什麼區別。

第一個（合併）效果很好，但是當我嘗試將算法轉換爲守護符號（合併）時，我得到了「非窮舉模式...」異常。

但爲什麼第三個版本（合併''）工作？它與合併幾乎相同，必須有我不明白的列表（x：xs）。

1 -- merges two sortedists           
    2 merge xs [] = xs 
    3 merge [] ys = ys 
    4 merge (x:xs) ys 
    5  | x <= head ys = x : (merge xs ys) 
    6  | otherwise = head ys : (merge (x:xs) (tail ys)) 
    7  
    8 -- merges two sorted lists (fails with exception) 
    9 merge' z@(x:xs) ys 
    10  | ys == [] = z 
    11  | z == [] = ys 
    12  | x <= head ys = x : (merge' xs ys) 
    13  | otherwise = head ys : (merge' (x:xs) (tail ys)) 
    14  
    15 
    16 -- merges two sorted lists (exept the last element of the first list) 
    17 merge'' z@(x:xs) ys 
    18  | ys == [] = z 
    19  | xs == [] = ys 
    20  | x <= head ys = x : (merge'' xs ys) 
    21  | otherwise = head ys : (merge'' (x:xs) (tail ys)) 

Answer 1

在merge'和merge''你承擔的第一個參數是這樣的形式x:xs的，這排除了空單，並且導致的問題。

例如

head z@(x:xs) = x 

會產生1調用head([1,2,3])時如預期，但head([])將拋出一個Non-exhaustive patterns in function head例外，因爲[]不匹配x:xs（該@並不重要這裏）。

特別是，這意味着在merge'中，z == []的情況永遠不會匹配，如果您撥打merge [] [1,2,3]例如merge''也會拋出異常。

另請注意，在merge''的情況下xs == []是有問題的。例如，如果我們呼叫merge'' [1] [2]，那麼這種情況是匹配的，因爲[1]是1:[]。然後，只是ys，即，[2]被返回並且x，即1丟失。

Answer 2

最後兩個解決方案之間的區別是，merge'有一個死支z == [] - 這種情況永遠不會成立，因爲z@(x:xs)。

版本merge''錯誤地工作 - 如果您嘗試其他輸入，在某點z==[]處，它會中斷。