This is an implementation of Mergesort using higher order functions,guards,where and recursion.
However getting an error from compiler 6:26: parse error on input ‘=’
mergeSort :: ([a] -> [a] -> [a]) -> [a] -> [a] mergeSort merge xs | length xs < 2 = xs | otherwise = merge (mergeSort merge first) (mergeSort merge second) where first = take half xs second = drop half xs half = (length xs) `div` 2I can't see whats wrong? or rather I don't understand the compiler.
14 Answers
Halving a list is not an O(1) operation but O(n), so the given solutions introduce additional costs compared to the imperative version of merge sort. One way to avoid halving is to simply start merging directly by making singletons and then merging every two consecutive lists:
sort :: (Ord a) => [a] -> [a]
sort = mergeAll . map (:[]) where mergeAll [] = [] mergeAll [t] = t mergeAll xs = mergeAll (mergePairs xs) mergePairs (x:y:xs) = merge x y:mergePairs xs mergePairs xs = xswhere merge is already given by others.
Another msort implementation in Haskell;
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) | x < y = x:merge xs (y:ys) | otherwise = y:merge (x:xs) ys
halve :: [a] -> ([a],[a])
halve xs = (take lhx xs, drop lhx xs) where lhx = length xs `div` 2
msort :: Ord a => [a] -> [a]
msort [] = []
msort [x] = [x]
msort xs = merge (msort left) (msort right) where (left,right) = halve xsHaskell is an indentation sensitive programming language, you simply need to fix that (btw. if you are using tabs change that to using spaces).
mergeSort :: ([a] -> [a] -> [a]) -> [a] -> [a]
mergeSort merge xs | length xs < 2 = xs | otherwise = merge (mergeSort merge first) (mergeSort merge second) where first = take half xs second = drop half xs half = length xs `div` 2None of these solutions is as smart as Haskell's own solution, which runs on the idea that in the worst case scenario's these proposed algorithms is still run Theta (n log n) even if the list to be sorted is already trivially sorted.
Haskell's solution is to merge lists of strictly decreasing (and increasing values). The simplified code looks like:
mergesort :: Ord a => [a] -> [a]
mergesort xs = unwrap (until single (pairWith merge) (runs xs))
runs :: Ord a => [a] -> [[a]]
runs = foldr op [] where op x [] = [[x]] op x ((y:xs):xss) | x <= y = (x:y:xs):xss | otherwise = [x]:(y:xs):xss`This will run Theta(n)
Haskell's version is smarter still because it will do an up run and a down run.
As usual I am in awe with the cleverness of Haskell!
1
