Haskell新手求助：如何用递归合并两个有序数字列表？

嘿，刚入坑Haskell的小伙伴～递归合并两个有序列表是个非常经典的练习，刚好能帮你熟悉Haskell的递归思维和模式匹配，我来一步步帮你搞定它！

首先得明确：合并两个有序列表的核心逻辑是逐个比较两个列表的当前首元素，把更小的那个先放进结果里，然后递归处理剩下的部分——你之前错误地把元素相加，应该是没抓住这个核心，没关系，我们重新来。

递归的基本情况 #

递归总得有“终止条件”，这里的情况很清晰：

• 如果其中一个列表是空的，那直接返回另一个列表就行（因为空列表和任何列表合并，结果就是那个非空列表）。

递归的核心逻辑 #

当两个列表都非空时，我们比较它们的首元素：

• 如果第一个列表的首元素更小（或相等），就把它放在结果的最前面，然后递归合并第一个列表剩下的部分和第二个完整列表；
• 反之，就把第二个列表的首元素放在前面，递归合并第一个完整列表和第二个列表剩下的部分。

完整代码实现 #

下面是符合这个逻辑的Haskell代码：

-- 约束Ord a是因为我们需要比较列表元素的大小
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys  -- 第一个列表为空，直接返回第二个列表
merge xs [] = xs  -- 第二个列表为空，直接返回第一个列表
merge (x:xs) (y:ys)
  | x <= y    = x : merge xs (y:ys)  -- x更小，先放x，递归处理剩下的xs和原y列表
  | otherwise = y : merge (x:xs) ys  -- y更小，先放y，递归处理原x列表和剩下的ys

测试你的例子（注意小细节） #

你给出的例子里，第二个输入列表[6,9,8,10]其实并不是有序的——这个merge函数的前提是两个输入列表本身已经是升序排列的！如果要得到你期望的[1,3,4,5,6,8,9,10]，你需要先把第二个列表整理成有序的[6,8,9,10]，然后调用：

merge [1,3,4,5] [6,8,9,10]

运行后就会得到你想要的结果啦～

如果你想处理任意两个列表（不管是否有序），可以先对两个列表分别排序再合并，比如：

import Data.List (sort)

mergeUnsorted :: Ord a => [a] -> [a] -> [a]
mergeUnsorted xs ys = merge (sort xs) (sort ys)

这样就算输入的列表无序，也能得到有序的合并结果。

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