Haskell的歸併執行編譯，但不返回任何

Question

這是我實現：

mergesort :: (Ord a) => [a] -> [a] 
mergesort list = merge (mergesort (left list)) (mergesort (right list)) 
    where 
    left xs = take (div (length xs) 2) xs 
    right xs = drop (div (length xs) 2) xs 
    merge [] ys = ys 
    merge xs [] = xs 
    merge (x:xs) (y:ys) 
     | x <= y = x : merge xs (y:ys) 
     | otherwise = y : merge (x:xs) ys 

代碼編譯，但是當我運行它，我的機器崩潰。我究竟做錯了什麼？

Answer 1

你缺少基礎案例 - 所以你得到無限遞歸。嘗試使用[]或[1]這樣的列表來查看您的示例，您將直接進入該問題。

mergesort :: (Ord a) => [a] -> [a] 
mergesort [] = [] -- < ADDED 
mergesort [x] = [x] -- < ADDED 
mergesort list = merge (mergesort (left list)) (mergesort (right list)) 
    where 
    left xs = take (div (length xs) 2) xs 
    right xs = drop (div (length xs) 2) xs 
    merge [] ys = ys 
    merge xs [] = xs 
    merge (x:xs) (y:ys) 
     | x <= y = x : merge xs (y:ys) 
     | otherwise = y : merge (x:xs) ys