Buona spiegazione di "Combinatori" (Per non matematici)

Question

Chiunque ha una buona spiegazione dei "combinatori" (combinatori a Y ecc. E NONthe company)?

Sto cercando uno per il programmatore pratico che comprende la ricorsione e le funzioni di ordine superiore, ma non ha una solida teoria o matematica.

(Nota: che sto parlando di these things)

Answer 1

Questo è un buon article. Gli esempi di codice sono in schema, ma non dovrebbero essere difficili da seguire.

Answer 2

A meno che tu non sia profondamente interessato alla teoria, puoi considerare il combinatore Y un semplice trucco con funzioni, come le monadi.

Monade consentono di concatenare azioni, il combinatore Y consente di definire le funzioni auto-ricorsive in .

Python è dotato di supporto per le funzioni di auto-ricorsiva, in modo da li può definire senza Y:

> def fun(): 
> print "bla" 
> fun() 

> fun() 
bla 
bla 
bla 
... 

fun è accessibile all'interno fun stessa, in modo che possiamo facilmente chiamare.

Ma cosa succede se Python erano diverse, e fun non erano accessibili all'interno fun?

> def fun(): 
> print "bla" 
> # what to do here? (cannot call fun!) 

La soluzione è passare fun stesso come un argomento di fun:

> def fun(arg): # fun receives itself as argument 
> print "bla" 
> arg(arg) # to recur, fun calls itself, and passes itself along 

E Y rende possibile:

> def Y(f): 
> f(f) 

> Y(fun) 
bla 
bla 
bla 
... 

Tutto lo fa chiamare una funzione con sé come argomento.

(non so se questa definizione di Y è corretta al 100%, ma credo che sia l'idea generale.)

Answer 3

Reginald Braithwaite (aka raganwald) ha scritto una grande serie su combinatori in Ruby sopra al suo nuovo blog, homoiconic.

Mentre non (a mia conoscenza) cerca nella Y-Combinator sé, egli ha un aspetto in altri combinatori, per esempio:

• il Kestrel
• il Thrush
• il Cardinal
• le Obdurate Kestrel
• altri Quirky Uccelli

e alcuni post su come si canuse loro.

Answer 4

Sono un po 'corto di teoria, ma posso darti un esempio che mette a fuoco la mia immaginazione, che potrebbe esserti utile. Il combinatore più semplice e interessante è probabilmente "test".

Spero che tu sappia Python

tru = lambda x,y: x 
fls = lambda x,y: y 

test = lambda l,m,n: l(m,n) 

Usage:

>>> test(tru,"goto loop","break") 
'goto loop' 
>>> test(fls,"goto loop","break") 
'break' 

test valuta al secondo argomento, se il primo argomento è vera, altrimenti il ​​terzo.

>>> x = tru 
>>> test(x,"goto loop","break") 
'goto loop' 

interi sistemi può essere costruita da pochi combinatori di base.

(Questo esempio è più o meno copiato fuori dei tipi e linguaggi di programmazione di Benjamin C. Pierce)

Answer 5

Citazione Wikipedia:

un combinatore è una funzione di ordine superiore che utilizza solo la funzione di applicazione e combinatori definiti in precedenza per definire un risultato dai suoi argomenti.

Ora cosa significa? Significa che un combinatore è una funzione (l'output è determinato unicamente dal suo input) il cui input include una funzione come argomento.

Che aspetto hanno queste funzioni e a che cosa servono? Ecco alcuni esempi:

(f o g)(x) = f(g(x))

qui o è un combinatore che prende in 2 funzioni, f e g, e restituisce una funzione come risultato, la composizione di f con g, cioè f o g.

Gli abbinatori possono essere utilizzati per nascondere la logica. Diciamo che abbiamo un tipo di dati NumberUndefined, dove NumberUndefined può assumere un valore numerico Num x o un valore Undefined, dove x a è un Number. Ora vogliamo costruire addizione, sottrazione, moltiplicazione e divisione per questo nuovo tipo numerico. La semantica è la stessa di quella di Number, tranne se Undefined è un input, l'output deve essere anche Undefined e quando si divide per il numero 0 l'output è anche Undefined.

Si potrebbe scrivere il codice noioso come di seguito:

Undefined +' num = Undefined 
num +' Undefined = Undefined 
(Num x) +' (Num y) = Num (x + y) 

Undefined -' num = Undefined 
num -' Undefined = Undefined 
(Num x) -' (Num y) = Num (x - y) 

Undefined *' num = Undefined 
num *' Undefined = Undefined 
(Num x) *' (Num y) = Num (x * y) 

Undefined /' num = Undefined 
num /' Undefined = Undefined 
(Num x) /' (Num y) = if y == 0 then Undefined else Num (x/y) 

Notate come l'hanno tutti la stessa logica riguardante Undefined valori di input. Solo la divisione fa un po 'di più. La soluzione è estrarre la logica rendendola un combinatore.

comb (~) Undefined num = Undefined 
comb (~) num Undefined = Undefined 
comb (~) (Num x) (Num y) = Num (x ~ y) 

x +' y = comb (+) x y 
x -' y = comb (-) x y 
x *' y = comb (*) x y 
x /' y = if y == Num 0 then Undefined else comb (/) x y 

Questo può essere generalizzato nel cosiddetto Maybe monade che i programmatori fanno uso di linguaggi funzionali come Haskell, ma non voglio andare lì.

Answer 6

In breve, il combinatore Y è una funzione di ordine superiore che viene utilizzata per implementare la ricorsione su espressioni lambda (funzioni anonime). Controlla l'articolo How to Succeed at Recursion Without Really Recursing di Mike Vanier: è una delle migliori spiegazioni pratiche su questo argomento che ho visto.

Inoltre, eseguire la scansione del SO archivi:

• What is a y-combinator?
• Y-Combinator Practical Example

Answer 7

un combinatore è funzione con senza variabili libere. Ciò significa, tra le altre cose, che il combinatore non ha dipendenze su cose al di fuori della funzione, solo sui parametri di funzione.

Utilizzando F # Questa è la mia comprensione della combinatori:

let sum a b = a + b;; //sum function (lambda) 

Nel caso somma sopra è un combinatore perché entrambi a e b sono legati ai parametri di funzione.

let sum3 a b c = sum((sum a b) c);; 

La funzione di cui sopra non è un combinatore in quanto utilizza sum, che non è una variabile vincolata (cioè esso non proviene da uno qualsiasi dei parametri).

possiamo fare sum3 un combinatore semplicemente passando la funzione somma come uno dei parametri:

let sum3 a b c sumFunc = sumFunc((sumFunc a b) c);; 

questo modo sumFunc è vincolati e quindi l'intera funzione è un combinatore.

Quindi, questa è la mia comprensione dei combinatori. Il loro significato, d'altra parte, mi sfugge ancora. Come altri hanno sottolineato, i combinatori a virgola fissa consentono di esprimere una funzione ricorsiva senza ricorsione explicit. Cioè invece di chiamare se stesso la funzione recusrsive chiama lambda che viene passato come uno degli argomenti.

Ecco una delle derivazioni Combinator più comprensibili che ho trovato:

http://mvanier.livejournal.com/2897.html

Answer 8

questo sembra un buon compromesso: http://www.catonmat.net/blog/derivation-of-ycombinator/