无需模式匹配编写双递归函数：归并排序merge函数优化探讨

问题回顾 #

你给出的Haskell归并函数实现非常经典：

merge a@(x:xs) b@(y:ys) | x < y = x : merge xs b | otherwise = y : merge a ys
merge [] b = b
merge a [] = a

它通过每次选取两个非空列表中相对更小的头部元素构建结果，且仅遍历两个列表一次。你想知道是否能借助通用迭代函数合并两条执行路径，同时希望了解更多双递归函数的实现思路。

一、用通用迭代函数合并执行路径 #

当然可以！Haskell的Data.List.unfoldr就是非常适合的通用迭代工具——它能从一个“种子”状态逐步生成列表元素，完美贴合“每次选更小头部”的核心逻辑。

我们可以把两个待合并的列表作为种子，每次从种子里取出符合条件的元素，同时更新种子为剩下的列表，直到两个列表都为空。实现如下：

import Data.List (unfoldr)

merge :: Ord a => [a] -> [a] -> [a]
merge a b = unfoldr nextStep (a, b)
  where
    nextStep (x:xs, y:ys) = Just (if x < y then (x, (xs, y:ys)) else (y, (x:xs, ys)))
    nextStep (x:xs, []) = Just (x, (xs, []))
    nextStep ([], y:ys) = Just (y, ([], ys))
    nextStep ([], []) = Nothing

这个实现把原来的两条递归路径合并到了nextStep函数中：

• 无论当前两个列表的状态如何，nextStep都会判断该取出哪个元素，并返回新的种子状态
• 当其中一个列表为空时，会逐个取出另一个列表的剩余元素，直到全部耗尽
• 逻辑完全贴合“选取相对更小的头部生成结果”的描述，而且避免了显式的双递归调用

二、双递归函数的实现思路 #

双递归确实容易让人头大，我分享几个实用的思路帮你降低难度：

• 先搞定边界条件：
  递归的终止条件永远是第一步要明确的。比如归并函数里，只要其中一个列表为空，直接返回另一个列表即可——这是最基础的终止情况，先写好它，后续就不用再考虑空列表的干扰。

• 从问题分解入手：
  双递归的核心是把原问题分解成结构相同的子问题。归并的本质是“合并两个已排序列表”，每次取出最小元素后，剩下的两个列表依然是已排序的，完全符合原问题的输入要求，所以自然可以递归调用自身处理子问题。

• 利用模式匹配简化逻辑：
  Haskell的模式匹配是处理列表递归的利器。比如a@(x:xs)这种as-pattern，能同时拿到整个列表、头部元素和尾部列表，不用手动拆分，让双递归的调用关系一目了然——你清楚地知道每次递归是在处理哪个列表的剩余部分。

• 用高阶函数替代显式递归：
  就像刚才用unfoldr的方式，把显式的双递归转化为迭代式的思维。你不用再跟踪两个递归调用的栈状态，只需要关注当前的种子（两个列表）如何更新，大大降低了思维复杂度。

• 手动模拟递归过程：
  拿小例子手动走一遍递归流程，比如merge [1,3] [2,4]，一步步写出每个递归调用的输入和输出，能帮你直观理解双递归的调用链，减少编写时的困惑。

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