haskell中的合并排序进入无限循环

Question

大家好我试图在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]

然而它没有正确地完成它的工作,因为它无限地开始循环(至少这是我的想法)并且它不会打印任何东西.

我认为这是因为我不会像在其他递归实验中那样从列表中删除元素,任何建议？

Answer 1

问题是,什么时候length xs == 2,

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

并splitAt 2 xs返回(xs, []).由于第一个列表仍然很长2,因此 msort将splitIn2在无限循环中再次尝试使用它.

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

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