反转列表时出现意外结果

Question

我需要对下面代码的意外结果进行一些解释，这似乎是由某个错误引起的。

reverse' :: [b] -> [b]
reverse' [] = []
reverse' [x] = [x]
reverse'(x:xs) = last (x:xs) : reverse' xs

*Main> reverse' [0,8,2,5,6,1,20,99,91,1]
[1,1,1,1,1,1,1,1,1,1]

这是因为有一些技术问题吗？

- TommyQ

---

问题在于你总是选择相同的最后一个元素作为列表的头。一个快速修复方法是 reverse' xs = last xs : reverse' (init xs)。然而，这个算法很糟糕 :) - is7s

谢谢is7s。我得更仔细地阅读我的代码。 - TommyQ

Answer 1

当您得到一个完全意料之外的结果，特别是像这样相对简单的函数时，手动跟随逻辑可能会有所帮助。因此，让我们手动来看看这里发生了什么:

reverse' (0:[8,2,5,6,1,20,99,91,1]) = 1 : reverse' xs ==>
1 : (reverse' (8:[2,5,6,1,20,99,91,1]) = 1 : reverse' xs ==>
1 : 1 : (reverse' (2:[5,6,1,20,99,91,1]) = 1 : reverse' xs ==>
...

你可以看出问题所在了。问题很简单；你只是在递归步骤中反转了列表的错误部分。现在你反转的是尾部，而你实际上想要反转除了最后一个元素之外的所有元素。因此，你可以将代码修正为以下内容：

reverse' :: [b] -> [b]
reverse' [] = []
reverse' [x] = [x]
reverse' xs = last xs : reverse' (init xs)

该函数返回您所期望的结果：reverse' [1,91,99,20,1,6,5,2,8,0] = [0,8,2,5,6,1,20,99,91,1]

- Jeff Burka

---

哇，非常感谢！这是一个非常愚蠢的“CS101”错误！ - TommyQ

然而，正如is7s所指出的那样，“reverse” xs = last xs : reverse’ (init xs)只是一个快速修复。该算法的时间复杂度为O（n²），对于反转列表来说这是荒谬的。 - leftaroundabout

没错，如果你想知道Prelude版本是如何实现它的，你可以在这里查看：http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/GHC-List.html#reverse。 - Jeff Burka

Answer 2

正如其他人已经指出的错误，让我向你展示一种常常适用并且经常导致高效算法的有用而优雅的技术：使用累加器。

rev xs = rev' xs [] where
  rev' [] acc = acc
  rev' (x:xs) acc = rev' xs (x:acc) 

在这里，您有一个带有额外参数的子函数（“累加器”），它收集您已经拥有的内容。显然，在基本情况下，您需要将此结果返回，因为您已经完成了。递归案例非常简单：就像从顶部一次一个地取出板子并逐个添加到顶部构建新堆栈一样。 此结果堆栈是反转的，就像我们所需的那样。

请注意，对于此技术的其他某些应用程序，您不希望进行反转，可以通过在基本情况下插入reverse来解决这个问题。

- Landei

Answer 3

您原始代码的最小更正可能是：

-- reverse'(x:xs) = last (x:xs) : reverse' xs
reverse' (x:xs) = reverse' xs ++ [x]

例如，您错误地按照错误的顺序组合了列表的子部分。

当然，这仍然是一个二次算法。通过首先观察，您可以得到其迭代版本。

reverse' (a:b:c:d:xs) = (((reverse' xs ++ [d]) ++ [c]) ++ [b]) ++ [a]

正如先前回应中所指出的那样，将产生的中间结果重新分组，并将其保存在一个单独的累加器参数中：

rev (x:xs) acc = rev xs (x:acc)

找到你的工作马，然后使用适当的接口进行设置。

reverse' xs = rev xs []

（加上一些边缘情况）。

- Will Ness

---

稍微解释一下等式推导：reverse' (a:b:c:d:xs) = (((reverse' xs ++ [d]) ++ [c]) ++ [b]) ++ [a] = reverse' xs ++ ([d] ++ ([c] ++ ([b] ++ [a]))) = reverse' xs ++ (d:c:b:a:[]) = reverse' (d:xs) ++ (c:b:a:[])，我们通过将 (++) 操作放在一边来得到累加器。 - Will Ness

Answer 4

在使用 Data.Monoid 时，我发现了以下替代方案，略带 Rube-Goldberg 风格：

import Data.Foldable
import Data.Monoid

reverse = getDual . foldMap (Dual . (:[])) 

- Landei

Answer 5

reverse2 :: [a] -> [a]
reverse2 [] = []
reverse2 [x] = [x]
reverse2 x = (last x) : (reverse2 (init x))

- neoplay

---

你能否提供一些解释？为什么你的答案比已经发布的答案更好？ - Theresa