编写没有模式匹配的双递归函数

Question

合并排序中使用的merge函数可以定义为：

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

该函数只是通过获取列表的头部来生成结果，其中相对较小的测试条件为"更真实"，其中对于空列表的不存在的头部为假，并且两个列表只遍历一次。因此，应该可以使用通用迭代函数，并将x < y谓词给出的两个执行路径合并为一个，这样该函数读起来更像我第一句话中的英文描述。我该怎么做？

尽管merge函数已经完全可读，但我有时发现双递归函数很难编写，所以我很乐意学习更多方法。

Answer 1

您可以将模式匹配一分为二：

merge (a:as) bs = loop bs where
loop (b:bs) | b < a = b : loop bs
loop bs             = a : merge as bs
merge [] bs = bs

也可以用span来表示

merge (a:as) bs = lts ++ a : merge as ges
where (lts, ges) = span (<a) bs
merge [] bs = bs

Answer 2

老实说，我觉得你的英文描述很难理解。其中测试条件...是"更真实"——什么？ 但我会尝试，因为我喜欢玩弄措辞。 首先，我们需要一种方法来表达"对于不存在的空列表的头部为假"。 我为此想到的是，我们需要像Maybe这样的数据类型，但"无"的情况是"无限大"。 以下操作即可：

data AdjInf a = Finite a | Infinite
deriving (Eq, Ord)

(就像Maybe一样，但构造函数顺序颠倒了——Ord派生负责其余的！

我们可以根据这一点获得列表的头部：

head' :: [a] -> AdjInf a
head' [] = Infinite
head' (x:xs) = Finite x

所以现在我们有：

merge :: (Ord a) => [a] -> [a] -> [a]
merge [] [] = []
merge xs ys = next : merge smaller bigger
where
(next : smaller, bigger)
| head' xs <= head' ys = (xs, ys)
| otherwise            = (ys, xs)

这可能符合您的标准。 (这个递归模式是一个列表变形，所以你可以用unfoldr来写(

我会避免这种特定的实现，因为next : smaller模式匹配将始终成功这一事实非常微妙。 如果列表包含比较相等的不同元素(即，此merge不是"稳定"(，则也不是完全相同的功能。

Answer 3

您可以根据测试结果使用不同的参数进行单个递归调用。

merge xxs@(x:xs) yys@(y:ys) =
let (z, xs', ys') = if x <= y then (x, xs, yys) else (y, xxs, ys)
in z : merge xs' ys'
merge [] ys = ys
merge xs [] = xs

PS，我不会称您的merge为双重递归。每个代码路径最多有一个递归调用。