为什么这些反向列表功能之一比另一个更快？
在https://wiki.haskell.org/99_questions/Solutions/5 上，有一个反转列表的解决方案：
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
然而，这个定义比 Prelude 中的定义更浪费，因为它在累积结果时反复重新计算。
reverse :: [a] -> [a] reverse list = reverse' list [] where reverse' [] reversed = reversed reverse' (x:xs) reversed = reverse' xs (x:reversed)reverse :: [a] -> [a] reverse list = reverse' list [] where reverse' [] reversed = reversed reverse' (x:xs) reversed = reverse' xs (x:reversed)以下变体避免了这种情况，因此在计算上更接近 Prelude 版本。
我试图了解两者之间的区别。什么reconses意思？
我的想法是reverse xs ++ [x]从第一个元素到最后一个元素，然后添加x，这需要n迭代 ( n= lenght of xs)。在第二个中，它将列表的其余部分附加到x. 但我不知道 Haskell 的内部结构，不知道它与其他示例有何不同。
究竟会发生什么？
回答
列表定义如下（伪代码，因为涉及到一些语法糖）
data [a] = [] | a : [a]
也就是说，列表要么是空的，要么由第一个元素和列表的其余部分组成。
从概念上讲，列表[1, 2, 3]存储在内存中，有点像下面这样。
如果您更熟悉命令式语言，可以将列表视为由指向“第一个”元素的指针和指向列表其余部分的指针组成。如果您以前使用过 Lisp，这应该看起来很熟悉。
现在，让我们看看有什么(++)呢
(++) :: [a] -> [a] -> [a]
(++) [] ys = ys
(++) (x:xs) ys = x : (xs ++ ys)
因为很容易将东西放在列表的开头，(++)取其左侧列表并将每个元素放到右侧列表中。在此期间，右侧列表是单独保留的。也就是说，由于列表的存储方式，[1] ++ [2..10000]速度快，但[1..9999] ++ [10000]速度慢。的时间复杂度（忽略懒惰）(++)仅取决于第一个参数，而不取决于第二个参数。
现在，您的第一个reverse实现是
这会反复将一个长列表（ 的“其余部分” xs）附加到一个短列表 ( [x]) 上。请记住，左边的参数(++)决定了它运行的速度，并且reverse xs通常会很长，所以这需要一段时间。它还会多次不必要地不断重建列表，这表明我们可以做得更好。例如，reverse [1, 2, 3, 4]将执行以下操作
reverse [1, 2, 3, 4]
reverse [2, 3, 4] ++ [1]
... lots of recursive work ...
[4, 3, 2] ++ [1]
... lots more recursive work ...
[4, 3, 2, 1]
虽然第一个递归步骤是必要的（当然，我们必须递归来反转列表），但第二个步骤只是将我们刚刚所做的所有艰苦工作撕开，然后将其重新构建。如果我们能避免这种情况，那就太好了。
进入累积反转功能。在这里，我们使用一个额外的参数以正确的方式“构建”反向列表。与其构建整个反向列表，然后使用(++)在末尾添加一些东西（记住，添加到大列表的末尾是低效的），我们在列表的末尾跟踪我们想要的所有内容，并继续将内容放在最后重复开始（把东西放在链表的开头是非常有效的）。
甚至在一个小列表上比较两个反向函数的评估[1, 2, 3]（同样，我假设我们立即强制此处的值，因此忽略了懒惰）
-- First function
reverse [1, 2, 3]
reverse [2, 3] ++ [1]
(reverse [3] ++ [2]) ++ [1]
((reverse [] ++ [3]) ++ [2]) ++ [1]
(([] ++ [3]) ++ [2]) ++ [1]
([3] ++ [2]) ++ [1]
(3 : ([] ++ [2])) ++ [1]
[3, 2] ++ [1]
3 : ([2] ++ [1])
3 : (2 : ([] ++ [1]))
[3, 2, 1]
-- Second function
reverse [1, 2, 3]
reverse' [1, 2, 3] []
reverse' [2, 3] [1]
reverse' [3] [2, 1]
reverse' [] [3, 2, 1]
[3, 2, 1]
请注意，第二个函数如何更清晰，并且在不必要的数据和重建结构方面进行了更少的改组。