Y-Combinator Esempio pratico

Question

Ho letto un po 'ultimamente circa la programmazione funzionale e sto cercando di Grok Y-Combinator. Capisco che è possibile utilizzare la Y-Combinator per attuare efficacemente la ricorsione in una lingua che non supporta direttamente la ricorsione. Tuttavia, ogni lingua che sono in grado di utilizzare già supporta la ricorsione, quindi non sono sicuro di come sarebbe utile per utilizzare la Y-Combinator per questo.

C'è un esempio migliore pratica di utilizzo Y-Combinator che mi manca? Qualcuno ha effettivamente utilizzato uno nel codice di produzione reale? O sta usando l'Y-Combinator in realtà solo un esercizio accademico mind-bending (anche se uno piuttosto fresco).

Answer 1

ho intenzione di essere in disaccordo con le altre risposte: Il tempo determinato punto (Y) Combinator non avere applicazioni pratiche , ma ci vuole una mente molto fantasioso per trovarli . Come Bruce McAdam. Ecco l'estratto dal suo giornale che circa avvolge fino :

  

Il combinatore Y per il calcolo dei punti fissi può essere espresso in standard ML. E 'spesso utilizzato come un esempio della potenza delle funzioni di ordine superiore, ma non è generalmente considerato come una costruzione programmazione utile. Qui, vedremo come una tecnica di programmazione basato sul combinatore Y e involucri può dare ai programmatori un livello di controllo sui meccanismi interni di funzioni non altrimenti possibile senza dover riscrivere e ricompilare il codice. Come esperimento, il tipo inferenza algoritmo W è implementata utilizzando questa tecnica, in modo che i messaggi di errore vengono prodotte con interferenza minima all'algoritmo. Il codice di questo programma di esempio illustra la vera utilità dei concetti e la facilità con cui possono essere applicati. Un certo numero di altre tecniche di implementazione e possibili applicazioni sono anche discusso, compreso l'uso di funzioni di ordine superiore per simulare l'uso di eccezioni e continuazioni.

E 'una grande carta; chiunque sia interessato nella programmazione funzionale sarà probabilmente godere di lettura.

Answer 2

Si potrebbe controllare questo post nifty sull'attuazione della Y Combinator in C #: ricorsive Lambda Expressions , potrebbe aiutare a capire l'idea migliore.

Si consiglia di verificare alcune belle articoli su Wikipedia: Punto fisso combinatore e < a href = "http://en.wikipedia.org/wiki/Fixed-point_theorem#Fixed_point_theorems_in_discrete_mathematics_and_theoretical_computer_science" rel = "nofollow noreferrer"> fissi teoremi di punto

Come dice Nathan, molte tecniche funzionali sono legati alla Combinator Y e sono utili, in modo da tenere a esso! Y è molto utile perché permette di capire il vostro codice migliore, ma non credo che sia particolarmente utile per descrivere come si aiuta.

Answer 3

Si può pensare al combinatore come la macchina virtuale che gestisce la vostra funzione, che si descrive da un funzionale (= funzione di ordine superiore) non ricorsivo.

A volte sarebbe bello avere questo Combinator sotto il controllo del programma, di fare cose simili come Aspect Oriented Programming (memoizing, il rintracciamento, ...), ma nessun linguaggio di programmazione che io conosca lo permette. Probabilmente sarebbe troppo ingombrante la maggior parte del tempo e / o troppo difficile da imparare.

Answer 4

Altri mi possono correggere se sbaglio, ma sono abbastanza sicuro che il combinatore Y è strettamente accademico. Pensateci: per la sua attuazione la lingua ha bisogno per supportare le funzioni di ordine superiore, ma non ricorsione. C'è solo una lingua che conosco così:. Lambda calcolo

Quindi, fino a quando le nostre macchine passano da macchine di Turing a esecuzione su lambda calcolo, il combinatore Y sarà strettamente accademico.

Nota: Altre tecniche funzionali relative al combinatore Y sono utile, in modo da tenere a esso. Comprendere il combinatore Y vi aiuterà a capire continuazioni, valutazione pigra, ecc.

Answer 5

let sprite = pipe4 sprite_start blanks (manyTill attribute newline) blanks (fun a b c _ -> Sprite(a,c))

let sprites = 
    let rec y f x = f (y f) x // The Y Combinator
    //let rec sprites_up = many1Indents sprite sprites_up |>> (fun x -> SubSprites x) // Does not work.
    let sprites_up = y (fun f -> many1Indents sprite f |>> (fun x -> SubSprites x))
    many1Indents sprite sprites_up

Ecco un esempio dal compilatore per una libreria di gioco piuttosto piccolo che sto facendo in F #. Più in particolare, in quanto sopra ho bisogno di avere la sprites_up chiamarsi in modo ricorsivo in caso contrario il parser rientro non avrebbe funzionato correttamente.

Senza la Y Combinator, non avrei potuto fare il parser correttamente e avrei dovuto ricorrere a scrivere qualcosa di simile a questo:

let sprites_up4 = many1Indents sprite error |>> (fun x -> SubSprites x) 
let sprites_up3 = many1Indents sprite sprites_up4 |>> (fun x -> SubSprites x) 
let sprites_up2 = many1Indents sprite sprites_up3 |>> (fun x -> SubSprites x) 
let sprites_up1 = many1Indents sprite sprites_up2 |>> (fun x -> SubSprites x) 
let sprites_up = many1Indents sprite sprites_up1 |>> (fun x -> SubSprites x) 

Non sarebbe stata una grande soluzione, la Y Combinator veramente mi ha salvato lì. Non era certamente la prima cosa che mi venne in mente però.