我一直在想这个很多，我还没有找到令人满意的答案。
为什么(++)“贵”？在惰性求值下，我们不会求值这样的表达式
xs ++ ys
在必要之前，即使那样，我们也只会在需要时评估我们需要的部分。
有人可以解释我错过了什么吗？
问问题
981 次
3 回答
15
如果您访问整个结果列表，惰性求值将不会保存任何计算。它只会延迟它，直到您需要每个特定元素，但最后，您必须计算相同的东西。
如果您遍历连接列表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) xis f (g x)。）
您可以检查两者
length $ (foldl (.) id (replicate 1000000 (showString "x"))) ""
和
length $ (foldr (.) id (replicate 1000000 (showString "x"))) ""
在合理的时间内运行（foldr更快一点，因为从右侧组合函数时开销较小，但两者在元素数量上都是线性的）。
于 2012-09-06T09:40:48.600 回答
5
它本身并不太贵，当你开始从左到右++组合很多时就会出现问题：这样的链被评估为
( ([1,2] ++ [3,4]) ++ [5,6] ) ++ [7,8]
≡ let a = ([1,2] ++ [3,4]) ++ [5,6]
≡ let b = [1,2] ++ [3,4]
≡ let c = [1,2]
in head c : tail c ++ [3,4]
≡ 1 : [2] ++ [3,4]
≡ 1 : 2 : [] ++ [3,4]
≡ 1 : 2 : [3,4]
≡ [1,2,3,4]
in head b : tail b ++ [5,6]
≡ 1 : [2,3,4] ++ [5,6]
≡ 1:2 : [3,4] ++ [5,6]
≡ 1:2:3 : [4] ++ [5,6]
≡ 1:2:3:4 : [] ++ [5,6]
≡ 1:2:3:4:[5,6]
≡ [1,2,3,4,5,6]
in head a : tail a ++ [7,8]
≡ 1 : [2,3,4,5,6] ++ [7,8]
≡ 1:2 : [3,4,5,6] ++ [7,8]
≡ 1:2:3 : [4,5,6] ++ [7,8]
≡ 1:2:3:4 : [5,6] ++ [7,8]
≡ 1:2:3:4:5 : [6] ++ [7,8]
≡ 1:2:3:4:5:6 : [] ++ [7,8]
≡ 1:2:3:4:5:6 : [7,8]
≡ [1,2,3,4,5,6,7,8]
您可以清楚地看到二次复杂度。即使您只想评估第n个元素，您仍然必须挖掘所有这些lets。这就是为什么++is infixr, for[1,2] ++ ( [3,4] ++ ([5,6] ++ [7,8]) )实际上效率更高。但是如果你在设计一个简单的序列化器时不小心，你可能很容易得到一个像上面这样的链。这是初学者被警告的主要原因++。
除此之外，Prelude.++与例如操作相比它很慢，Bytestring原因很简单，它通过遍历链表来工作，链表总是有次优的缓存使用等，但这不是问题；这会阻止您获得类似 C 的性能，但仅使用普通列表++就可以正确编写程序，并且仍然可以轻松地与用 Python 编写的类似程序相媲美。
于 2012-09-06T09:49:08.900 回答