Cos'è un combinatore Y?[Chiuso]

https://stackoverflow.com/questions/93526

01-07-2019
|

Domanda

Un combinatore Y è un concetto informatico dal lato “funzionale” delle cose.La maggior parte dei programmatori non sa molto sui combinatori, sempre che ne abbiano sentito parlare.

Cos'è un combinatore Y?
Come funzionano i combinatori?
A cosa servono?
Sono utili nei linguaggi procedurali?

Soluzione

Se sei pronto per una lunga lettura, Mike Vanier ha un Grande spiegazione.Per farla breve, ti consente di implementare la ricorsione in un linguaggio che non necessariamente la supporta in modo nativo.

Altri suggerimenti

Un combinatore Y è un "funzionale" (una funzione che opera su altre funzioni) che consente la ricorsione, quando non è possibile fare riferimento alla funzione dall'interno di se stessa.Nella teoria informatica, it generalizza la ricorsione, astraendo la sua implementazione e quindi separandola dal lavoro effettivo della funzione in questione.Il vantaggio di non aver bisogno di un nome in fase di compilazione per la funzione ricorsiva è una sorta di vantaggio.=)

Questo è applicabile nelle lingue che supportano funzioni lambda.IL espressioneLa natura basata sui lambda di solito significa che non possono riferirsi a se stessi per nome.E aggirare questo problema dichiarando la variabile, facendo riferimento ad essa e quindi assegnandole la lambda, per completare il ciclo di autoreferenzialità, è fragile.La variabile lambda può essere copiata e la variabile originale riassegnata, il che interrompe l'autoreferenzialità.

I combinatori a Y sono difficili da implementare e spesso da utilizzare di tipo statico lingue (che linguaggi procedurali spesso lo sono), perché di solito le restrizioni di digitazione richiedono che il numero di argomenti per la funzione in questione sia noto in fase di compilazione.Ciò significa che è necessario scrivere un combinatore y per qualsiasi conteggio di argomenti che è necessario utilizzare.

Di seguito è riportato un esempio di utilizzo e funzionamento di un Y-Combinator, in C#.

L'uso di un combinatore Y implica un modo "insolito" di costruire una funzione ricorsiva.Per prima cosa devi scrivere la tua funzione come un pezzo di codice che chiama una funzione preesistente, piuttosto che se stessa:

// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);

Quindi lo trasformi in una funzione che accetta una funzione da chiamare e restituisce una funzione che lo fa.Questo è chiamato funzionale, perché prende una funzione ed esegue con essa un'operazione che risulta in un'altra funzione.

// A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func<Func<Double, Double>, Func<Double, Double>> fact =
  (recurs) =>
    (x) =>
      x == 0 ? 1 : x * recurs(x - 1);

Ora hai una funzione che accetta una funzione e restituisce un'altra funzione che assomiglia a un fattoriale, ma invece di chiamare se stessa, chiama l'argomento passato alla funzione esterna.Come si fa a renderlo il fattoriale?Passare la funzione interiore a se stesso.Il Combinatore Y fa questo, essendo una funzione con un nome permanente, che può introdurre la ricorsione.

// One-argument Y-Combinator.
public static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> F)
{
  return
    t =>  // A function that...
      F(  // Calls the factorial creator, passing in...
        Y(F)  // The result of this same Y-combinator function call...
              // (Here is where the recursion is introduced.)
        )
      (t); // And passes the argument into the work function.
}

Invece della chiamata del fattoriale stesso, ciò che accade è che il fattoriale chiama il generatore fattoriale (restituito dalla chiamata ricorsiva a Y-Combinator).E a seconda del valore corrente di t, la funzione restituita dal generatore chiamerà nuovamente il generatore, con t - 1, o restituirà semplicemente 1, terminando la ricorsione.

È complicato e criptico, ma tutto si risolve in fase di esecuzione e la chiave del suo funzionamento è "l'esecuzione differita" e la suddivisione della ricorsione per estendere due funzioni.La F interna è passato come argomento, da chiamare nella prossima iterazione, solo se necessario.

