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