我很困惑为什么这种合并排序的实现不起作用？

Question

我是 Haskell 的新手，我正在尝试实现归并排序，但它不起作用，我很困惑为什么？

我的代码：

halve :: [a] -> ([a],[a])
halve xs = splitAt (length xs `div` 2) xs

merge :: [Int] -> [Int] -> [Int]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) =
         if x < y
                 then x:(merge xs (y:ys))
                 else y:(merge (x:xs) ys)

msort :: [Int] -> [Int]
msort [] = []
msort xs 
    | length xs <= 1 = xs
    | otherwise      = merge (msort fst(halve xs)) (msort snd(halve xs))

在msort主体中，我对它应该如何工作的理解是，如果长度xs小于或等于，1则返回列表。否则，它将列表减半xs并mosrt再次递归开始，直到length等于或小于 1，此时它对其应用合并。

我错过了什么/这是怎么回事？

任何帮助表示赞赏:)

Answer 1

您在递归msort调用中忘记了括号：

msort :: [Int] -> [Int]
msort xs 
    | length xs <= 1 = xs
    | otherwise = merge (msort (fst (halve xs))) (msort (snd (halve xs)))

话虽如此，使用length通常不是一个好主意，因为它在O(n) 中运行。这里最好使用模式匹配。此外，您可以使用where子句来避免计算halve xs两次：

msort :: Ord a => [a] -> [a]
msort [] = []
msort [x] = [x]
msort xs = merge (msort la) (msort lb)
    where (la, lb) = halve xs

的halve可构造在这里我们每第二元件传递到2元组，等的元件中的一个：

halve :: [a] -> ([a], [a])
halve [] = ([], [])
halve (x:xs) = (x:ya, yb)
    where (yb, ya) = halve xs

或使用foldr模式：

halve :: [a] -> ([a], [a])
halve = foldr (\x (yb, ya) -> (x:ya, yb)) ([], [])

并且merge可以通过使用as-patterns更优雅地实现：

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge xa@(x:xs) ya@(y:ys)
    | x <= y = x : merge xs ya
    | otherwise = y : merge xa ys