haskell - 为什么这些反向列表功能之一比另一个更快？

Question

关于 https://wiki.haskell.org/99_questions/Solutions/5有这个解决方案来反转列表:

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

However this definition is more wasteful than the one in Prelude as itrepeatedly reconses the result as it is accumulated. The followingvariation avoids that, and thus computationally closer to the Preludeversion.

reverse :: [a] -> [a]
reverse list = reverse' list []
  where
    reverse' [] reversed     = reversed
    reverse' (x:xs) reversed = reverse' xs (x:reversed)

我想了解两者之间的区别。 reconses 是什么意思？

我的想法是 reverse xs++ [x] 从第一个元素到最后一个元素，然后添加 x，这需要 n 迭代(n= xs 的长度)。在第二个中，它将列表的其余部分附加到 x。但我不知道 Haskell 的内部结构，不知道它与其他示例有何不同。

到底发生了什么？

Answer 1

列表定义如下(伪代码，因为涉及一些语法糖)

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 :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

这会将一个长列表(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]

虽然第一个递归步骤是必要的(当然，我们必须递归以反转列表)，但第二个递归步骤只是将我们刚刚完成的所有艰苦工作拆散并重新构建它。如果我们能避免这种情况，那就太好了。

reverse :: [a] -> [a]
reverse list = reverse' list []
  where
    reverse' [] reversed     = reversed
    reverse' (x:xs) reversed = reverse' xs (x:reversed)

进入累计反转功能。在这里，我们使用一个额外的参数以正确的方式“构建”反向列表。我们不是构建整个反向列表，然后使用 (++) 向末尾添加内容(记住，向大列表的末尾添加是低效的)，而是跟踪我们想要的所有内容列表的末尾并不断将内容放在开头(将内容放在链表的开头非常有效)。

甚至在一个小列表 [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]

请注意第二个函数如何更简洁，并且减少了很多不必要的数据改组和重建结构。