Come faccio a utilizzare correzione, e come funziona?

Question

ero un po 'confuso dalla documentazione per fix (anche se credo di aver capito quello che si suppone di fare ora), così ho guardato il codice sorgente. Che mi ha lasciato più confuso:

fix :: (a -> a) -> a
fix f = let x = f x in x

Come funziona esattamente questo ritorno un punto fisso?

ho deciso di provarlo nella riga di comando:

Prelude Data.Function> fix id
...

E si blocca lì. Ora, per essere onesti, questo è il mio vecchio macbook, che è un po 'lento. Tuttavia, questa funzione non può essere anche computazionalmente costoso in quanto qualsiasi cosa passata per id dà la stessa cosa di nuovo (per non parlare che si sta mangiando fino nessun tempo di CPU). Che cosa sto facendo di sbagliato?

Answer 1

Si sta facendo niente di male. fix id è un ciclo infinito.

Quando si dice che fix restituisce il punto di minimo fisso di una funzione, che significa che nel dominio teoria senso. Così fix (\x -> 2*x-1) è non di andare a tornare 1, perché anche se 1 è un punto fisso di tale funzione, non è il almeno una nell'ordinamento dominio.

Non posso descrivere l'ordinamento di dominio in un mero paragrafo o due, così vi rimando al link teoria dei domini sopra. Si tratta di un ottimo tutorial, facile da leggere, e molto illuminante. Lo consiglio vivamente.

Per la vista da 10.000 piedi, fix è una funzione di ordine superiore che codifica l'idea di ricorsione . Se avete l'espressione:

let x = 1:x in x

Quali risultati nella lista [1,1..] infinita, si potrebbe dire la stessa cosa usando fix:

fix (\x -> 1:x)

(O semplicemente fix (1:)), che dice a trovare un punto fisso della funzione (1:), IOW un x valore tale che x = 1:x ... proprio come sopra definito. Come si può vedere dalla definizione, fix non è altro che questa idea -. Ricorsione incapsulato in una funzione

Si tratta di un concetto veramente generale della ricorsione, come pure - si può scrivere qualsiasi funzione ricorsiva in questo modo, comprese le funzioni che utilizzano polimorfico ricorsione . Così, per esempio la tipica funzione di Fibonacci:

fib n = if n < 2 then n else fib (n-1) + fib (n-2)

Può essere scritto utilizzando fix in questo modo:

fib = fix (\f -> \n -> if n < 2 then n else f (n-1) + f (n-2))

Esercizio:. Espandere la definizione di fix per dimostrare che queste due definizioni di fib sono equivalenti

Ma per una piena comprensione, leggere sulla teoria del dominio. E 'davvero cool stuff.

Answer 2

Non pretendo di capire questo a tutti, ma se questo aiuta nessuno ... quindi Yippee.

Si consideri la definizione di fix. fix f = let x = f x in x. La parte da capogiro è che x è definito come f x. Ma pensate per un minuto.

x = f x

Poiché x = f x, allora possiamo sostituire il valore di x sul lato destro di questo, giusto? Così dunque ...

x = f . f $ x -- or x = f (f x)
x = f . f . f $ x -- or x = f (f (f x))
x = f . f . f . f . f . f . f . f . f . f . f $ x -- etc.

Quindi il trucco è, al fine di interrompere, f deve generare una sorta di struttura, in modo che una successiva f lattina modello match che struttura e terminare la ricorsione, senza realmente preoccuparsi circa il "valore" pieno del suo parametro ( ?)

A meno che, naturalmente, si vuole fare qualcosa di simile a creare un elenco infinito, come illustrato luqui.

spiegazione fattoriale di TomMD è buona. Tipo firma di correzione è (a -> a) -> a. La firma tipo per (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) è (b -> b) -> b -> b, in altre parole, (b -> b) -> (b -> b). Quindi possiamo dire che a = (b -> b). In questo modo, fix prende la nostra funzione, che è a -> a, o realmente, (b -> b) -> (b -> b), e restituisce un risultato di tipo a, in altre parole, b -> b, in altre parole, un'altra funzione!

