反转列表时出现意外结果

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]

这是因为一些错误吗？

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]

Answer 2

正如其他人已经指出了这个错误,让我向您展示一种有用而优雅的技术,这种技术通常可以应用于这种情况,并且通常会导致高效的算法:使用累加器.

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

所以你有一个带有附加参数的子函数("累加器"),它收集你已经拥有的东西.显然,在基本情况下,你需要回复这个结果,因为你已经完成了.递归的情况在这里非常简单:它就像有一叠板,你从顶部逐个采取,并通过在顶部逐个添加来构建一个新的堆栈.这个结果堆栈是相反的,就像我们需要它一样.

请注意,对于此技术的某些其他应用程序,您不希望进行返回,可以通过reverse在基本情况中插入来修复.

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 []

(加上少数边缘情况).