Haskell归并排序

Question

这是使用高阶函数、守卫、where和递归实现的Mergesort。但是编译器报错：6:26：输入上的解析错误“=”。

 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

我看不出有什么问题？或者说我不理解编译器。

- emuterisa

---

顺便说一下，如果您正在使用长度，这是一个O（n）操作 - 因此，您正在产生不必要的开销。一般来说，如果您在使用（单向）链表时经常使用长度索引，则可能使用了错误的数据结构。 - epsilonhalbe

Answer 1

将列表减半不是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已经由其他人提供。

- L.-T. Chen

---

一个小而美的优化：不要将列表分解为单个元素，而是将其分解为两个元素的排序列表。这样可以节省O(n)的内存分配，而且代码复杂度也不会增加太多。 - dfeuer

Answer 2

这是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

- Redu

---

为了提高效率，合并函数不应该是尾递归函数吗？我还没有进行基准测试，但仅在repl.it上运行一个包含30000个值的列表时，尾递归会稍微快一些：https://repl.it/@faebl/Sorting - Fabian Schneider

msort 缺少方程式 "msort [] = []"。否则，如果要排序的数组为空，则会一直执行下去。 - Cuban coffee

@Cuban coffee 感谢提醒，已经更正。 - Redu

@FabianSchneider，不应该。Haskell列表在它们的元素和（这里很重要的）它们的尾部都是惰性的。因此，用上述代码构造Haskell列表是高效的：列表构造器首先被分配，只有后来才评估尾部。 - dfeuer

@dfeuer 感谢提供的信息；我考虑了一下，读了一些关于惰性和列表构造器的资料，现在有点明白了。而且在 repl.it 上进行“基准测试”并不是很可靠的事情... - Fabian Schneider

Answer 3

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

- epsilonhalbe

---

似乎已经修复了那个错误，但现在当我运行函数mergeSort时，它说merge不在作用域内。这是否意味着代码不完整，我需要进一步定义merge的实际操作？ - emuterisa

@emuterisa 如果这个回答解决了你的问题，即使它是三年前的，也应该被接受。 - Fabian Schneider

Answer 4

这些解决方案都不如Haskell自己的解决方案聪明，它运用了一种思想，在最坏情况下，即使要排序的列表已经是简单排序的，这些提出的算法仍然可以运行Theta（n log n）。

Haskell的解决方案是合并严格递减（和递增）值的列表。简化后的代码如下：

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`

这将运行Theta(n)。

Haskell版本更加智能，因为它会进行上行和下行运行。

像往常一样，我对Haskell的聪明才智感到敬畏！

- Lau Sandt

---

Data.List 中的版本确实很聪明，作为一种通用排序方式。但并不是每个应用程序都期望元素已经部分排序好了。在这种应用程序中，通常更快的方法是不尝试检测已排序元素的运行。此外，有相当多的应用程序更注重运行时间的可预测性，而不是速度的快慢。在这些应用程序中，最好不要利用排序运行。 - dfeuer