Haskell合并排序

Question

这是Mergesort的实现，使用了更高阶的函数，保护，where和递归。

但是从编译器得到一个错误 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` 2

我看不出怎么了？或者我不理解编译器。

Answer 1

Haskell 中的另一个msort实现；

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 xs

Answer 2

Haskell 是一种缩进敏感的编程语言，您只需要修复它（顺便说一句。如果您使用制表符，请将其更改为使用空格）。

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` 2

Answer 3

将列表减半不是O（1）运算，而是O（n），因此与合并排序的命令版本相比，给定的解决方案会带来额外的开销。避免减半的一种方法是简单地通过制作单例直接开始合并，然后合并每两个连续的列表：

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 = xs

其中merge已经被别人给的。