2016-05-21 11 views
18

In Haskell, questo è un semplice (ingenua) definizione di un punto fissoPerché questa versione di "correzione" è più efficiente in Haskell?

fix :: (a -> a) -> a 
fix f = f (fix f) 

Ma, ecco come Haskell in realtà lo implementa (bassi consumi)

fix f = let x = f x in x 

mia domanda è perché è la la seconda più efficiente della prima?

+3

su quale base si sostiene che uno è più efficiente dell'altro - si può fornire qualche prova – epsilonhalbe

+0

Beh, per uno, sembra correre più veloce. E anche, vedi qui http://h2.jaguarpaw.co.uk/posts/polymorphic-recursion-combinator/ –

risposta

22

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.

+3

Immagino che oggi non sia in grado di analizzare l'inglese ma se si dice "chiama f esattamente una volta" non si sta parlando di valutare "f" per un certo punto, giusto? perché ovviamente dovrai chiamare 'facf' un paio di volte indipendentemente da quale magia sia coinvolta (lo spostamento di' trace' in 'facf' lo mostrerà) – Carsten

+1

' facf' non è ricorsivo, lo chiamiamo una volta, e 'fix'' restituisce un oggetto funzione. Quando chiamiamo * that * function object con un argomento numerico, esso si richiama in modo ricorsivo probabilmente più volte (che può essere nuovamente tracciato come dici tu). –

+0

Grazie per la spiegazione. Ho una domanda più generale. Tutte le funzioni ricorsive possono essere "ottimizzate" usando questo approccio vincolante? In tal caso, perché GHC non utilizza internamente questa tecnica per ottimizzare le ricorsioni? Assumerei che il modo _naive_ di scrivere le funzioni ricorsive sia più facile da leggere e capire. –

5

Credo che questo sia già stato chiesto, ma non ho trovato la risposta. La ragione è che la prima versione

fix f = f (fix f) 

è una funzione ricorsiva, quindi non può essere espansa in linea e quindi ottimizzata. Dalla GHC manual:

Ad esempio, per una funzione di auto-ricorsiva, l'interruttore ciclo può essere solo la funzione stessa, quindi un INLINE pragma viene sempre ignorato.

Ma

fix f = let x = f x in x 

non è ricorsiva, la ricorsione viene spostato nella let vincolante, quindi è possibile inline esso.

Aggiornamento: Ho effettuato alcuni test e mentre la versione precedente non è in linea mentre il secondo lo fa, non sembra essere cruciale per le prestazioni. Quindi le altre spiegazioni (un singolo oggetto su heap e la creazione di una ogni iterazione) sembrano essere più accurate.

+0

Non penso che ci sia qualche inlining coinvolto. –

+0

@ AndrásKovács corretto. Entrambe le varianti di 'fix' vengono compilate in un modo diverso, uno tramite un binding 'let rec', l'altro tramite' rec'. ('-ddump-simpl'). – Zeta

9

Non penso che questo sia sempre (o necessariamente) utile quando si chiama fix con una funzione che richiede due argomenti per produrre una funzione che accetta un argomento. Dovresti eseguire alcuni benchmark per vedere. Ma puoi anche chiamarlo con una funzione che accetta un argomento!

fix (1 :) 

è una circolare lista collegata .Usando la definizione ingenua di fix, sarebbe invece una lista infinita, con nuovi pezzi costruiti pigramente mentre la struttura è forzata.

Problemi correlati