性能增益實現concatMap與foldl'爲有限列表？

Question

我從Foldr Foldl Foldl'讀取，foldl'由於嚴格性屬性對長有限列表更有效。我知道它不適合無限列表。

因此，我限制只有長有限列表的比較。

---

concatMap

concatMap使用foldr，這使得它的懶惰實現。然而，根據這篇文章，使用它與長期有限的名單將建立一個長期未減少的鏈。

concatMap :: Foldable t => (a -> [b]) -> t a -> [b] 
concatMap f xs = build (\c n -> foldr (\x b -> foldr c b (f x)) n xs) 

因此我拿出來與使用foldl'以下實現。

concatMap' :: Foldable t => (a -> [b]) -> t a -> [b] 
concatMap' f = reverse . foldl' (\acc x -> f x ++ acc) [] 

---

測試出來

我有構建以下兩個功能來測試性能。

lastA = last . concatMap (: []) $ [1..10000] 
lastB = last . concatMap' (: []) $ [1..10000] 

但是，我對結果感到震驚。

lastA: 
(0.23 secs, 184,071,944 bytes) 
(0.24 secs, 184,074,376 bytes) 
(0.24 secs, 184,071,048 bytes) 
(0.24 secs, 184,074,376 bytes) 
(0.25 secs, 184,075,216 bytes) 

lastB: 
(0.81 secs, 224,075,080 bytes) 
(0.76 secs, 224,074,504 bytes) 
(0.78 secs, 224,072,888 bytes) 
(0.84 secs, 224,073,736 bytes) 
(0.79 secs, 224,074,064 bytes) 

---

後續問題

concatMap outcompetes我在這兩個時間和內存concatMap'。我不知道我在我的concatMap'實施中犯了什麼錯誤。

因此，我懷疑陳述foldl'的好處的文章。

1. 是否有任何concatMap黑魔法使它如此高效？

2. 確實foldl'對於長有限表更有效嗎？

3. 使用帶有長有限列表的foldr是否真的會建立一個長未減少的鏈並影響性能？

Answer 1

concatMap中是否有任何黑魔法使它如此高效？

不，不是真的。

確實foldl'對長有限表更有效嗎？

並不總是如此。這取決於摺疊功能。

問題是，foldl和foldl'總是必須在產生輸出之前掃描整個輸入列表。相反，foldr並不總是必須的。

作爲一個極端的情況下，考慮

foldr (\x xs -> x) 0 [10..10000000] 

計算結果爲10即刻 - 僅在列表的第一個元素進行評價。這種減少有點像

foldr (\x xs -> x) 0 [10..10000000] 
= foldr (\x xs -> x) 0 (10 : [11..10000000]) 
= (\x xs -> x) 10 (foldr (\x xs -> x) 0 [11..10000000]) 
= (\xs -> 10) (foldr (\x xs -> x) 0 [11..10000000]) 
= 10 

並且由於懶惰而不評估遞歸調用。

一般而言，計算foldr f a xs時，它要檢查f y ys是否能夠評估ys之前以構建輸出的一部分是非常重要的。例如

foldr f [] xs 
where f y ys = (2*y) : ys 

評估2*y和ys之前產生列表細胞_ : _。這使得它成爲foldr的絕佳選擇。

同樣，我們可以定義

map f xs = foldr (\y ys -> f y : ys) [] xs 

它運行得很好。它消耗xs中的一個元素並輸出第一個輸出單元。然後它消耗下一個元素，輸出下一個元素，依此類推。使用foldl'不會輸出任何東西，直到整個列表被處理，使代碼效率非常低。

相反，如果我們寫

sum xs = foldr (\y ys -> y+ys) 0 xs 

然後我們做的xs第一個元素被消耗後不輸出任何東西。 我們構建了一個長長的連環，浪費了大量的內存。 在這裏，foldl'將改爲在恆定空間中工作。

這是真的，使用foldr長有限名單將建立一個長期未還原鏈和抗衝擊性能？

並不總是如此。它強烈依賴於輸出如何被調用者使用。

作爲一個拇指規則，如果輸出是「原子」，即輸出使用者不能僅觀察其中的一部分（例如Bool, Int, ...），則最好使用foldl'。如果輸出是由許多獨立值（列表，樹，...）組成的「列」，可能foldr是更好的選擇，如果f可以「流」方式逐步產生其輸出。