合併排序進入無限循環

Question

大家好，我試圖重現哈斯克爾歸併排序，這裏是我的代碼：

-- 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 

Answer 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]