这种实现合并排序好吗？

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等命令式语言来实现它(通过修改原始列表).这个版本在内存上的成本略高,但确实有它的优点 - 它更容易推理因此它更易于维护,而且除了算法本身之外,它很容易并行化,而不关心其他任何东西 - 这正是一个好的编程语言应该为使用它的开发人员提供的.

编辑1:

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

• 模式匹配 - 带@符号的位称为as-pattern.你会在那里找到它
• let是一个关键字,用于声明要在其后面的表达式中使用where的变量(而绑定在其前面的表达式中的变量).有关Haskell语法的更多信息,包括警卫(其中包含的内容| condition = value)可以在这里找到,在本章中了解一下Haskell

编辑2:

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

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

编辑3:

这是另一个答案,提供了合并排序的替代实现,它也具有稳定的属性:

懒惰的评估和时间复杂性

希望这有助于并欢迎来到功能编程的精彩世界!