L'ho preso da http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html che è una spiegazione che ho scritto diversi anni fa.

Utilizzerò JavaScript in questo esempio, ma funzioneranno anche molti altri linguaggi.

Il nostro obiettivo è essere in grado di scrivere una funzione ricorsiva di 1 variabile usando solo funzioni di 1 variabili e nessuna assegnazione, definire le cose per nome, ecc.(Perché questo è il nostro obiettivo è un'altra domanda, prendiamola come la sfida che ci viene data.) Sembra impossibile, eh?Ad esempio, implementiamo fattoriale.

Bene, il passaggio 1 è dire che potremmo farlo facilmente se tradissimo un po '.Usando funzioni di 2 variabili e assegnazione possiamo almeno evitare di dover utilizzare l'assegnazione per impostare la ricorsione.

// Here's the function that we want to recurse.
X = function (recurse, n) {
  if (0 == n)
    return 1;
  else
    return n * recurse(recurse, n - 1);
};

// This will get X to recurse.
Y = function (builder, n) {
  return builder(builder, n);
};

// Here it is in action.
Y(
  X,
  5
);

Adesso vediamo se riusciamo a imbrogliare di meno.Bene, prima stiamo usando un incarico, ma non ne abbiamo bisogno.Possiamo semplicemente scrivere X e Y in linea.

// No assignment this time.
function (builder, n) {
  return builder(builder, n);
}(
  function (recurse, n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse, n - 1);
  },
  5
);

Ma stiamo usando funzioni di 2 variabili per ottenere una funzione di 1 variabile.Possiamo sistemarlo?Beh, un ragazzo intelligente di nome Haskell Curry ha un trucco accurato, se hai buone funzioni di ordine superiore, allora hai solo bisogno di funzioni di 1 variabile.La prova è che puoi ottenere da funzioni di 2 (o più nel caso generale) variabili a 1 variabile con una trasformazione del testo puramente meccanico come questa:

// Original
F = function (i, j) {
  ...
};
F(i,j);

// Transformed
F = function (i) { return function (j) {
  ...
}};
F(i)(j);

Dove ...rimane esattamente lo stesso.(Questo trucco si chiama "Currying" dopo il suo inventore.La lingua Haskell è anche nominata per Haskell Curry.File che sotto le curiosità inutili.) Ora applicano questa trasformazione ovunque e otteniamo la nostra versione finale.

// The dreaded Y-combinator in action!
function (builder) { return function (n) {
  return builder(builder)(n);
}}(
  function (recurse) { return function (n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse)(n - 1);
  }})(
  5
);

Sentiti libero di provarlo.alert() che ritorna, collegalo a un pulsante, qualunque cosa.Tale codice calcola fattoriali, in modo ricorsivo, senza utilizzare l'assegnazione, le dichiarazioni o le funzioni di 2 variabili.(Ma provare a tracciare il modo in cui funziona è probabile che ti farà girare la testa.E consegnarlo, senza la derivazione, solo leggermente riformattati comporterà un codice che sicuramente confonderà e confonderà.)

Puoi sostituire le 4 linee che definiscono ricorsivamente fattoriali con qualsiasi altra funzione ricorsiva che desideri.

Mi chiedo se sia utile tentare di costruirlo da zero.Vediamo.Ecco una funzione fattoriale di base e ricorsiva:

