Why is this code hanging when I execute it?

user_7981890 0
Viewed 230

What I'm trying to achieve

As an exercise, I'm trying to write a 'mergeSorted' function which takes two lists, and returns a single list, in which all the elements from the two lists are sorted.

For example:

  • mergeSorted [2,6,5] [3,4,1] should return [1,2,3,4,5,6]
  • mergeSorted [] [4,1] should return [4,1]

Here's what I wrote:

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
  where
    smaller = [a | a <- xs, a <= x]
    larger = [b | b <- xs, b > x]

mergeSorted :: Ord a => [a] -> [a] -> [a]
mergeSorted listX [] = qsort listX
mergeSorted [] listY = qsort listY
mergeSorted listX listY   | x <= y      = x : mergeSorted xs (y:ys)
                          | otherwise   = y : mergeSorted (x:xs) ys
                          where
                            (y:ys) = sortedYs
                            (x:xs) = sortedXs
                            sortedYs = qsort ys
                            sortedXs = qsort xs

The issue

The qsort code seems to be working well. But my mergeSorted isn't working. If I execute mergeSorted with two lists which are not empty in GHCi, execution hangs forever. (i.e. I never get a result).

My question

Please can you tell me what's wrong with my mergeSorted code?

haskell
1 Answers

You write (y:ys) = sortedYs, and sortedYs = qsort ys, hence you sort the result of the sort, and thus get stuck in an infinite loop. But even if you manage to solve that, it would not be very efficient, since for each item, you will sort the list of remaining items again.

I think it is better to simplify this in a helper function for merging, and another one that calls qsort (or something else) as pre-processing step:

import Data.Function(on)

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge xa@(x:xs) ya@(y:ys)
    | x <= y = x : merge xs ya
    | otherwise = y : merge xa ys

mergeSorted :: Ord a => [a] -> [a] -> [a]
mergeSorted = merge `on` qsort
user_675790
Related