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

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的严格分析能够在幕后做到这一点。