list - haskell 函数的时间复杂度

Question

有没有简单的方法来控制haskell中函数的时间复杂度？

我已经构建了一个反转任何类型列表的函数，目标是让它具有线性时间复杂度，我试图这样解决:

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

我的意图是让它成为线性的，O(n)，但我不确定它是否真的是这样，因此我想使用某种类型的工具来分析代码/函数以表明它实际上是线性的。

我想知道:

这个函数是线性的吗？我可以用任何分析工具来展示它吗？

Answer 1

(…) have it linear, O(n), but i am unsure if it actually is and would therefore like use some type of tool that might analyze the code/function to show that it is infact linear.

函数不是线性的。追加函数(++) :: [a] -> [a] -> [a]是线性的。由于我们对列表中的每个元素都执行此操作，因此我们最终会得到 O(n²) 时间复杂度。

我们可以做的就是使用一个累加器来使它成为一个线性函数:一个额外的参数，我们每次使用它都会以更新形式传递:

myrev :: [a] -> [a]
myrev = (`go` <b>[]</b>)
  where go (x:xs) <b>ys</b> = go xs (x:<b>ys</b>)
        go [] <b>ys</b> = <b>ys</b>

因此，我们以空列表启动累加器。对于原始列表 x 中的每个元素，我们将其从第一个列表中弹出，并将其推送到第二个列表。当第一个列表用完时，ys 包含反向列表。