list - 反转列表时出现意外结果

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]