在Haskell中合并两个排序列表 - 这些算法之间的区别是什么

Question

我试着理解,后两种算法之间有什么区别.

第一个(合并)效果很好,但是当我尝试将算法转换为Guarded表示法(merge')时,我得到了一个"非详尽模式......"异常.

但为什么第三个版本(merge'')有效？它几乎和merge一样,有一些我不理解的列表(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''如果你打电话的话也会抛出异常merge [] [1,2,3].

还要注意,在merge''这种情况下xs == []是有问题的.例如,如果我们调用merge'' [1] [2],那么这种情况是匹配的,因为[1]是1:[].然后,只是ys,即[2]返回,然后x,它1就会丢失.