function factorial(n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

Effettuiamo il refactoring e creiamo una nuova funzione chiamata fact che restituisce una funzione di calcolo fattoriale anonima invece di eseguire il calcolo stesso:

function fact() {
    return function(n) {
        return n == 0 ? 1 : n * fact()(n - 1);
    };
}

var factorial = fact();

È un po' strano, ma non c'è niente di sbagliato in questo.Stiamo semplicemente generando una nuova funzione fattoriale ad ogni passaggio.

La ricorsione in questa fase è ancora abbastanza esplicita.IL fact la funzione deve essere consapevole del proprio nome.Parametrizziamo la chiamata ricorsiva:

function fact(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
}

function recurser(x) {
    return fact(recurser)(x);
}

var factorial = fact(recurser);

È fantastico, ma recurser ha ancora bisogno di conoscere il proprio nome.Parametrizziamo anche quello:

function recurser(f) {
    return fact(function(x) {
        return f(f)(x);
    });
}

var factorial = recurser(recurser);

Ora, invece di chiamare recurser(recurser) direttamente, creiamo una funzione wrapper che restituisce il suo risultato:

function Y() {
    return (function(f) {
        return f(f);
    })(recurser);
}

var factorial = Y();

Ora possiamo sbarazzarci di recurser nome del tutto;è solo un argomento della funzione interna di Y, che può essere sostituita con la funzione stessa:

function Y() {
    return (function(f) {
        return f(f);
    })(function(f) {
        return fact(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y();

L'unico nome esterno a cui si fa ancora riferimento è fact, ma a questo punto dovrebbe essere chiaro che anche questo è facilmente parametrizzabile, creando la soluzione completa e generica:

function Y(le) {
    return (function(f) {
        return f(f);
    })(function(f) {
        return le(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y(function(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
});

La maggior parte delle risposte sopra descrivono cosa è il combinatore Y È ma non di cosa si tratta per.

Combinatori di punto fisso sono usati per dimostrarlo calcolo lambda È completamento.Questo è un risultato molto importante nella teoria del calcolo e fornisce una base teorica per programmazione funzionale.

Lo studio dei combinatori a punto fisso mi ha anche aiutato a comprendere veramente la programmazione funzionale.Tuttavia non ho mai trovato alcun utilizzo per loro nella programmazione vera e propria.

combinatore y in JavaScript:

var Y = function(f) {
  return (function(g) {
    return g(g);
  })(function(h) {
    return function() {
      return f(h(h)).apply(null, arguments);
    };
  });
};

var factorial = Y(function(recurse) {
  return function(x) {
    return x == 0 ? 1 : x * recurse(x-1);
  };
});

factorial(5)  // -> 120

Modificare:Imparo molto guardando il codice, ma questo è un po' difficile da digerire senza un po' di background, mi spiace.Con alcune conoscenze generali presentate da altre risposte, puoi iniziare a distinguere ciò che sta accadendo.

La funzione Y è il "combinatore y".Ora dai un'occhiata a var factorial linea in cui viene utilizzato Y.Nota che gli passi una funzione che ha un parametro (in questo esempio, recurse) che viene utilizzato anche successivamente nella funzione interna.Il nome del parametro diventa fondamentalmente il nome della funzione interna permettendole di eseguire una chiamata ricorsiva (poiché utilizza recurse() nella sua definizione.) Il combinatore y esegue la magia di associare la funzione interna altrimenti anonima con il nome del parametro della funzione passata a Y.

Per la spiegazione completa di come Y esegue la magia, dai un'occhiata al articolo collegato (non da me comunque.)

Per i programmatori che non hanno approfondito la programmazione funzionale e non desiderano iniziare ora, ma sono leggermente curiosi:

Il combinatore Y è una formula che consente di implementare la ricorsione in una situazione in cui le funzioni non possono avere nomi ma possono essere passate come argomenti, utilizzate come valori restituiti e definite all'interno di altre funzioni.

Funziona passando la funzione a se stesso come argomento, in modo che possa richiamare se stesso.

Fa parte del lambda calcolo, che in realtà è matematica ma è effettivamente un linguaggio di programmazione, ed è piuttosto fondamentale per l'informatica e soprattutto per la programmazione funzionale.

Il valore pratico quotidiano del combinatore Y è limitato, poiché i linguaggi di programmazione tendono a consentire di nominare le funzioni.

Nel caso in cui sia necessario identificarlo in una fila di polizia, assomiglia a questo:

Y = λf.(λx.f (x x)) (λx.f (x x))

Di solito puoi individuarlo a causa del ripetuto (λx.f (x x)).

IL λ I simboli sono la lettera greca lambda, che dà il nome al lambda calcolo, e ce ne sono molti (λx.t) termini di stile perché è così che appare il lambda calcolo.

Altre risposte forniscono una risposta abbastanza concisa a questo, senza un fatto importante:Non è necessario implementare il combinatore di punto fisso in nessun linguaggio pratico in questo modo contorto e farlo non ha alcuno scopo pratico (tranne "guarda, so cos'è il combinatore Y").È un concetto teorico importante, ma di scarso valore pratico.

Ecco un'implementazione JavaScript del Combinatore Y e della funzione Fattoriale (dall'articolo di Douglas Crockford, disponibile all'indirizzo: http://javascript.crockford.com/little.html).

function Y(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);
        });
    }));
}

var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});

var number120 = factorial(5);

Un combinatore Y è un altro nome per un condensatore di flusso.

Ho scritto una sorta di "guida per idioti" all'Y-Combinator sia in Clojure che in Scheme per aiutarmi ad affrontarlo.Sono influenzati dal materiale di "The Little Schemer"

Nello schema:https://gist.github.com/z5h/238891

o Clojure:https://gist.github.com/z5h/5102747

Entrambi i tutorial sono codici intervallati da commenti e dovrebbero essere tagliati e incollati nel tuo editor preferito.

Ricorsione anonima

Un combinatore a virgola fissa è una funzione di ordine superiore fix che per definizione soddisfa l'equivalenza

forall f.  fix f  =  f (fix f)

fix f rappresenta una soluzione x all'equazione di punto fisso

               x  =  f x

Il fattoriale di un numero naturale può essere dimostrato da

fact 0 = 1
fact n = n * fact (n - 1)

Utilizzando fix, dimostrazioni costruttive arbitrarie su funzioni generali/μ-ricorsive possono essere derivate senza autoreferenzialità anonima.

fact n = (fix fact') n

Dove

fact' rec n = if n == 0
                then 1
                else n * rec (n - 1)

tale che

   fact 3
=  (fix fact') 3
=  fact' (fix fact') 3
=  if 3 == 0 then 1 else 3 * (fix fact') (3 - 1)
=  3 * (fix fact') 2
=  3 * fact' (fix fact') 2
=  3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1)
=  3 * 2 * (fix fact') 1
=  3 * 2 * fact' (fix fact') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1)
=  3 * 2 * 1 * (fix fact') 0
=  3 * 2 * 1 * fact' (fix fact') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1)
=  3 * 2 * 1 * 1
=  6

