È possibile migliorare la asintotica dei contenitori funzionali?

Question

mente il seguente programma:

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 

Qui, run è ovviamente lineare, dal momento che è un recurses da 0 a n e stepper è una funzione costante di tempo. È possibile verificare che modificando la costante - il runtime cambia linearmente proporzionale. Ora, la mente di questo codice:

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' 

Questo è lo stesso algoritmo come il programma di cui sopra, l'unica cosa cambiata è che una funzione viene utilizzata come contenitore, invece di un tipo di dati. Tuttavia, è quadratico: stepper' state non viene mai eseguito, creando un thunk più grande e più grande che viene rivalutato in ogni passaggio. Entrambi i programmi richiedono la stessa quantità di tempo per l'esecuzione, indipendentemente dalle costanti estremamente diverse. Credo che il secondo programma potrebbe essere risolto con una media di valutazione di un termine in forma normale, ma GHC non prevede che, quindi, è possibile correggere il secondo programma in modo che non sia più quadratico?

Answer 1

Sulla mia macchina, le seguenti corse solo tre volte più lento di quanto il tuo codice veloce:

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' 

Ci sono due differenze fondamentali: in primo luogo, ho rispecchiato la definizione stepper (Box x) = Box (x+1), che potrebbe anche essere scritto come stepper box = Box (getter box + 1). Per rispecchiarlo, ho definito uno mkBox che specchi Box. La seconda differenza fondamentale è che ho esplicitamente reso l'argomento mkBox strict; Credo nella tua versione veloce L'analisi di rigore di GHC fa questo dietro le quinte.