Il lento fix
chiama f
in ogni fase della ricorsione, mentre quello veloce chiama f
esattamente una volta. Può essere visualizzato con tracciamento:
import Debug.Trace
fix f = f (fix f)
fix' f = let x = f x in x
facf :: (Int -> Int) -> Int -> Int
facf f 0 = 1
facf f n = n * f (n - 1)
tracedFacf x = trace "called" facf x
fac = fix tracedFacf
fac' = fix' tracedFacf
Ora provare qualche corsa:
> fac 3
called
called
called
called
6
> fac' 3
called
6
Più in dettaglio, let x = f x in x
risultati in un thunk artificiale ripartendo per x
, e un puntatore a questo thunk viene passato f
. Alla prima valutazione di fix' f
, il thunk viene valutato e tutti i riferimenti ad esso (qui in particolare: quello che passiamo a f
) vengono reindirizzati al valore risultante. Accade semplicemente che a x
venga assegnato un valore che contiene anche un riferimento a x
.
Ammetto che questo può essere piuttosto sconvolgente. È qualcosa a cui ci si deve abituare quando si lavora con la pigrizia.
fonte
2016-05-21 18:01:47
su quale base si sostiene che uno è più efficiente dell'altro - si può fornire qualche prova – epsilonhalbe
Beh, per uno, sembra correre più veloce. E anche, vedi qui http://h2.jaguarpaw.co.uk/posts/polymorphic-recursion-combinator/ –