Questa prova formale che

fact 3  =  6

utilizza metodicamente l'equivalenza del combinatore in virgola fissa per riscrive

fix fact'  ->  fact' (fix fact')

Calcolo lambda

IL lambda calcolo non tipizzato il formalismo consiste in una grammatica libera dal contesto

E ::= v        Variable
   |  λ v. E   Abstraction
   |  E E      Application

Dove v spazia sulle variabili, insieme a beta E riduzione dell’ETA regole

(λ x. B) E  ->  B[x := E]                                 Beta
  λ x. E x  ->  E          if x doesn’t occur free in E   Eta

La riduzione beta sostituisce tutte le occorrenze libere della variabile x nel corpo di astrazione (“funzione”) B dall'espressione (“argomento”) E.La riduzione dell'ETA elimina l'astrazione ridondante.Talvolta viene omesso dal formalismo.UN irriducibile è presente un'espressione alla quale non si applica alcuna regola di riduzione normale O forma canonica.

λ x y. E

è una scorciatoia per

λ x. λ y. E

(multiarità dell’astrazione),

E F G

è una scorciatoia per

(E F) G

(applicazione sinistra-associatività),

λ x. x

λ y. y

Sono equivalente alfa.

Astrazione e applicazione sono le uniche due “primitive del linguaggio” del lambda calcolo, ma lo consentono codifica di dati e operazioni arbitrariamente complessi.

I numeri Church sono una codifica dei numeri naturali simile ai naturali Peano-assiomatici.

   0  =  λ f x. x                 No application
   1  =  λ f x. f x               One application
   2  =  λ f x. f (f x)           Twofold
   3  =  λ f x. f (f (f x))       Threefold
    . . .

SUCC  =  λ n f x. f (n f x)       Successor
 ADD  =  λ n m f x. n f (m f x)   Addition
MULT  =  λ n m f x. n (m f) x     Multiplication
    . . .

Una prova formale che

1 + 2  =  3

utilizzando la regola di riscrittura della riduzione beta:

   ADD                      1            2
=  (λ n m f x. n f (m f x)) (λ g y. g y) (λ h z. h (h z))
=  (λ m f x. (λ g y. g y) f (m f x)) (λ h z. h (h z))
=  (λ m f x. (λ y. f y) (m f x)) (λ h z. h (h z))
=  (λ m f x. f (m f x)) (λ h z. h (h z))
=  λ f x. f ((λ h z. h (h z)) f x)
=  λ f x. f ((λ z. f (f z)) x)
=  λ f x. f (f (f x))                                       Normal form
=  3

Combinatori

Nel calcolo lambda, combinatori sono astrazioni che non contengono variabili libere.Più semplicemente: I, il combinatore di identità

λ x. x

isomorfo alla funzione identità

id x = x

Tali combinatori sono gli operatori primitivi di calcoli combinatori come il sistema SCI.

S  =  λ x y z. x z (y z)
K  =  λ x y. x
I  =  λ x. x

La riduzione della beta non lo è fortemente normalizzante;non tutte le espressioni riducibili, “redexes”, convergono alla forma normale sotto riduzione beta.Un semplice esempio è l’applicazione divergente dell’omega ω combinatore

λ x. x x

a se stesso:

   (λ x. x x) (λ y. y y)
=  (λ y. y y) (λ y. y y)
. . .
=  _|_                     Bottom

La riduzione delle sottoespressioni più a sinistra (“teste”) ha la priorità. Ordine applicativo normalizza gli argomenti prima della sostituzione, ordine normale non.Le due strategie sono analoghe alla valutazione entusiasta, ad es.C e valutazione pigra, ad es.Haskell.

   K          (I a)        (ω ω)
=  (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y))

