sorting - 这种合并排序的实现好吗？

Question

我昨晚刚开始学习 Haskell，以前从未使用过函数式编程语言。
我只想知道我的合并排序实现是好是坏，究竟是好是坏。
也许它甚至是错误的 - 它确实排序但也许算法不是我认为的合并排序。

只要告诉我我可以在这里改进的一切。我自己认为这是一个非常清晰和简单的实现。
感谢您的建议，这是代码:)

merge [] ys = ys
merge xs [] = xs
merge xs ys =  sorted : merge left right
                where 
                    sorted = if head(xs) < head(ys) then head(xs) else head(ys)
                    left = if head(xs) <= head(ys) then tail(xs) else xs
                    right = if head(xs) > head(ys) then tail(ys) else ys

msort [] = []
msort [x] = [x]
msort xs = merge (msort left) (msort right)
            where 
                left = take (div (length xs) 2) xs
                right = drop (div (length xs) 2) xs

Answer 1

好吧，首先，我们可以使用模式匹配将 merge 重写得更优雅一些

merge [] ys = ys
merge xs [] = xs
merge xs@(x:xs1) ys@(y:ys1)
    | x <= y = x : merge xs1 ys
    | otherwise = y : merge xs ys1

一般来说，您应该避免使用 head和 tail因为它们有点不安全(它们会为空列表引发错误)并尽可能使用模式匹配。
msort的执行几乎是正确的，除了我们可以以更有效的方式拆分列表。那是因为 length xs - 需要 O(N) 才能完成。编译器可能会保存您并缓存 length 的结果。调用以便第二次调用 length不会再次遍历列表。但是 take和 drop几乎会导致另外两次遍历，因此使用 3 次遍历拆分列表，这可能被证明是昂贵的。我们可以通过将列表分成两个列表来做得更好——第一个列表包含奇数位置的元素，第二个列表包含偶数位置的元素，如下所示:

msort [] = []
msort [x] = [x]
msort xs = merge (msort first) (msort second)
    where
        (first, second) = splitInHalves xs
        splitInHalves [] = ([], [])
        splitInHalves [x] = ([x], [])
        splitInHalves (x:y:xs) =
            let (xs1, ys1) = splitInHalves xs
            in  (x:xs1, y:ys1)

这使您在 O(NlogN) 时间内获得相同的合并排序。感觉不同，因为您可能会用 C 之类的命令式语言就地实现它(通过修改原始列表)。这个版本在内存上的成本略高，但它确实有它的优点 - 更容易推理，因此更易于维护，也很容易 parallelize除了算法本身之外，不关心其他任何事情——这正是一种好的编程语言应该为使用它的开发人员提供的。

编辑 1:

如果语法有点多，这里有一些资源:

Pattern Matching - 带有 @ 的位符号称为 as-pattern。你会在那里找到它

let是一个关键字，用于声明要在其后的表达式中使用的变量(而 where 将变量绑定(bind)到它之前的表达式中)。有关 Haskell 语法的更多信息，包括守卫(带有 | condition = value 的东西)可以在这里找到，在 Learn You a Haskell 的这一章中

编辑 2:

@is7s 提出了一个更简洁的 splitInHalves 版本。使用 foldr function :

splitInHalves = foldr (\x (l,r) -> (x:r,l)) ([],[])

编辑 3:

这是另一个答案，它提供了合并排序的替代实现，它还具有 stable 的属性。 :

Lazy Evaluation and Time Complexity

希望这有助于并欢迎来到函数式编程的精彩世界!