haskell - 为什么这段代码在我执行的时候挂了？

Question

我要实现的目标

作为练习，我正在尝试编写一个“mergeSorted”函数，它接受两个列表并返回一个列表，其中两个列表中的所有元素都已排序。

例如:

• mergeSorted [2,6,5] [3,4,1] 应该返回 [1,2,3,4,5,6]
• mergeSorted [] [4,1] 应该返回 [4,1]

这是我写的:

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]

mergeSorted :: Ord a => [a] -> [a] -> [a]
mergeSorted listX [] = qsort listX
mergeSorted [] listY = qsort listY
mergeSorted listX listY   | x <= y      = x : mergeSorted xs (y:ys)
                          | otherwise   = y : mergeSorted (x:xs) ys
                          where
                            (y:ys) = sortedYs
                            (x:xs) = sortedXs
                            sortedYs = qsort ys
                            sortedXs = qsort xs

问题

qsort 代码似乎运行良好。但是我的 mergeSorted 不工作。如果我在 GHCi 中使用两个不为空的列表执行 mergeSorted，执行将永远挂起。 (即我从来没有得到结果)。

我的问题

你能告诉我我的 mergeSorted 代码有什么问题吗？

Answer 1

你写(y:ys) = sortedYs, 和sortedYs = qsort ys，因此你对排序的结果进行排序，从而陷入无限循环.但即使你设法解决了这个问题，它也不会很有效，因为对于每个项目，你将再次对剩余项目列表进行排序。

我认为最好将其简化为合并的辅助函数，以及另一个调用 qsort(或其他东西)作为预处理步骤的函数:

import Data.Function(on)

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge xa@(x:xs) ya@(y:ys)
    | x <= y = x : merge xs ya
    | otherwise = y : merge xa ys

mergeSorted :: Ord a => [a] -> [a] -> [a]
mergeSorted = merge `on` qsort