diverge sotto l’intensa riduzione beta dell’ordine applicativo

=  (λ k l. k) a ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ y. y y) (λ y. y y))
. . .
=  _|_

da allora rigoroso semantica

forall f.  f _|_  =  _|_

ma converge sotto una pigra riduzione beta di ordine normale

=  (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  a

Se un'espressione ha una forma normale, la riduzione beta di ordine normale la troverà.

Y

La proprietà essenziale del Y combinatore a virgola fissa

λ f. (λ x. f (x x)) (λ x. f (x x))

è dato da

   Y g
=  (λ f. (λ x. f (x x)) (λ x. f (x x))) g
=  (λ x. g (x x)) (λ x. g (x x))           =  Y g
=  g ((λ x. g (x x)) (λ x. g (x x)))       =  g (Y g)
=  g (g ((λ x. g (x x)) (λ x. g (x x))))   =  g (g (Y g))
. . .                                      . . .

L'equivalenza

Y g  =  g (Y g)

è isomorfo a

fix f  =  f (fix f)

Il lambda calcolo non tipizzato può codificare dimostrazioni costruttive arbitrarie su funzioni generali/ricorsive μ.

 FACT  =  λ n. Y FACT' n
FACT'  =  λ rec n. if n == 0 then 1 else n * rec (n - 1)

   FACT 3
=  (λ n. Y FACT' n) 3
=  Y FACT' 3
=  FACT' (Y FACT') 3
=  if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1)
=  3 * (Y FACT') (3 - 1)
=  3 * FACT' (Y FACT') 2
=  3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1)
=  3 * 2 * (Y FACT') 1
=  3 * 2 * FACT' (Y FACT') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1)
=  3 * 2 * 1 * (Y FACT') 0
=  3 * 2 * 1 * FACT' (Y FACT') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1)
=  3 * 2 * 1 * 1
=  6

(Moltiplicazione ritardata, confluenza)

Per il lambda calcolo Churchian non tipizzato, è stato dimostrato che esiste un'infinità ricorsivamente enumerabile di combinatori a virgola fissa oltre a Y.

 X  =  λ f. (λ x. x x) (λ x. f (x x))
