尾递归方式排序和合并两个列表

Question

我正在尝试编写一种尾递归方式将两个已排序的列表合并为一个已排序的列表。

这是我的尝试。首先，我有非尾递归的方法。

merge2 :: Ord a => [a] -> [a] -> [a]
merge2 l1 [] = l1
merge2 [] l2 = l2
merge2 (x:xs) (y:ys) | x > y = y : merge2 (x:xs) ys
                     | x < y = x : merge2 xs (y:ys)
                     | otherwise = x : merge2 (x:xs) ys

mergeTail :: Ord a => [a] -> [a] -> [a]
mergeTail accum [] = accum
mergeTail accum (x:xs) = mergeTail (x:accum) xs

当我输入像 merge2Tail [1,2] [2,3,4] 这样的内容时，我期望得到 [1,2,2,3,4] 作为输出结果，但实际上我得到了一些随机的顺序。我不确定在保持尾递归的情况下如何实现检查顺序的情况。

- Larry.Fish

---

那听起来相当低效。你为什么要让它成为尾递归？ - melpomene

@Larry.Fish：是的，你应该。 :) - Ry-

@Larry.Fish，您需要三个参数，即l1、l2和累加器。 - melpomene

我调用它的时候，不是需要传入3个参数吗？那第三个参数该传什么呢？ - Larry.Fish

是的，基于累加器的解决方案使用带有附加参数的辅助函数。最初，它可以是一个空列表。在递归时，将要“输出”的元素前置到累加器中。最后，累加器将包含所需的列表，但是顺序是反向的。 - chi

Answer 1

正如其他人所指出的，这是一个高度人为的练习：用Haskell合并两个已排序列表以形成一个已排序列表不应该使用尾递归方式完成。但如果您正在使用具有非常有限调用栈大小且没有支持cons模式的尾递归的语言环境来构建一个严格脊柱列表，那么这可能是一个合理的选择。在这种环境下，通常最好将这类问题分为两个部分：

1. 遍历列表（S），在累加器中反向构建列表。

2. 使用累加器构建最终结果。

让我们从这里开始。

merge :: Ord a => [a] -> [a] -> [a]
merge = \xs ys -> go [] xs ys
  where
    go acc [] ys = reverse acc ++ ys
    go acc xs [] = reverse acc ++ xs
    go acc xss@(x : xs) yss@(y : ys)
      | x <= y = go (x : acc) xs yss
      | otherwise = go (y : acc) xss ys

即使满足上述条件，还存在一个效率问题：reverse会完全重构其参数，而++则会完全重构其第一个参数。因此，reverse acc ++ ys会两次重构acc（如果++也是尾递归写法，则会重构三次）。让我们修复这个问题。

-- reverseOnto xs ys = reverse xs ++ ys
reverseOnto :: [a] -> [a] -> [a]
reverseOnto [] ys = ys
reverseOnto (x : xs) ys = reverseOnto xs (x : ys)

最后，

merge :: Ord a => [a] -> [a] -> [a]
merge = \xs ys -> go [] xs ys
  where
    go acc [] ys = acc `reverseOnto` ys
    go acc xs [] = acc `reverseOnto` xs
    go acc xss@(x : xs) yss@(y : ys)
      | x <= y = go (x : acc) xs yss
      | otherwise = go (y : acc) xss ys

我相信，在你的限制条件下，那大概是你所能做到的最好的。

- dfeuer

---

顺便提一句，“reverseOnto” 在 Lisp 中是非常常见的范例，我总以为甚至内置了相应的函数 “revappend” 或类似的东西；如果没有的话，应该加上。（当然在 Haskell 中我们可以使用“flip $ foldl' (flip (:))”来实现。） :) - Will Ness

Answer 2

首先，让我们看一下非尾递归的样子：

merge :: Ord a => [a] -> [a] -> [a]
merge xs []                                 = xs
merge [] ys                                 = ys
merge fullXs@(x:xs) fullYs@(y:ys)  | x <= y = x : merge xs fullYs
                                   | x > y  = y : merge fullXs ys

为了使其成为尾递归，您必须在某处拥有一个“accum”，并调用子函数助手。 由于它是尾递归的，您必须在末尾添加元素以保持顺序：

查看使用“foldl”时会发生什么：

foldl (flip (:)) [] [1,2,3,4,5]
=> [5,4,3,2,1]

因此，这个函数将会是：

mergeTail :: Ord a => [a] -> [a] -> [a]
mergeTail xs [] = xs
mergeTail [] ys = ys
mergeTail xs ys = mergeAccum [] xs ys


mergeAccum :: Ord a => [a] -> [a] -> [a] -> [a]
mergeAccum acc [] []                       = acc
mergeAccum acc [] (y:ys)                   = mergeAccum (acc ++ [y]) [] ys
mergeAccum acc (x:xs) []                   = mergeAccum (acc ++ [x]) xs []
mergeAccum acc (x:xs) (y:ys)  | x <= y     = mergeAccum (acc ++ [x]) xs (y:ys)
                              | x > y      = mergeAccum (acc ++ [y]) (x:xs) ys

ejemplo:

$> mergeTail [1,2,6] [1,2,3,5]
=> [1,1,2,2,3,5,6]

注意：

在这种情况下，该函数效率低下，因为每次递归调用都必须到达 accum 列表的末尾。

- developer_hatch

---

标准解决方案是使用高效的(:)将累加器逆向构建，在基本情况下反转累积的结果后再返回。 - Will Ness

@WillNess 我不太理解你的概念，它应该是什么样子的？我不知道它。 - developer_hatch

你需要将递归子句中的 mergeAccum (acc ++ [y]) ... 改为 mergeAccum (y : acc) ...，并将基本情况子句 ... = acc 改为 ... = reverse acc。 :) - Will Ness