Haskell 3 路归并排序堆栈溢出异常

Question

我是 Haskell 和函数式编程的新手。我正在尝试用 Haskell 编写 3 路合并排序算法。问题是，当我在 GHCi 中运行代码时，它只返回

*** Exception: stack overflow

。我一直试图理解这个问题，但没有找到解决方案。如果有人可以提供帮助，我将不胜感激。代码和输出如下。

-- three_way.hs

-- Merge function to merge three sorted lists
merge :: Ord a => [a] -> [a] -> [a] -> [a]
merge [] [] [] = []
merge left [] [] = left
merge [] left [] = left
merge [] [] right = right
merge left middle [] = merge left middle []
merge left [] right = merge left [] right
merge (l:ls) (m:ms) (r:rs)
  | l <= m && l <= r = l : merge ls (m:ms) (r:rs)
  | m <= l && m <= r = m : merge (l:ls) ms (r:rs)
  | otherwise = r : merge (l:ls) (m:ms) rs

-- 3-way Merge Sort function
threeWayMergeSort :: Ord a => [a] -> [a]
threeWayMergeSort [] = []
threeWayMergeSort [x] = [x]
threeWayMergeSort xs = merge (threeWayMergeSort left) (threeWayMergeSort middle) (threeWayMergeSort right)
  where
    n = length xs
    left = take (n `div` 3) xs
    middle = take (n `div` 3) (drop (n `div` 3) xs)
    right = drop (2 * (n `div` 3)) xs

$ ghci three_way.hs
GHCi, version 9.4.8: https://www.haskell.org/ghc/  :? for help
[1 of 2] Compiling Main             ( three_way.hs, interpreted )
Ok, one module loaded.
ghci> threeWayMergeSort [2,1]
*** Exception: stack overflow

Answer 1

您进行递归调用而没有“进度”，例如：

merge left middle [] = merge left middle []
merge left [] right = merge left [] right

这意味着如果您调用

merge [1] [2] []

，它只会继续调用

merge [1] [2] []

。

因此，在这种情况下，您应该执行双向合并。