Y'  =  (λ x y. x y x) (λ y x. y (x y x))
 Z  =  λ f. (λ x. f (λ v. x x v)) (λ x. f (λ v. x x v))
 Θ  =  (λ x y. y (x x y)) (λ x y. y (x x y))
  . . .

La riduzione beta di ordine normale rende il lambda calcolo non esteso e non tipizzato un sistema di riscrittura completo di Turing.

In Haskell il combinatore a virgola fissa può essere implementato in modo elegante

fix :: forall t. (t -> t) -> t
fix f = f (fix f)

La pigrizia di Haskell si normalizza al limite prima che tutte le sottoespressioni siano state valutate.

primes :: Integral t => [t]
primes = sieve [2 ..]
   where
      sieve = fix (\ rec (p : ns) ->
                     p : rec [n | n <- ns
                                , n `rem` p /= 0])

David Turner: Tesi di Church e programmazione funzionale
Chiesa di Alonzo: Un problema irrisolvibile della teoria elementare dei numeri
Calcolo lambda
Teorema di Church-Rosser

Il combinatore y implementa la ricorsione anonima.Quindi invece di

function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

tu puoi fare

function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

ovviamente il combinatore y funziona solo nelle lingue chiamate per nome.Se desideri utilizzarlo in qualsiasi normale linguaggio call-by-value, allora avrai bisogno del relativo combinatore z (il combinatore y divergerà/loop infinito).

Come principiante dei combinatori, ho scoperto L'articolo di Mike Vanier (grazie Nicholas Mancuso) per essere stato davvero d'aiuto.Vorrei scrivere un riassunto, oltre a documentare quanto ho capito, se potesse essere di aiuto a qualcun altro mi farebbe molto piacere.

Da Schifoso A Meno schifoso

Usando il fattoriale come esempio, usiamo quanto segue almost-factorial funzione per calcolare il fattoriale del numero x:

def almost-factorial f x = if iszero x
                           then 1
                           else * x (f (- x 1))

Nello pseudo-codice sopra, almost-factorial assume funzione f e numero x (almost-factorial è al curry, quindi può essere visto come se stesse assumendo funzione f e restituendo una funzione 1-arità).

Quando almost-factorial calcola il fattoriale per x, delega il calcolo del fattoriale per x - 1 funzionare f e accumula quel risultato con x (in questo caso moltiplica il risultato di (x - 1) per x).

Può essere visto come almost-factorial prende in a schifoso versione della funzione fattoriale (che può calcolare solo fino al numero x - 1) e restituisce a meno schifoso versione del fattoriale (che calcola fino al numero x).Come in questa forma:

almost-factorial crappy-f = less-crappy-f

Se passiamo ripetutamente il meno schifoso versione del fattoriale a almost-factorial, alla fine otterremo la funzione fattoriale desiderata f.Dove può essere considerato come:

almost-factorial f = f

Punto fisso

Il fatto che almost-factorial f = f significa f è il punto fisso di funzione almost-factorial.

