爲什麼foldl有時比foldr慢？ 我有一個列表的列表「一」像foldl with（++）比foldr慢很多
a = [[1],[2],[3]]
，並希望通過摺疊
foldr (++) [] a
將其更改爲一個列表，它工作正常（時間複雜度爲O（n））。但是如果我使用foldl，它會很慢（時間複雜度是O（n^2））。
foldl (++) [] a
如果與foldl只是摺疊從左側的輸入列表中，
(([] ++ [1]) ++ [2]) ++ [3]
和foldr相似是從右側，
[1] ++ ([2] ++ ([3] ++ []))
計算的次數（++）在兩種情況下應該是相同的。爲什麼foldr這麼慢？根據時間複雜度，foldl看起來好像將輸入列表掃描多倍於foldr一樣。我用下面的計算機時間
length $ fold (++) [] $ map (:[]) [1..N] (fold is either foldl or foldr)
這是因爲如何++作品。請注意，它的第一個參數是由歸納定義的。
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
遞歸調用的數量僅取決於length xs。
正因爲如此，在xs ++ ys比其他方式有一個小的xs和一個大的ys更方便。
注意，摺疊右側達到這樣的：
[1] ++ ([2] ++ ([3] ++ ...
我們只有很短（O（1） - 長度）上的++左側，使得折成本爲O（n）名單。
不是摺疊左邊是壞：
((([] ++ [1]) ++ [2]) ++ [3]) ++ ...
左側的參數變得越來越大。因此，我們在這裏得到O（n^2）的複雜性。
考慮輸出列表是如何被要求的，這個參數可以做得更精確。可以觀察到foldr以「流式」方式產生其結果，其中要求例如第一個輸出列表單元格只強制輸入的一小部分 - 只需要執行第一個輸入列表++，實際上只需要執行其第一個遞歸步驟！即使只有foldl結果中的第一項會強制要求所有調用++，這使得它非常昂貴（即使每個調用只需要一個遞歸步驟，都有O（n）調用）。
'（++）'的*結果*在兩種情況下應該是相同的。這並不意味着計算的數量是相同的。 –
（大列表）++（小列表）慢於（小列表）++（大列表） – immibis
我看到你在這裏待了很長時間，並且在不接受問題的情況下問了很多問題。如果答案對您有幫助，請考慮[接受]（https：// stackoverflow。com/help/accepted-answer）它。請花2分鐘做一個[旅遊]（https://stackoverflow.com/tour）瞭解這個網站的工作原理 –