7

我昨晚刚开始学习 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
4

1 回答 1

14

好吧，首先，我们可以使用模式匹配将 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

一般来说，您应该避免使用headandtail因为它们有点不安全（它们会为空列表引发错误）并尽可能使用模式匹配。

的实现msort几乎是正确的，除了我们可以以更有效的方式拆分列表。那是因为length xs- 需要 O(N) 才能完成。编译器可能会保存您并缓存length调用结果，以便第二次调用length不会再次遍历列表。但是takeanddrop几乎会导致另外两次遍历，因此使用 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）可以在这里找到，在Learn You a Haskell的这一章中

编辑 2：

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

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

编辑 3：

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

惰性评估和时间复杂度

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

于 2012-11-19T14:46:50.173 回答