Is it possible to improve the asymptotics of functional containers?

Question

Mind the following program:

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

Here, run is obviously linear, since it is a recurses from 0 to n and stepper is a constant time function. You can verify that by changing the constant - the runtime changes linearly proportional. Now, mind this code:

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'

This is the very same algorithm as the program above, the only thing changed is that a function is used as the container, instead of a datatype. Yet, it is quadratic: stepper' state is never executed, creating a bigger and bigger thunk that is re-evaluated at each step. Both programs take the same amount of time to run, regardless of hugely different constants. I believe the second program could be fixed with a mean of evaluating a term to normal form, but GHC doesn't provide that, so, is it possible to fix the second program so it is not quadratic anymore?

Answer 1

On my machine, the following runs only three times slower than your fast code:

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'

There are two key differences: first, I mirrored the definition stepper (Box x) = Box (x+1), which could also be written as stepper box = Box (getter box + 1). To mirror it, I defined a mkBox which mirrors Box. The second key difference is that I explicitly made the argument to mkBox strict; I believe in your fast version GHC's strictness analysis does this behind the scenes.