Questo è stato un modo davvero interessante di vedere le relazioni delle funzioni di cui sopra ed è stato un momento aha per me.(per favore leggi il post di Mike sul punto fisso se non l'hai fatto)

Tre funzioni

Per generalizzare, abbiamo a non ricorsivo funzione fn (come il nostro quasi-fattoriale), abbiamo il suo punto fisso funzione fr (come la nostra f), allora cosa Y fa è quando dai Y fn, Y restituisce la funzione punto fisso di fn.

Quindi riassumendo (semplificando assumendo fr accetta solo un parametro; x degenera a x - 1, x - 2...in ricorsione):

Definiamo il calcoli fondamentali COME fn: def fn fr x = ...accumulate x with result from (fr (- x 1)), questo è il quasi utile funzione - anche se non possiamo usarla fn direttamente su x, tornerà utile molto presto.Questo non ricorsivo fn utilizza una funzione fr per calcolarne il risultato
fn fr = fr, fr è il punto fisso di fn, fr è il utile funzione, possiamo usare fr SU x per ottenere il nostro risultato
Y fn = fr, Y restituisce il punto fisso di una funzione, Y trasforma il nostro quasi utile funzione fn in utile fr

Derivare `Y` (non incluso)

Tralascerò la derivazione di Y e vai alla comprensione Y.Il post di Mike Vainer contiene molti dettagli.

La forma di `Y`

Y è definito come (in calcolo lambda formato):

Y f = λs.(f (s s)) λs.(f (s s))

Se sostituiamo la variabile s nella sinistra delle funzioni, otteniamo

Y f = λs.(f (s s)) λs.(f (s s))
=> f (λs.(f (s s)) λs.(f (s s)))
=> f (Y f)

Quindi in effetti, il risultato di (Y f) è il punto fisso di f.

Perché lo fa `(Y f)` lavoro?

A seconda della firma di f, (Y f) può essere una funzione di qualsiasi arità, per semplificare, supponiamo (Y f) accetta solo un parametro, come la nostra funzione fattoriale.

def fn fr x = accumulate x (fr (- x 1))

Da fn fr = fr, continuiamo

=> accumulate x (fn fr (- x 1))
=> accumulate x (accumulate (- x 1) (fr (- x 2)))
=> accumulate x (accumulate (- x 1) (accumulate (- x 2) ... (fn fr 1)))

il calcolo ricorsivo termina quando il più interno (fn fr 1) è il caso base e fn non usa fr nel calcolo.

Guardando Y Ancora:

fr = Y fn = λs.(fn (s s)) λs.(fn (s s))
=> fn (λs.(fn (s s)) λs.(fn (s s)))

COSÌ

fr x = Y fn x = fn (λs.(fn (s s)) λs.(fn (s s))) x

Per me, le parti magiche di questa configurazione sono:

fn E fr dipendono l'uno dall'altro: fr 'avvolge' fn dentro, ogni volta fr viene utilizzato per calcolare x, "genera" ("solleva"?) e fn e delega il calcolo a quello fn (passante in sé fr E x);d'altra parte, fn dipende da fr e usi fr per calcolare il risultato di un problema più piccolo x-1.
Al momento fr viene utilizzato per definire fn (Quando fn usi fr nelle sue operazioni), il reale fr non è ancora definito.
Suo fn che definisce la vera logica aziendale.Basato su fn, Y crea fr -una funzione di aiuto in una forma specifica -per facilitare il calcolo fn in un ricorsivo maniera.

Mi ha aiutato a capire Y in questo modo al momento, spero che sia d'aiuto.

A proposito, ho trovato anche il libro Un'introduzione alla programmazione funzionale attraverso il Lambda Calcolo molto bene, sono solo in parte consapevole del fatto che non riuscivo a concentrarmi Y nel libro mi ha portato a questo post.

Ecco le risposte a domande originali, compilato da l'articolo (che vale TOTALMENTE la pena leggere) menzionato nel risposta di Nicola Mancuso, così come altre risposte:

Cos'è un combinatore Y?

Un combinatore Y è un "funzionale" (o una funzione di ordine superiore, una funzione che opera su altre funzioni) che accetta un singolo argomento, che è una funzione non ricorsiva, e restituisce una versione della funzione che è ricorsivo.

Un po' ricorsivo =), ma definizione più approfondita:

Un combinatore è semplicemente un'espressione lambda senza variabili libere.
Variabile libera: è una variabile che non è una variabile vincolata.
Variabile vincolata: variabile contenuta nel corpo di un'espressione lambda che ha quel nome di variabile come uno dei suoi argomenti.

Un altro modo di pensare a questo è che combinator è un'espressione lambda, in cui puoi sostituire il nome di un combinator con la sua definizione ovunque si trovi e fare in modo che tutto funzioni ancora (entrerai in un ciclo infinito se combinator lo farebbe contenere riferimento a se stesso, all'interno del corpo lambda).

Il combinatore Y è un combinatore a virgola fissa.

Il punto fisso di una funzione è un elemento del dominio della funzione che viene mappato su se stesso dalla funzione.
Vale a dire, c è un punto fisso della funzione f(x) Se f(c) = c
Questo significa f(f(...f(c)...)) = fn(c) = c

