3

So i have this function and when i try to use it like this: mergeSortedLists [1,1] [1,1] it gives me an error:

[1,1*** Exception: SortFunctions.hs:(86,1)-(91,89): Non-exhaustive patterns in function mergeSortedLists

85 mergeSortedLists :: (Ord t)       => [t] -> [t] -> [t]
86 mergeSortedLists [] []            = []
87 mergeSortedLists (x:[]) []        = x:[]
88 mergeSortedLists [] (y:[])        = y:[] 
89 mergeSortedLists (x:[]) (y:[])    = (max x y) : (min x y) : []
90 mergeSortedLists (x:tail1) (y:tail2) | x > y  = x : (mergeSortedLists tail1     (y:tail2))
91                                      | otherwise = y : (mergeSortedLists (x:tail1) tail2)

I can't figure out the source of a problem since i think i covered every case possible. What could be the problem here?

Alehar
  • 639
  • 5
  • 16

1 Answers1

9

Your patterns for the second and third cases cover lists of length 1 merged with an empty list, but nothing covers longer lists merged with the empty list. That is, you didn't cover cases like this:

mergeSortedLists [3, 2, 1] []
mergeSortedLists [] [3, 2, 1]

Here's a function that does what I think you are trying to do in fewer cases:

mergeSortedLists :: (Ord t) => [t] -> [t] -> [t]
mergeSortedLists x [] = x
mergeSortedLists [] y = y
mergeSortedLists (x:tail1) (y:tail2)
    | x > y     = x : (mergeSortedLists tail1 (y:tail2))
    | otherwise = y : (mergeSortedLists (x:tail1) tail2)

(Also, isn't your function technically merging reverse sorted lists?)

Aaron Rotenberg
  • 972
  • 7
  • 22
  • Your solution works perfectly, thank you! Well yeah, they are sorted in descending way. I guess i should pass (Ord a => a -> a -> Bool) to make it more generic. – Alehar Jul 24 '12 at 07:00
  • The way I would do this is to always sort in "standard" (ascending) order w/r/t whatever the Ord implementation is. If the user wants reverse order they can newtype the input type and implement Ord with the comparison reversed. (Actually I'm surprised that AFAICT the Haskell libraries do not have a generic newtype for this predefined.) – Aaron Rotenberg Jul 24 '12 at 13:02