爲什麼在Haskell中總和比foldl'慢？

ghc中的默認sum如何比其foldl'（foldl的stricter equivalent）等效地慢10倍？如果是這樣的話，爲什麼它不使用foldl'？爲什麼在Haskell中總和比foldl'慢？

import Data.List 
> foldl' (+) 0 [1..10^7] 
50000005000000 
(0.39 secs, 963,528,816 bytes) 

> sum [1..10^7] 
50000005000000 
(4.13 secs, 1,695,569,176 bytes)

爲了完整這裏也是foldl和foldr的統計信息。

> foldl (+) 0 [1..10^7] 
50000005000000 
(4.02 secs, 1,695,828,752 bytes) 

> foldr (+) 0 [1..10^7] 
50000005000000 
(3.78 secs, 1,698,386,648 bytes)

貌似sum使用foldl，因爲它們的運行時類似於實施。測試ghc 7.10.2。

來源

2016-04-28 dimid

如果使用-O2進行編譯，它們是相同的。 –

@JoachimBreitner對不起 – Carsten

另請參閱：https://www.reddit.com/r/haskell/comments/2agxcb/why_is_sum_lazy/ – ZhekaKozlov

的sum功能在GHC使用foldl實施：

-- | The 'sum' function computes the sum of a finite list of numbers. 
sum      :: (Num a) => [a] -> a 
{-# INLINE sum #-} 
sum      = foldl (+) 0

可以看出in the source。

它必須這樣，因爲它是規格in the Haskell report。

理由很可能是，對於列表中的某些懶惰元素類型，foldl是正確的。（我個人認爲foldl幾乎總是錯的，只能使用foldl'）。

經過充分的優化，GHC將內聯該定義，將其專用於手頭的元素類型，注意循環是嚴格的，並強制在每次迭代中評估累加器;正如@AndrásKovács所觀察到的那樣，將其有效地轉化爲foldl'。

由於GHC-7.10,sum itself是Foldable類型的方法，默認定義將通過foldMap進行。然而，instance Foldable []以上述的sum的定義覆蓋了這一點。

來源

2016-04-28 11:35:41

爲了補充@Joachim Breitner的回答，我發現了這個blog post，這是一個非常有趣的閱讀（來自reddit的討論，感謝@ZhekaKozlov的鏈接）。

當Haskell 1.0在24年前的這一天發佈時，根本沒有seq功能，所以沒有選擇，只能以「經典」方式定義foldl。最後，經過六年多的討論，我們在Haskell 1.3中獲得了seq函數。雖然實際上在Haskell 1.3 seq是Eval類的一部分，所以你不能在任何地方使用它，比如在foldl中。在Haskell 1.3，你將不得不與該類型定義與foldl」：

foldl' :: Eval b => (b -> a -> b) -> b -> [a] -> b

哈斯克爾1.4和Haskell 98擺脫了評估和演示類約束的序列中，但與foldl沒有改變。擁抱和GHC和其他實現添加了非標準foldl'。

我懷疑人們認爲它是兼容性和慣性問題。添加一個非標準的foldl很容易，但是你不能輕易改變標準。

我懷疑，如果我們從一開始就有seq，那麼我們就會使用它定義foldl。

作爲Haskell的前身語言之一的Miranda在Haskell 1.0之前已經有了5年的seq。

順便說一句，我已經成功地刮鬍子20毫秒以上使用

foldl1' (+) [1..10^7]

所以，我想foldl1'應該是sum和product默認值（以空列表進行特殊處理）。

來源

2016-05-01 20:36:52 dimid

爲什麼在Haskell中總和比foldl'慢？

回答

相關問題