Haskell中mergeSorted函数执行时永久挂起的原因排查

问题根源 #

你的mergeSorted挂死是where块里的循环定义导致的，属于变量名混用搞出来的无限递归：

where
  (y:ys) = sortedYs
  (x:xs) = sortedXs
  sortedYs = qsort ys
  sortedXs = qsort xs

这段逻辑完全是自引用的死结：

• 你要匹配出x和xs，必须先算出sortedXs
• 但你定义sortedXs的时候，传给qsort的参数恰恰是还没匹配出来的xs
sortedYs也是完全一样的问题，只要传入两个非空列表，代码就会卡在这个自引用的循环里，永远不会返回结果。

另外你逻辑上还有个疏漏：你写的逐元素比较的逻辑，本来是用来合并两个已经有序的列表的，但你根本没对传入的两个完整原始列表做排序，qsort的入参是从还没算出来的排序结果里拆出来的尾部，完全没用到完整的入参listX和listY，就算解决了死循环也拿不到正确结果。

修正方法 #

把排序和归并逻辑拆分开：先把两个原始输入列表分别排好序，再对两个有序列表做归并即可。
修正后的完整代码：

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
  where
    smaller = [a | a <- xs, a <= x]
    larger = [b | b <- xs, b > x]

-- 专门处理两个有序列表的归并
mergeOrdered :: Ord a => [a] -> [a] -> [a]
mergeOrdered l [] = l
mergeOrdered [] r = r
mergeOrdered (x:xs) (y:ys)
  | x <= y    = x : mergeOrdered xs (y:ys)
  | otherwise = y : mergeOrdered (x:xs) ys

mergeSorted :: Ord a => [a] -> [a] -> [a]
mergeSorted l r = mergeOrdered (qsort l) (qsort r)

测试第一个示例mergeSorted [2,6,5] [3,4,1]，会正确返回[1,2,3,4,5,6]。
补充：你写的第二个示例mergeSorted [] [4,1]预期返回[4,1]和函数“返回有序列表”的定位矛盾，按逻辑应该返回排序后的[1,4]，属于写示例时的笔误。

内容的提问来源于stack exchange，提问作者jfhector