我一直想知道这个问题,但没有找到满意的答案。
为什么(++)
“贵”?在惰性评估下,我们不会评估像
xs ++ ys
在必要之前,甚至到那时,我们只会在需要时评估我们需要的部分。
有人可以解释一下我缺少什么吗?
最佳答案
如果您访问整个结果列表,延迟计算将不会节省任何计算。它只会延迟它,直到您需要每个特定元素,但最后,您必须计算相同的东西。
如果遍历串联列表xs ++ ys
,访问第一部分 ( xs
) 的每个元素会增加一点常量开销,检查是否 xs
是否已被花费。
所以,如果你关联++
,就会产生很大的不同。向左或向右。
如果您关联
n
长度列表k
向左侧,例如(..(xs1 ++ xs2) ... ) ++ xsn
然后访问第一个k
中的每一个元素将采用O(n)
时间,访问每个下一个k
需要O(n-1)
等等。所以遍历整个列表将需要O(k n^2)
。你可以检查一下sum $ foldl (++) [] (replicate 100000 [1])
需要真的很长的时间。
如果您关联
n
长度列表k
到右侧,例如xs1 ++ ( ..(xsn_1 ++ xsn) .. )
那么你只会得到每个元素的恒定开销,因此遍历整个列表将只是O(k n)
。你可以检查一下sum $ foldr (++) [] (replicate 100000 [1])
很有道理。
编辑:这就是ShowS
背后隐藏的魔力。 。如果将每个字符串 xs
转换至showString xs :: String -> String
( showString
只是 (++)
的别名)并组合这些函数,然后无论您如何关联它们的组合,最终它们都会从右到左应用 - 这正是我们获得线性时间复杂度所需的。 (这只是因为 (f . g) x
是 f (g x)
。)
您可以检查两者
length $ (foldl (.) id (replicate 1000000 (showString "x"))) ""
和
length $ (foldr (.) id (replicate 1000000 (showString "x"))) ""
在合理的时间内运行( foldr
更快一些,因为从右侧编写函数时开销较小,但两者在元素数量上都是线性的)。
关于haskell - (++) 惰性求值的性能,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12296694/