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

老实说,我觉得你的英文描述很难理解。 '测试条件…“更真实”吗? --什么?但我会努力的,因为我喜欢玩弄措辞。首先,我们需要一种方法来表达“对于空列表中不存在的头,在哪里是错误的”。我想到的是我们需要这样的数据类型 Maybe 但对于它来说,“无”的情况是“无限大”。将执行以下操作:

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

(就像 也许吧 但是构造函数顺序颠倒了-- 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 不是“稳定的”)。

您可以将模式匹配分为两部分:

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

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

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 双重递归。每个代码路径最多有一个递归调用。