是否有可能改善功能容器的漸近性？

Question

心下面的程序：

data Box = Box Int 
initial   = Box 1 
stepper (Box x) = Box (x+1) 
getter (Box x) = x 
run 0 state  = [] 
run n state  = getter state : run (n-1) (stepper state) 
main   = print $ sum $ run 50000000 initial 

這裏，run顯然是線性的，因爲它是一個遞歸從0到n和stepper是恆定的時間函數。您可以通過更改常數來驗證 - 運行時間線性比例變化。現在，考慮到這一點代碼：

initial' box  = box 1 
stepper' box box_ = box (\ x -> (box_ (x+1))) 
getter' box  = box (\ x -> x) 
run' 0 state  = [] 
run' n state  = getter' state : run' (n-1) (stepper' state) 
main    = print $ sum $ run' 8000 initial' 

這是非常相同的算法上面的程序，唯一改變的事情是，一個功能是用作容器，而不是數據類型。然而，它是二次的：stepper' state永遠不會執行，創建一個越來越大的thunk，並在每個步驟重新評估。無論常量大小不同，兩個程序都需要相同的時間運行。我相信第二個程序可以固定的意思是評估一個術語到正常形式，但是GHC沒有提供，所以，是否有可能修復第二個程序，因此它不是二次的？

Answer 1

在我的機器，下面的運行比你快的代碼慢了三次：

mkBox n box = box n 
getter' box = box (\ x -> x) 
initial'  = mkBox 1 
stepper' box = mkBox $! getter' box+1 
run' 0 state = [] 
run' n state = getter' state : run' (n-1) (stepper' state) 
main   = print $ sum $ run' 50000000 initial' 

有兩個關鍵的區別：第一，我反映的定義stepper (Box x) = Box (x+1)，這也可以寫成stepper box = Box (getter box + 1)。爲了反映它，我定義了一個mkBox，它反映了Box。第二個關鍵區別在於我明確提出了嚴格的mkBox參數;我相信GHC的嚴格分析能夠在幕後做到這一點。