優化部分計算在Haskell

Question

我很好奇如何優化此代碼：

fun n = (sum l, f $ f0 l, g $ g0 l) 
    where l = map h [1..n] 

假設f，f0，g，g0和h都是昂貴的，但l的創建和存儲是非常昂貴。

正如所寫，l被存儲，直到返回的元組被完全評估或垃圾收集。相反，length l,f0 l和g0 l都應該在它們中的任何一個都被執行時執行，但f和g應該被延遲。

看來這種行爲可能是固定的寫作：

fun n = a `seq` b `seq` c `seq` (a, f b, g c) 
    where 
    l = map h [1..n] 
    a = sum l 
    b = inline f0 $ l 
    c = inline g0 $ l 

還是很相似：

fun n = (a,b,c) `deepSeq` (a, f b, g c) 
    where ... 

我們或許可以指定一幫內部類型來達到相同的效果好，看起來很痛苦。還有其他選擇嗎？

另外，我明明跟我inline s表示編譯器融合sum，f0和g0成一個單一循環，構建和消耗l逐項希望。我可以通過手動內聯來明確這一點，但這很吸引人。有沒有辦法明確阻止創建和/或強制內聯列表l？可能在編譯期間內聯或融合失敗時會產生警告或錯誤的編譯指示？

順便說一句，我很好奇，爲什麼seq，inline，lazy，等等，都由let x = x in x的序幕定義。這僅僅是爲了給他們一個編譯器的重寫定義嗎？

Answer 1

如果您想確定，唯一的辦法就是自己動手。對於任何給定的編譯器版本，您可以嘗試幾個源代碼公式，並檢查生成的核心/程序集/ llvm字節代碼/無論它是否按照您的要求進行。但是這可能會破壞每個新的編譯器版本。

如果你寫

fun n = a `seq` b `seq` c `seq` (a, f b, g c) 
    where 
    l = map h [1..n] 
    a = sum l 
    b = inline f0 $ l 
    c = inline g0 $ l 

或deepseq其版本，編譯器也許能合併的a，b和c的計算並行（而不是在併發意義上）在單個進行遍歷l，但暫時，我相信GHC不會，如果JHC或UHC做到了，我會感到驚訝。爲此，計算結構b和c需要足夠簡單。

在編譯器和編譯器版本中獲得所需結果的唯一方法是自己做。在接下來的幾年裏，至少。

根據f0和g0，這可能是因爲這樣做適當的蓄壓式嚴格的左摺疊和組合功能，如著名的平均

data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !Double 

average :: [Double] -> Double 
average = ratio . foldl' count (P 0 0) 
    where 
    ratio (P n s) = s/fromIntegral n 
    count (P n s) x = P (n+1) (s+x) 

但如果f0和/或g0結構簡單不適合，說一個左邊的摺疊，另一個是正確的摺疊，可能不可能在一次遍歷中進行計算。在這種情況下，選擇是在重新創建l和存儲l之間。存儲l很容易通過顯式共享來實現（where l = map h [1..n]），但如果編譯器執行一些常見的子表達式消除操作（例如GHC確實傾向於共享該表單的列表，即使它沒有CSE ）。對於GHC，標記fno-cse和-fno-full-laziness可以幫助避免不必要的共享。