MergeSort w/ Custom Functions

Question

Please review my implementation of mergesort:

mergesort' :: (Ord a) => [a] -> [a]
mergesort' [] = []
mergesort' xs = merge' (sort' fst', sort' snd')
 where fst' = take half xs
 snd' = drop half xs
 half = len `div` 2 
 len = length xs
merge' :: (Ord a) => ([a], [a]) -> [a]
merge' ([], []) = []
merge' ([], ys) = ys
merge' (xs, []) = xs 
merge' (x:xs, y:ys) = if x < y then x : merge' (xs, y:ys) else y : merge'(x:xs, ys)
sort' :: (Ord a) => [a] -> [a]
sort' [] = []
sort' (x:xs) = m : sort' rest
 where m = foldl (\acc x -> if x < acc then x else acc) x xs
 rest = filterOne' (/= m) (x:xs)
filterOne' :: (a -> Bool) -> [a] -> [a]
filterOne' _ [] = []
filterOne' f (x:xs) = if not $ f x then xs else x : filterOne' f xs

If it doesn't adhere to the mergesort algorithm, please let me know.

Also, is there a Haskell library function for my filterOne'?

Answer 1

This isn't mergesort! sort' is a different sorting algorithm entirely, so you end up only performing one merge step before kicking it over to (I believe) selection sort.

First let's address the easy stylistic issues so we have a good base to work from. The primary issue is that the argument passed to merge' is a tuple, which is unnecessary, uncurried, and not very Haskell-y. I'll also drop the extra apostrophes where there isn't an actual naming conflict with the Prelude. We use as-patterns to avoid reconstructing patterns we just deconstructed. And let's just toss sort' and filterOne', they're not part of the solution!

mergesort :: (Ord a) => [a] -> [a]
mergesort [] = []
mergesort xs = merge (??? left) (??? right)
 where half = (length xs) `div` 2
 left = take half xs
 right = drop half xs
merge :: (Ord a) => [a] -> [a] -> [a]
merge [] [] = []
merge xs [] = xs
merge [] ys = ys
merge xss@(x:xs) yss@(y:ys) = if x <= y then x : merge xs yss else y : merge xss ys
 -- ^ Less than *or equal* so our sort is stable

One question is what goes in for the ??? where we used to call sort'? Well, mergesort!

One more complex issue of style is the usage of if in merge. Top-level ifs are better represented as guards in Haskell, it's easier to extend guards and their usage is more idiomatic.

merge xss@(x:xs) yss@(y:ys) | x <= y = x : merge xs yss
 | otherwise = y : merge xss ys

One small change we can make is adding another base case to mergesort to account for lists of length 1, which are by definition sorted.

mergesort xs@[x] = xs

There's only one more improvement I'd make to this, and that's to call splitAt rather than take and drop in mergesort. Using both take and drop leads to walking half the list twice in each recursive step where we can walk it only once by doing some more bookkeeping. splitAt takes an index to split a list at, and returns the prefix and remainder just like using take and drop separately would.

So putting all of that together, here's the final version.

mergesort :: (Ord a) => [a] -> [a]
mergesort [] = []
mergesort xs@[x] = xs
mergesort xs = merge (mergesort left) (mergesort right)
 where half = (length xs) `div` 2
 (left, right) = splitAt half xs
merge :: (Ord a) => [a] -> [a] -> [a]
merge [] [] = []
merge xs [] = xs
merge [] ys = ys
merge xss@(x:xs) yss@(y:ys) | x <= y = x : merge xs yss
 | otherwise = y : merge xss ys

• Kevin Meredith: when I re-implemented after peeking at your answer, I first ran into a non-convergent (never completed) result since I hadn't properly handled the mergesort [x] case.

Answer 2

For your merge function, you can simplify it a bit using as-patterns. This allows you to bind both x, xs, and the full list to a name:

merge' (xs'@(x:xs), ys'@(y:ys)) = if x < y then x : merge' (xs, ys') else y : merge (xs', ys)

This basically says "Use the name xs' to refer to (x:xs)".

The closest thing in Data.List to your filterOne' function is probably span. This can be used as follows:

filterOne' :: (a -> Bool) -> [a] -> [a]
filterOne' f xs = fst z ++ (tail $ snd z)
 where z = span f xs