реализация 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