Come funzionano i combinatori?

Gli esempi seguenti presuppongono forte + dinamico digitando:

Combinatore Y pigro (ordine normale):
Questa definizione si applica alle lingue con pigro (anche:valutazione differita, chiamata per necessità): strategia di valutazione che ritarda la valutazione di un'espressione fino a quando il suo valore non è necessario.

Y = λf.(λx.f(x x)) (λx.f(x x)) = λf.(λx.(x x)) (λx.f(x x))

Ciò significa che, per una determinata funzione f (che è una funzione non ricorsiva), la corrispondente funzione ricorsiva può essere ottenuta prima mediante calcolo λx.f(x x), e quindi applicando questa espressione lambda a se stessa.

Combinatore Y rigoroso (ordine applicativo):
Questa definizione si applica alle lingue con stretto (anche:desideroso, avido) valutazione: strategia di valutazione in cui un'espressione viene valutata non appena è legata a una variabile.

Y = λf.(λx.f(λy.((x x) y))) (λx.f(λy.((x x) y))) = λf.(λx.(x x)) (λx.f(λy.((x x) y)))

È uguale a quello pigro nella sua natura, ha solo un extra λ involucri per ritardare la valutazione del corpo della lambda.Ho chiesto un'altra domanda, in qualche modo legato a questo argomento.

A cosa servono?

~~Rubato~~ preso in prestito da risposta di Chris Ammerman:Il combinatore Y generalizza la ricorsione, astraendone l'implementazione e quindi separandola dal lavoro effettivo della funzione in questione.

Anche se Y-combinator ha alcune applicazioni pratiche, è principalmente un concetto teorico, la cui comprensione amplierà la tua visione generale e, probabilmente, aumenterà le tue capacità analitiche e di sviluppo.

Sono utili nei linguaggi procedurali?

COME dichiarato da Mike Vanier: è possibile definire un combinatore Y in molti linguaggi tipizzati staticamente, ma (almeno negli esempi che ho visto) tali definizioni di solito richiedono un po' di hacking di tipo non ovvio, perché il combinatore Y stesso non ha un tipo statico semplice .Questo va oltre lo scopo di questo articolo, quindi non ne parlerò ulteriormente

E come menzionato da Chris Ammerman:la maggior parte dei linguaggi procedurali ha una tipizzazione statica.

Quindi rispondi a questa domanda: non proprio.

Un combinatore di punto fisso (o operatore di punto fisso) è una funzione di ordine superiore che calcola un punto fisso di altre funzioni.Questa operazione è rilevante nella teoria dei linguaggi di programmazione perché consente l'implementazione della ricorsione sotto forma di regola di riscrittura, senza il supporto esplicito del motore runtime del linguaggio.(origine Wikipedia)

L'operatore this può semplificarti la vita:

var Y = function(f) {
    return (function(g) {
        return g(g);
    })(function(h) {
        return function() {
            return f.apply(h(h), arguments);
        };
    });
};

Quindi eviti la funzione extra:

var fac = Y(function(n) {
    return n == 0 ? 1 : n * this(n - 1);
});

Alla fine chiami fac(5).

Penso che il modo migliore per rispondere sia scegliere un linguaggio, come JavaScript:

function factorial(num)
{
    // If the number is less than 0, reject it.
    if (num < 0) {
        return -1;
    }
    // If the number is 0, its factorial is 1.
    else if (num == 0) {
        return 1;
    }
    // Otherwise, call this recursive procedure again.
    else {
        return (num * factorial(num - 1));
    }
}

Ora riscrivilo in modo che non utilizzi il nome della funzione all'interno della funzione, ma lo chiami comunque in modo ricorsivo.

L'unico posto è il nome della funzione factorial dovrebbe essere visto sul luogo della chiamata.

Suggerimento:non è possibile utilizzare nomi di funzioni, ma è possibile utilizzare nomi di parametri.

Elabora il problema.Non cercarlo.Una volta risolto, capirai quale problema risolve il combinatore y.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow