1

I try to understand, what's the difference between the second two algorithms.

The first one (merge) works well, but when I try to convert the algorithm to Guarded notation (merge') I get a "Non-exhaustive patterns ..." exception.

But why is the third version (merge'') working? It is almost the same like merge', there has to be something with the list (x:xs) that I don't understand.

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

2 Answers 2

5

In merge' and merge'' you assume the first argument to be of the form x:xs, this excludes the empty list, and is causing the problems.

For example

head z@(x:xs) = x

will produce 1 as expected when calling head([1,2,3]), but head([]) will throw a Non-exhaustive patterns in function head exception because [] does not match x:xs (the @ is not really important here).

In particular, this means that in merge' the z == [] case can never be matched and also merge'' will throw an exception if you call merge [] [1,2,3] for example.

Also note that in merge'' the case xs == [] is problematic. If, for example, we call merge'' [1] [2], then this case is matched because [1] is 1:[]. Then, just ys, i.e., [2] is returned and the x, which is 1, gets lost.

1

The difference between the last two solutions is that merge' has a dead branch z == [] - this condition will never hold, given that z@(x:xs).

The version merge'' works by mistake - it will break if you try some other inputs, where at some point z==[].

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.