0

大家好，我正在尝试在 haskel 中重现合并排序，这是我的代码：

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

-- split
splitIn2 :: (Ord a) => [a] -> ([a],[a])
splitIn2 [] = ([],[])
splitIn2 xs = splitAt ((length xs `div` 2)+1) xs

-- msort
msort :: (Ord a) => [a] -> [a]
msort [] = []
msort [x] = [x]
msort (xs) = merge (msort as) (msort bs)
    where (as,bs) = splitIn2 xs

它在 ghc 上编译，适用于：

*Main> msort([])
[]
*Main> msort([1])
[1]

然而它不能正确地完成它的工作，因为它开始无限循环（至少这是我的想法）并且它不打印任何东西。

我认为这是因为我没有像在其他递归实验中那样从列表中删除元素，有什么建议吗？

4

2 回答 2

8

问题是当length xs == 2,

(length xs `div` 2) + 1
= (2 `div` 2) + 1
= 1 + 1
= 2

并splitAt 2 xs返回(xs, [])。由于第一个列表仍然是 length 2， 将在无限循环中再次msort尝试向下。splitIn2

要解决这个问题，您可以简单地摆脱+1; 这是完全没有必要的。您还可以消除空列表的特殊情况，因为splitAt 0 [] = ([], []).

splitIn2 xs = splitAt (length xs `div` 2) xs
于 2012-11-25T22:52:15.433 回答
2 
*Main> splitIn2 [1, 2, 3, 0, 5, 6]
([1,2,3,0],[5,6])

并经过小改动（删除+1）：

splitIn2 xs = splitAt ((length xs `div` 2)) xs

有用：

*Main> splitIn2 [1, 2, 3, 0, 5, 6]
([1,2,3],[0,5,6])
*Main> msort [1, 2, 3, 0, 5, 6]
[0,1,2,3,5,6]
于 2012-11-25T22:42:51.663 回答