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

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