Aspetta, ho pensato che avrebbe dovuto restituire un punto fisso ... non una funzione. Beh lo fa, più o meno (poiché le funzioni sono dati). Si può immaginare che ci ha dato la funzione definitiva per la ricerca di un fattoriale. Abbiamo dato una funzione che dind sanno ricorsione (quindi uno dei parametri ad essa è una funzione utilizzata per recurse), e fix insegnato che come ricorsione.

Ricordate come ho detto che f deve generare una sorta di struttura in modo che un modello di incontro f possono poi e terminare? Bene che non è esattamente giusto, credo. TomMD illustrato come possiamo espandere x applicare la funzione e passo verso il caso base. Per il suo funzionamento, ha usato un if / then, e questo è ciò che provoca la terminazione. Dopo ripetute sostituzioni, la parte in dell'intero definizione di fix casualmente cessa di essere definito in termini di x e che è quando è calcolabile e completo.

Answer 3

Hai bisogno di un modo per il punto fisso per terminare. Ampliare il tuo esempio è ovvio che non finirà:

fix id
--> let x = id x in x
--> id x
--> id (id x)
--> id (id (id x))
--> ...

Ecco un esempio reale di me usando correzione (nota io non uso correzione spesso e fu probabilmente stanco / non preoccuparsi di codice leggibile quando ho scritto questo):

(fix (\f h -> if (pred h) then f (mutate h) else h)) q

WTF, che dici! Beh, sì, ma ci sono alcuni punti molto utili qui. Prima di tutto, il tuo primo argomento fix di solito dovrebbe essere una funzione che è il caso 'recurse' e il secondo argomento è i dati su cui agire. Qui è lo stesso codice come una funzione denominata:

getQ h
      | pred h = getQ (mutate h)
      | otherwise = h

Se siete ancora confusi allora forse fattoriale sarà un esempio facile:

fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 5 -->* 120

Avviso valutazione:

fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 3 -->
let x = (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x in x 3 -->
let x = ... in (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 3 -->
let x = ... in (\d -> if d > 0 then d * (x (d-1)) else 1) 3

Oh, hai appena visto? Che x è diventato una funzione all'interno della nostra filiale then.

let x = ... in if 3 > 0 then 3 * (x (3 - 1)) else 1) -->
let x = ... in 3 * x 2 -->
let x = ... in 3 * (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 2 -->

In quanto sopra è necessario ricordare x = f x, quindi i due argomenti della x 2 alla fine invece di 2.

let x = ... in 3 * (\d -> if d > 0 then d * (x (d-1)) else 1) 2 -->

E mi fermo qui!

Answer 4

Come ho capito che è, esso trova un valore per la funzione, in modo tale che emette la stessa cosa si dà. La cattura è, sarà sempre scegliere indefinito (o un ciclo infinito, in Haskell, indefinito e cicli infiniti sono gli stessi) o qualsiasi altra cosa ha il maggior numero undefineds in esso. Ad esempio, con id,

λ <*Main Data.Function>: id undefined
*** Exception: Prelude.undefined

Come si può vedere, non definito è un punto fisso, in modo da fix sceglierà questo. Se invece fai (\ X-> 1: x).

λ <*Main Data.Function>: undefined
*** Exception: Prelude.undefined
λ <*Main Data.Function>: (\x->1:x) undefined
[1*** Exception: Prelude.undefined

Quindi fix può non scegliere indefinito. Per rendere un po 'più collegato a un loop infinito.

λ <*Main Data.Function>: let y=y in y
^CInterrupted.
λ <*Main Data.Function>: (\x->1:x) (let y=y in y)
[1^CInterrupted.

Anche in questo caso, una leggera differenza. Allora, qual è il punto fisso? Cerchiamo repeat 1.

λ <*Main Data.Function>: repeat 1
[1,1,1,1,1,1, and so on
λ <*Main Data.Function>: (\x->1:x) $ repeat 1
[1,1,1,1,1,1, and so on

E 'lo stesso! Dal momento che questo è l'unico punto fisso, fix deve stabilirsi su di esso. fix Spiacente, nessun cicli infiniti o undefined per voi.