为什么这个尾递归Haskell函数更慢？

Question

我试图实现一个Haskell函数,它将整数A的数组作为输入,并产生另一个数组B = [A [0],A [0] + A [1],A [0] + A [1] + A [2],......].我知道Data.List中的scanl可以用于函数(+).在看到scanl的源代码后,我编写了第二个实现(执行速度更快).我想知道为什么第一个实现比第二个实现慢,尽管是尾递归？

-- This function works slow.
ps s x [] = x
ps s x y  = ps s' x' y'
            where
                s' = s + head y
                x' = x ++ [s']
                y' = tail y

-- This function works fast.
ps' s []   = []
ps' s y    = [s'] ++ (ps' s' y') 
             where 
                s' = s + head y
                y' = tail y

有关上述代码的一些细节:

实施1:应该称为

ps 0 [] a

其中'a'是你的数组.

实施2:应该称为

ps' 0 a

其中'a'是你的数组.

Answer 1

你正在改变++联想的方式.在您的第一个函数中,您正在计算,((([a0] ++ [a1]) ++ [a2]) ++ ...) 而在第二个函数中,您正在计算[a0] ++ ([a1] ++ ([a2] ++ ..)).将一些元素添加到列表的开头是O(1),而在列表的末尾添加一些元素是列表O(n)的长度.这导致整体的线性与二次算法.

您可以通过以相反顺序构建列表,然后在最后再次反转,或使用dlist之类的东西来修复第一个示例.然而,对于大多数目的而言,第二个仍然会更好.虽然尾调用确实存在并且在Haskell中很重要,但如果您熟悉一种严格的函数式语言(如Scheme或ML),那么您对如何以及何时使用它们的直觉是完全错误的.

第二个例子在很大程度上更好,因为它是递增的; 它立即开始返回消费者可能感兴趣的数据.如果你刚刚使用双反向或dlist技巧修复了第一个例子,你的函数将在它返回任何内容之前遍历整个列表.