Is it possible to improve the asymptotic behavior of functional containers?

Question

Pay attention to 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 recursive from 0 to n , and stepper is a constant function of time. You can make sure that by changing the constant, the runtime changes linearly proportionally. Now remember 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 same algorithm as the program above, the only thing that has changed is that the function is used as a container, not a data type. However, it is quadratic: the stepper' state never executed, creating a larger and larger tone, which is reviewed at every step. Both programs take the same amount of time to run, regardless of very different constants. I believe that the second program can be fixed with an average value for expressing the term in normal form, but the GHC does not provide for this, so can the second program be fixed so that it is no longer quadratic?

Answer 1

On my machine, the following only runs 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 reflected the definition of stepper (Box x) = Box (x+1) , which could also be written as stepper box = Box (getter box + 1) . To reflect this, I defined a mkBox that reflects Box . The second key difference is that I explicitly made the mkBox strict argument; I believe in your quick version of the GHC rigor test doing this backstage.