Ce qui est un Y-combinator?

Un Y combinator est une science de l'ordinateur le concept de la “fonctionnelle” côté des choses. La plupart des programmeurs ne savent pas beaucoup au sujet de combinators, si ils ont même jamais entendu parler.

Ce qui est un Y-combinator?
Comment combinators travail?
À quoi servent-elles?
Sont-ils utiles dans les langages procéduraux?

Peu d'astuce, si vous en apprendre davantage sur les langages fonctionnels comme je le fais, mieux vaut laisser combinators jusqu'à ce que vous obtenez à l'aise avec elle, sinon, c'est une route à la folie...
Arrivés à sourire à la gravatar de l'éditeur de cette question 🙂 lien sur Mads Torgensen blog
Voir aussi: Claire, intuitive, le calcul du point fixe combinator (Y combinator)?
J'ai écrit un court résumé de partage de ma compréhension du Y Combinator: gist.github.com/houtianze/b274e4b975a28fe08aee681699c3f7d0 je l'ai expliqué (à ma connaissance) comment le "Y Combinator fait fonction récursive"
Comment cette question est "trop large"?

InformationsquelleAutor Chris Ammerman | 2008-09-18

193

Si vous êtes prêt pour une lecture longue, Mike Vanier a un grand explication. Longue histoire courte, il vous permet de mettre en œuvre la récursivité dans une langue qui n'est pas nécessairement en charge en mode natif.
- Génial le lien, mais...c'est juste un lien.
- Parfois, un lien est tout ce que vous devez
- Il est un peu plus qu'un lien si; c'est un lien avec un résumé. Un résumé plus détaillé serait appréciée.
- Compte tenu de la qualité des autres réponses, cela ne devrait pas être accepté de répondre.
- C'est juste un lien, MAIS il ne peut pas obtenir mieux que cela. Cette réponse mérite (add1 votes) avec des pas de base le cas où la condition de sortie; aka une récursion infinie.
- MacFie: je n'ai pas de commentaires sur l'effort, j'ai fait des observations sur la qualité. En général, la politique sur Stack Overflow est que les réponses devraient être autonome, avec des liens vers plus d'informations.
- est droit. C'est un grand lien, mais c'est juste un lien. Il a également été mentionné dans les 3 autres réponses ci-dessous, mais seulement comme un document à l'appui qu'ils ont tous de bonnes explications sur leur propre. Cette réponse n'a même pas de tenter de répondre à l'OP de questions.
InformationsquelleAutor Nicholas Mancuso
278

Un Y combinator est un "fonctionnelle" (une fonction qui fonctionne sur d'autres fonctions) qui permet la récursivité, lorsque vous ne pouvez pas se référer à la fonction à partir de l'intérieur de lui-même. Dans la théorie des sciences, il généralise la récursivité, l'abstraction de sa mise en œuvre, et ce qui le sépare du travail réel de la fonction en question. L'avantage de ne pas avoir besoin d'un moment de la compilation du nom de la fonction récursive est une sorte de bonus. =)

C'est applicable dans les langues lambda fonctions. Le expression-en fonction de la nature des lambdas signifie généralement qu'ils ne peuvent pas se référer à eux-mêmes par leur nom. Et de travail autour de ce en déclarant la variable, qui est venu à elle, puis à attribuer le lambda-il, pour compléter l'auto-référence de la boucle, est fragile. Le lambda variable peut être copié, et la variable d'origine attribué à nouveau, ce qui rompt l'auto-référence.

Y combinators sont lourdes à mettre en œuvre, et souvent à utiliser, dans statique-tapé langues (les langages procéduraux est souvent le cas), parce que d'habitude de taper des restrictions exigent le nombre d'arguments de la fonction en question à être connu au moment de la compilation. Cela signifie qu'un y combinator doit être écrit pour tout argument compter que l'on doit utiliser.

Ci-dessous est un exemple de la façon dont l'utilisation et le fonctionnement d'un Y-Combinator, en C#.

À l'aide d'un Y-combinator implique un "inhabituel" la construction d'une fonction récursive. D'abord, vous devez écrire votre fonction comme un morceau de code qui appelle une pré-existante de la fonction, plutôt que de lui-même:
```
//Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);
```
Alors vous transformer en une fonction qui prend une fonction à appeler, et retourne une fonction qui le fait. Cela s'appelle fonctionnel, car il faut une fonction, et effectue une opération avec elle que les résultats dans une autre fonction.
```
//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);
```
Maintenant, vous avez une fonction qui prend une fonction, et retourne une fonction qui donne l'impression d'être une factorielle, mais au lieu d'appeler lui-même, il appelle l'argument passé à la fonction externe. Comment voulez-vous faire de cette factoriel? Passer à la fonction interne à lui-même. Le Y Combinator fait que, en étant une fonction avec un nom permanent, qui peut introduire la récursivité.
```
//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.
}
```
Plutôt que la factorielle d'appel lui-même, ce qui se passe, c'est que la factorielle appelle la factorielle générateur (retourné par l'appel récursif à Y Combinator). Et en fonction de la valeur actuelle de t la fonction renvoyée à partir du générateur d'appeler le générateur encore, à t - 1, ou juste de retour de 1, la résiliation de la récursivité.

C'est compliqué et cryptique, mais tout s'équilibrera au moment de l'exécution, et la clé de son travail est "l'exécution différée", et la rupture de la récursivité à durée de deux fonctions. L'intérieur F est passé comme argument, d'être appelé dans la prochaine itération, seulement si nécessaire.
- Pourquoi, oh pourquoi avez-vous dû l'appeler " Y "et le paramètre "F"! Ils ont tout simplement perdu dans le type des arguments!
- En Haskell, vous pouvez abstraction de récursivité avec: fix :: (a -> a) -> a, et la a à son tour, peut-être autant d'arguments que vous le souhaitez. Cela signifie que le typage statique n'a pas vraiment faire de cet encombrant.
- Selon Mike Vanier description, votre définition de Y est fait pas un combinateur parce que c'est récursive. En vertu de "l'Élimination (la plupart) explicite la récursivité (paresseux version)" il a le paresseux schéma équivalent de votre code C#, mais les explique dans le point 2: "Il n'est pas un combinator, parce que la Y dans le corps de la définition est une variable indépendante qui est uniquement lié une fois la définition complète..." je pense que la chose cool à propos de Y-combinators est qu'ils produisent de la récursivité en évaluant le point fixe d'une fonction. De cette façon, ils n'ont pas besoin explicite de la récursivité.
- Vous faites un bon point. Il a été quelques années depuis que j'ai posté cette réponse. L'écrémage de Vanier post maintenant je vois que j'ai écrit Y, mais pas un Y Combinator. Je vais lire son post à nouveau bientôt et voir si je peux poster une correction. Mon intuition me signalant que le strict typage statique de C# peut empêcher à la fin, mais je vais voir ce que je peux faire.
- Je n'ai jamais vu le mot "fonctionnel" utilisé comme un substantif de cette façon. Pouvez-vous indiquer toute autre source qui utilise le terme de la même façon?
- Voici une autre explication qui peut compléter ce très grand: blogs.msdn.com/b/wesdyer/archive/2007/02/02/...
- Si je suis compréhension ceci réponse à ma question correctement, vous ne pouvez pas faire un Y combinator en C# parce qu'il veut évaluer les paramètres avant l'appel de fonctions.
- Il est assez courant dans les mathématiques.
- pas tout à fait--fonctionnelles sont celles de la carte à partir de la fonction des espaces à un champ de scalaires, et pas seulement à des fins générales des cartes de fonctions de fonctions
- Je pense que Mads Torgersen correctement implémente le Y combinator en C# dans le blogs.msdn.microsoft.com/madst/2007/05/11/...
InformationsquelleAutor Chris Ammerman
98

J'ai soulevé ce de http://www.mail-archive.com/[email protected]/msg02716.html qui est une explication que j'ai écrit il y a plusieurs années.

Je vais utiliser JavaScript dans cet exemple, mais de nombreuses autres langues de travail.

Notre objectif est d'être capable d'écrire une fonction récursive de 1
variable en utilisant uniquement les fonctions de 1 variables et pas de
d'affectations, de définir les choses par leur nom, etc. (Pourquoi c'est notre
but est une autre question, nous allons juste prendre ce que l'
le défi que nous nous sommes donnés). Semble impossible, hein? Comme
un exemple, nous allons mettre en œuvre factorielle.

Bien l'étape 1 consiste à dire que l'on peut faire facilement si nous
triché un peu. Utilisation des fonctions de 2 variables et
affectation du moins pouvons-nous éviter d'avoir à utiliser
cession pour configurer la récursivité.
```
//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
);
```
Maintenant, nous allons voir si nous pouvons tricher moins. Eh bien tout d'abord que nous utilisons
d'affectation, mais nous n'avons pas besoin de. Il nous suffit d'écrire X et
Y en ligne.
```
//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
);
```
Mais nous sommes à l'aide de fonctions de 2 variables pour obtenir une fonction de 1
variable. Pouvons-nous résoudre ce problème? Eh bien c'est un gars intelligent par le nom de
Haskell Curry a une astuce, si vous avez de bons d'ordre supérieur
fonctions vous avez seulement besoin de fonctions de 1 variable. L'
la preuve est que vous pouvez obtenir à partir de fonctions de 2 (ou plus dans le
cas général) des variables à 1 variable purement
mécanique de transformation du texte comme ceci:
```
//Original
F = function (i, j) {
  ...
};
F(i,j);

//Transformed
F = function (i) { return function (j) {
  ...
}};
F(i)(j);
```
où ... reste exactement la même. (Cette astuce est appelé
"nourrissage" d'après son inventeur. Le langage Haskell est également
nommé pour Haskell Curry. Fichier sous inutile de trivia.)
Maintenant, il suffit d'appliquer cette transformation partout et nous obtenons
notre version 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
);
```
N'hésitez pas à essayer. alert() qui renvoient, de la lier à un bouton, que ce soit.
Ce code calcule factorielles, de manière récursive, sans l'aide de
d'affectation, de déclarations, ou des fonctions de 2 variables. (Mais
pour retrouver la trace de la façon dont il fonctionne est susceptible de vous faire tourner la tête.
Et de remettre, sans la dérivation, juste un peu reformaté
sera le résultat dans le code qui est sûr pour le déflecteur et les confondre.)

Vous pouvez remplacer les 4 lignes que de manière récursive définir factorielle avec
toute autre fonction récursive qui vous voulez.
- Vraiment bien expliqué. Bonne mars de la logique.
- Belle explication. Pourquoi avez-vous écrit function (n) { return builder(builder)(n);} au lieu de builder(builder)?
- Parce que j'étais en tournant une fonction de 2 variables dans un ordre supérieur de la fonction d'une variable à l'aide de nourrissage.
- Est-ce la raison nous avons besoin de fermetures?
- Les fermetures de nous laisser cravate comportement personnalisé derrière un appel à une fonction anonyme. C'est juste une autre abstraction de la technique.
InformationsquelleAutor btilly
80

Je me demande si il n'y a aucune utilisation dans la tentative de construire ce à partir du sol. Voyons voir. Voici une base, la fonction factorielle récursive:
```
function factorial(n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}
```
Nous allons refactoriser et de créer une nouvelle fonction appelée fact qui renvoie un anonyme factorielle-le calcul de la fonction au lieu d'effectuer le calcul en lui-même:
```
function fact() {
    return function(n) {
        return n == 0 ? 1 : n * fact()(n - 1);
    };
}

var factorial = fact();
```
C'est un peu bizarre, mais il n'y a rien de mal à cela. Nous en sommes seulement à la génération d'une nouvelle fonction factorielle à chaque étape.

La récursivité, à ce stade, est encore assez explicite. Le fact fonction doit être conscient de son propre nom. Nous allons paramétrer l'appel récursif:
```
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);
```
C'est très bien, mais recurser faut quand même savoir son nom propre. Nous allons paramétrer qu', trop:
```
function recurser(f) {
    return fact(function(x) {
        return f(f)(x);
    });
}

var factorial = recurser(recurser);
```
Maintenant, au lieu d'appeler recurser(recurser) directement, nous allons créer une fonction wrapper qui renvoie son résultat:
```
function Y() {
    return (function(f) {
        return f(f);
    })(recurser);
}

var factorial = Y();
```
On peut maintenant se débarrasser de la recurser nom de tout; c'est juste un argument de Y sont à l'intérieur de la fonction, qui peut être remplacée par la fonction elle-même:
```
function Y() {
    return (function(f) {
        return f(f);
    })(function(f) {
        return fact(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y();
```
Externe, nom encore référencé est fact, mais il devrait être clair maintenant que c'est facilement paramétrable, aussi, la création de l'complet, générique, solution:
```
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);
    };
});
```
- devrait commencer comme: de retour n <= 2 ? (n == 2 ? 2 : 1) : n * factorielle(n - 1); pour la bonne réponse 0->1 :). de toute façon, agréable de voir l'évolution.
- Merci. Fixe.
- Une explication similaire en JavaScript: igstan.ro/posts/...
- Vous m'avez perdu lorsque vous avez introduit la fonction recurser. Pas la moindre idée de ce qu'il fait, ni pourquoi.
- Nous essayons de construire un générique solution récursive pour les fonctions qui ne sont pas explicitement récursive. Le recurser fonction est la première étape vers cet objectif, car il nous donne une version récursive de fact que jamais des références de lui-même par son nom.
- C'est la plus claire explication de Y combinator j'ai jamais vu. Aussi le commentaire ci-dessus par @WayneBurkett fait beaucoup de sens.
- Puis-je réécrire le Y combinator comme ceci: function Y(recurse) { return recurse(recurse); } let factorial = Y(creator => value => { return value == 0 ? 1 : value * creator(creator)(value - 1); });. Et c'est ainsi que je le digérer(pas sûr si c'est correct): Par pas explicitement référence à la fonction(non autorisé en tant que combinator), on peut utiliser deux partiellement appliquée/au curry fonctions(créateur de la fonction et de la fonction calculate), avec qui nous pouvons créer lambda/fonctions anonymes qui permettent d'atteindre récursive sans avoir besoin d'un nom pour la fonction calculate?
InformationsquelleAutor Wayne Burkett
48

La plupart des réponses ci-dessus décrivent ce que le Y combinator est, mais pas ce qu'il est pour.

Point fixe combinators sont utilisés pour montrer que lambda calcul est turing. C'est un résultat très important dans la théorie du calcul et fournit un fondement théorique à la programmation fonctionnelle.

L'étude de point fixe combinators m'a aussi permis de vraiment comprendre la programmation fonctionnelle. Je n'ai jamais trouvé d'aucune utilité dans la programmation si.
- Merci--- j'ai été frustré par le manque de "pourquoi?" les réponses.
- Bien sûr, vous êtes de gauche avec une encore plus grande "Pourquoi" 🙂 la question est "en haut-en récursif", et à l'infini, donc 😉
InformationsquelleAutor Jørgen Fogh
23

y combinator en 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
```
Modifier:
J'apprends beaucoup en regardant le code, mais celui-ci est un peu difficile à avaler sans quelques arrière-plan - désolé à ce sujet. Avec quelques connaissances générales présentées par d'autres réponses, vous pouvez commencer à chercher en dehors de ce qui se passe.

La fonction Y est le "y combinator". Maintenant, jetez un oeil à la var factorial ligne où Y est utilisé. Avis de passer une fonction qui a un paramètre (dans cet exemple, recurse) qui est également utilisé plus tard dans l'intérieur de la fonction. Le nom du paramètre, fondamentalement, devient le nom de la fonction interne lui permettant de réaliser un appel récursif (car il utilise recurse() dans sa définition.) Le y combinator effectue la magie d'associer les anonymes intérieur de la fonction avec le paramètre nom de la fonction transmise à Y.

Pour l'explication complète de la façon dont Y fait la magie, vérifié les article lié (pas par moi btw.)
- regarde confyoozing! l'intention de code pas clair
- Javascript n'a pas besoin d'un Y-combinator faire anonyme récursivité parce que vous pouvez accéder à la fonction avec des arguments.le destinataire de l'appel (voir la section en.wikipedia.org/wiki/...)
- arguments.callee n'est pas autorisé en Mode Strict: developer.mozilla.org/en/JavaScript/...
- Vous pouvez toujours donner n'importe quelle fonction d'un nom, et si c'est l'expression de fonction alors que le nom n'est connu à l'intérieur de la fonction elle-même. (function fact(n){ return n <= 1? 1 : n * fact(n-1); })(5)
- sauf dans IE. kangax.github.io/enf
InformationsquelleAutor Zach
17

Pour les programmeurs qui n'ont pas rencontré de la programmation fonctionnelle en profondeur, et ne se soucient pas de commencer maintenant, mais sont légèrement curieux:

Le Y combinator est une formule qui permet de mettre en œuvre la récursivité dans une situation où les fonctions ont pas de noms, mais peuvent être passés comme arguments utilisés comme valeurs de retour, et définis dans d'autres fonctions.

Il fonctionne par le passage de la fonction à lui-même comme un argument, de sorte qu'il peut s'appeler elle-même.

C'est une partie du lambda calcul, ce qui est vraiment maths mais est effectivement un langage de programmation, et est assez fondamental, à l'informatique et en particulier à la programmation fonctionnelle.

Au jour le jour à la pratique de la valeur de Y combinator est limité, car les langages de programmation ont tendance à vous laisser le nom des fonctions.

Dans le cas où vous avez besoin d'identifier une police de gamme, il ressemble à ceci:

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

Vous pouvez généralement place à cause de la répétition de l' (λx.f (x x)).

La λ symboles sont la lettre grecque lambda, qui donne le lambda calcul de son nom, et il y a beaucoup de (λx.t) style, parce que c'est ce que le lambda calcul ressemble.
- ce doit être la accepté de répondre. BTW, avec U x = x x, Y = U . (. U) (abusant de Haskell-comme la notation). OIE, avec une bonne combinators, Y = BU(CBU). Ainsi, Yf = U (f . U) = (f . U) (f . U) = f (U (f . U)) = f ((f . U) (f . U)).
InformationsquelleAutor El Zorko
12

D'autres réponses fournir assez concis réponse à cette question, sans que l'un fait important: Vous n'avez pas besoin de mettre en œuvre combinateur de point fixe dans la pratique de la langue dans ce tortueux chemin et de le faire ne sert aucun but pratique (à l'exception de "regardez, je sais de quoi Y combinator est"). Il est important concept théorique, mais de peu de valeur pratique.

InformationsquelleAutor Ales Hakl

Ici est un code JavaScript de la mise en œuvre du Y Combinator et de la fonction Factorielle (à partir de Douglas Crockford de l'article, disponible sur: 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);

InformationsquelleAutor xgMz

6

Un Y Combinator est un autre nom pour un flux condensateur.
- c'est très drôle. 🙂 jeune(re) ceux pourriez ne pas reconnaître la référence si.
- haha! Yep, le jeune (moi) peut encore comprendre...
- Je pensais que c'était vrai et j'ai atterri ici. youtube.com/watch?v=HyWqxkaQpPw Article Récent futurism.com/scientists-made-real-life-flux-capacitor
InformationsquelleAutor Jon Davis
5

J'ai écrit une sorte de "idiots guide" pour le Y Combinator dans les deux Clojure et un Schéma pour m'aider à venir à bout avec elle. Ils sont influencés par article dans "Le Petit Intrigant"

Dans Le Schéma:
https://gist.github.com/z5h/238891

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

Les deux tutoriels sont code entrecoupés de commentaires et doit être coupé & pastable dans votre éditeur préféré.

InformationsquelleAutor z5h
4

Le y combinator met en œuvre anonyme de la récursivité. Ainsi, au lieu de
```
function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }
```
vous pouvez faire
```
function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }
```
bien sûr, le y combinator ne fonctionne qu'en appel par le nom de langues. Si vous souhaitez utiliser ce normal d'appel-par-valeur de la langue, alors vous aurez besoin de la liés à z combinator (y-combinator divergent/infinite loop).
- Y combinator peut travailler avec le passage par valeur et d'évaluation différée.
InformationsquelleAutor Andrew
4

Comme un débutant à combinators, j'ai trouvé Mike Vanier de l'article (merci Nicolas Mancuso) pour être vraiment utile. Je voudrais écrire un résumé, en plus de documenter ma compréhension, si elle pouvait être utile à d'autres, je serais très heureux.

De de Merde à Moins Merdique

À l'aide de factorielles comme un exemple, nous utilisons les almost-factorial fonction pour calculer le factoriel de nombre x:
```
def almost-factorial f x = if iszero x
                           then 1
                           else * x (f (- x 1))
```
Dans le pseudo-code ci-dessus, almost-factorial prend en fonction f et le nombre x (almost-factorial est au cari, de sorte qu'il peut être considéré comme prenant en fonction f renvoi d'un 1-arité de la fonction).

Quand almost-factorial calcule la factorielle pour x, il délègue le calcul de factorielle pour x - 1 à la fonction f et s'accumule à ce résultat avec x (dans ce cas, il multiplie le résultat de (x - 1) x).

Il peut être vu comme almost-factorial prend dans un de merde version de la fonction factorielle (qui ne peut calculer jusqu'au numéro x - 1) et renvoie un moins de merde version de factorielle (qui calcule jusqu'au numéro x). Comme dans ce formulaire:
```
almost-factorial crappy-f = less-crappy-f
```
Si nous avons à plusieurs reprises passer le moins de merde version de factorielle de almost-factorial, nous finirons par obtenir notre fonction factorielle f. Où il peut être considéré comme:
```
almost-factorial f = f
```
Fix -

Le fait que almost-factorial f = f signifie f est le fix-point de la fonction almost-factorial.

C'était vraiment un moyen intéressant de voir les relations des fonctions ci-dessus, et c'était un moment aha pour moi. (veuillez lire Mike post sur fix-là, si vous ne l'avez pas)

Trois fonctions

De généraliser, nous avons un non-récursive fonction fn (comme la quasi-factorielle), nous avons son fix-point fonction fr (comme notre f), alors ce Y n'est lorsque vous donnez Y fn, Y retourne le fix-point de la fonction de fn.

Donc en résumé (simplifié en supposant fr prend qu'un seul paramètre; x dégénère à x - 1, x - 2... dans la récursivité):
- Nous définissons la calculs du cœur comme fn: def fn fr x = ...accumulate x with result from (fr (- x 1)), c'est le presque-utile fonction - bien que nous ne pouvons pas utiliser fn directement sur x, il sera utile très bientôt. Cette non-récursive fn utilise une fonction fr pour calculer son résultat
- fn fr = fr, fr est la correction du point de fn, fr est le utile d'une fonction, on peut utiliser fr sur x pour obtenir notre résultat
- Y fn = fr, Y retourne le fix-point de fonction, Y tourne notre presque-utile fonction fn en utile fr
Découlant Y (non inclus)

Je vais sauter la dérivation de Y et aller à la compréhension de Y. Mike Vainer post a beaucoup de détails.

La forme de Y

Y est définie comme (dans lambda calcul format):
```
Y f = λs.(f (s s)) λs.(f (s s))
```
Si l'on remplace la variable s, à gauche de l'fonctions, nous obtenons
```
Y f = λs.(f (s s)) λs.(f (s s))
=> f (λs.(f (s s)) λs.(f (s s)))
=> f (Y f)
```
Donc en effet, le résultat de (Y f) est la correction du point de f.

Pourquoi ne (Y f) travail?

Selon la signature de f, (Y f) peut être une fonction de toute arité, pour simplifier, supposons (Y f) ne prend qu'un seul paramètre, à l'instar de notre fonction factorielle.
```
def fn fr x = accumulate x (fr (- x 1))
```
depuis fn fr = fr, nous continuons
```
=> 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)))
```
le récursive de calcul s'arrête lorsque l'intérieur de la plupart des (fn fr 1) est le cas de base et fn ne pas utiliser fr dans le calcul.

Regardant Y de nouveau:
```
fr = Y fn = λs.(fn (s s)) λs.(fn (s s))
=> fn (λs.(fn (s s)) λs.(fn (s s)))
```
Donc
```
fr x = Y fn x = fn (λs.(fn (s s)) λs.(fn (s s))) x
```
Pour moi, la magie des pièces de cette configuration sont:
- fn et fr interdepend les uns les autres: fr 'emballages" fn à l'intérieur, chaque fois fr est utilisée pour calculer x, il engendre' ("soulève"?) un fn et délègue le calcul pour que fn (passage en lui-même fr et x); d'autre part, fn dépend fr et utilise fr pour calculer une moindre problème x-1.
- Au moment fr est utilisé pour définir fn (quand fn utilise fr dans ses opérations), le réel fr n'est pas encore défini.
- C'est fn qui définit le véritable logique d'entreprise. Basé sur fn, Y crée fr - une fonction d'assistance dans un formulaire spécifique afin de faciliter le calcul pour fn dans un récursive manière.
Il m'a aidé à comprendre Y de cette façon, pour le moment, espérons que cela aide.

BTW, j'ai aussi trouvé le livre Une Introduction à la Programmation Fonctionnelle Par le biais de Lambda Calcul très bon, je suis seulement en partie grâce à elle et le fait que je ne pouvais pas obtenir ma tête autour de Y dans le livre m'a amené à ce poste.

InformationsquelleAutor Dapeng Li
4

Voici des réponses à la questions originales, compilée à partir de l'article (qui est VRAIMENT la peine de lire) mentionné dans le réponse par Nicolas Mancuso, ainsi que d'autres réponses:

Ce qui est un Y-combinator?

Un Y combinator est un "fonctionnelle" (ou d'une fonction d'ordre supérieur — une fonction qui fonctionne sur d'autres fonctions) qui prend un seul argument, qui est une fonction n'est pas récursive, et renvoie une version de la fonction qui est récursive.

Un peu recursive =), mais plus en profondeur définition:

Un combinator — est juste une expression lambda sans variables libres.

Libre variable est une variable qui n'est pas une variable liée.

Lié variable — variable qui est contenue à l'intérieur du corps d'une expression lambda qui a le nom de la variable que l'un de ses arguments.

Une autre façon de penser à ce sujet est que combinator est une expression lambda, dans laquelle vous êtes en mesure de remplacer le nom d'un combinateur avec sa définition partout où il est présent et ont tout le travail (vous allez entrer dans une boucle infinie si combinator contiendrait référence à lui-même, à l'intérieur du corps de lambda).

Y combinator est un point fixe du combinator.

Point fixe d'une fonction est un élément de la fonction de domaine de ce qui est mappé à lui-même par la fonction.

C'est-à-dire, c est un point fixe de la fonction f(x) si f(c) = c

Cela signifie f(f(...f(c)...)) = fn(c) = c

Comment combinators travail?

Exemples ci-dessous supposent forte + dynamique tapant:

Paresseux (normal-commande) Y-combinator:

Cette définition s'applique aux langues avec lazy (aussi: différé, appel par nécessité) d'évaluation — évaluation de la stratégie, ce qui retarde l'évaluation d'une expression jusqu'à ce que sa valeur est nécessaire.
```
Y = λf.(λx.f(x x)) (λx.f(x x)) = λf.(λx.(x x)) (λx.f(x x))
```
Ce que cela signifie, c'est que, pour une fonction donnée f (qui est un non-récursive de la fonction), la fonction récursive peut être obtenue d'abord par le calcul λx.f(x x), puis en appliquant cette expression lambda pour lui-même.

Strict (applicative-commande) Y-combinator:

Cette définition s'applique aux langues avec la plus stricte (aussi: désireux, avide) d'évaluation — évaluation de la stratégie dans lequel une expression est évaluée dès qu'il est lié à une variable.
```
Y = λf.(λx.f(λy.((x x) y))) (λx.f(λy.((x x) y))) = λf.(λx.(x x)) (λx.f(λy.((x x) y)))
```
C'est même comme un paresseux dans sa nature, il a juste un supplément de λ wrappers pour retarder le lambda du corps de l'évaluation. J'ai demandé à une autre question, plus ou moins liés à ce sujet.

À quoi servent-elles?

~~Vol~~ empruntés réponse par Chris Ammerman: Y-combinator généralise la récursivité, l'abstraction de sa mise en œuvre, et ce qui le sépare du travail réel de la fonction en question.

Même si, Y combinator a quelques applications pratiques, c'est surtout un concept théorique, la compréhension de qui permettra d'élargir votre vision globale et, probablement, une augmentation de votre analyse et des compétences de développeur.

Sont-ils utiles dans les langages procéduraux?

Comme déclaré par Mike Vanier: il est possible de définir un Y combinator dans de nombreux langages statiquement typés, mais (au moins dans les exemples que j'ai vu), ces définitions exigent habituellement une certaine non-évidente type hackery, parce que le Y combinator lui-même ne dispose pas d'un simple de type statique. C'est au-delà de la portée de cet article, donc je n'en parle pas plus

Et comme mentionné par Chris Ammerman: la plupart des langages procéduraux a statique-typage.

Afin de répondre à un — pas vraiment.

InformationsquelleAutor Filipp W.
4

Anonyme récursivité

Un point fixe du combinator est une fonction d'ordre supérieur fix que, par définition, satisfait de l'équivalence
```
forall f.  fix f  =  f (fix f)
```
fix f représente une solution x pour le point fixe de l'équation
```
               x  =  f x
```
La factorielle d'un nombre naturel peut être prouvé par
```
fact 0 = 1
fact n = n * fact (n - 1)
```
À l'aide de fix, arbitraire des preuves constructives sur le général/μ-fonctions récursives peuvent être calculées sans les nonymous l'auto-référentialité.
```
fact n = (fix fact') n
```
où
```
fact' rec n = if n == 0
                then 1
                else n * rec (n - 1)
```
tels que
```
   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
```
Cette preuve formelle que
```
fact 3  =  6
```
méthodiquement utilise le point fixe du combinator équivalence pour réécrit
```
fix fact'  ->  fact' (fix fact')
```
Lambda calcul

La non typée lambda calcul formalisme consiste dans un contexte de grammaire
```
E ::= v        Variable
   |  λ v. E   Abstraction
   |  E E      Application
```
où v de chaînes de variables, en collaboration avec le bêta et eta réduction règles
```
(λ x. B) E  ->  B[x := E]                                 Beta
  λ x. E x  ->  E          if x doesn’t occur free in E   Eta
```
Bêta de réduction des succédanés de toutes gratuit les occurrences de la variable x dans l'abstraction (“fonction”) corps B par l'expression (“argument”) E. Eta réduction en éliminant les doublons d'abstraction. Il est parfois omis dans le formalisme. Un irréductible expression, à laquelle aucune réduction de la règle s'applique, est en normal ou forme canonique.
```
λ x y. E
```
est un raccourci pour
```
λ x. λ y. E
```
(abstraction multiarity),
```
E F G
```
est un raccourci pour
```
(E F) G
```
(application à gauche-associativité),
```
λ x. x
```
et
```
λ y. y
```
sont alpha-équivalent.

L'Abstraction et de la demande sont les deux seuls “langues primitives” du lambda calcul, mais elles permettent de encodage arbitrairement complexes de données et d'opérations.

L'Église, les chiffres sont un codage des nombres naturels semblables aux Peano-axiomatique naturals.
```
   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
    . . .
```
Une preuve formelle que
```
1 + 2  =  3
```
à l'aide de la règle de réécriture de la bêta de réduction:
```
   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
```
Combinators

En lambda calcul, combinators sont des abstractions qui ne contiennent pas de variables libres. Plus simplement: I, l'identité du combinator
```
λ x. x
```
isomorphe à l'identité de la fonction
```
id x = x
```
Tels combinators sont les primitives opérateurs de combinator calculs comme les pistes de SKI du système.
```
S  =  λ x y z. x z (y z)
K  =  λ x y. x
I  =  λ x. x
```
Bêta de réduction n'est pas fortement normalisant; non pas réductible expressions, “redexes”, de converger vers une forme normale en vertu de la bêta de réduction. Un exemple simple est l'application divergente de l'omega ω combinator
```
λ x. x x
```
à lui-même:
```
   (λ x. x x) (λ y. y y)
=  (λ y. y y) (λ y. y y)
. . .
=  _|_                     Bottom
```
Réduction de gauche sous-expressions (“tête”) est une priorité. Applicative afin normalise les arguments avant de substitution, ordre normal ne le fait pas. Les deux stratégies sont analogues à ceux désireux d'évaluation, par exemple C, et de l'évaluation différée, par exemple, Haskell.
```
   K          (I a)        (ω ω)
=  (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y))
```
diverge sous désireux applicative ordre bêta réduction
```
=  (λ 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))
. . .
=  _|_
```
depuis dans stricte sémantique
```
forall f.  f _|_  =  _|_
```
mais converge en vertu de paresseux normal d'ordre bêta réduction
```
=  (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  a
```
Si une expression a une forme normale, normale ordre bêta réduction de la trouver.

Y

La propriété essentielle de la Y point fixe combinator
```
λ f. (λ x. f (x x)) (λ x. f (x x))
```
est donnée par
```
   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'équivalence
```
Y g  =  g (Y g)
```
est isomorphe à
```
fix f  =  f (fix f)
```
Le type lambda calcul peut encoder arbitraire des preuves constructives sur le général/μ-fonctions récursives.
```
 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
```
(Multiplication retard, confluence)

Pour Churchian non typée lambda calcul, il a été démontré pour un récursivement énumérable infinité de point fixe combinators outre 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))
  . . .
```
Normal d'ordre bêta réduction rend le rangement de type lambda calcul un de Turing-réécriture complète du système.

En Haskell, le point fixe du combinator peuvent être élégamment mis en œuvre
```
fix :: forall t. (t -> t) -> t
fix f = f (fix f)
```
Haskell paresse normalise pour un fini avant que toutes les sous-expressions ont été évalués.
```
primes :: Integral t => [t]
primes = sieve [2 ..]
   where
      sieve = fix (\ rec (p : ns) ->
                     p : rec [n | n <- ns
                                , n `rem` p /= 0])
```
- David Turner: L'église de la Thèse et de la Programmation Fonctionnelle
- Alonzo Church: Un Problème Insoluble de l'Élémentaire de la Théorie des nombres
- Lambda calcul
- Church–Rosser le théorème de
- Même si j'apprécie la rigueur de la réponse, il n'est en aucune façon accessible à un programmeur avec peu de formation en mathématiques après le premier saut de ligne.
- La réponse est destiné à donner une complémentaire Wonkaian histoire à propos de la CS/math notions derrière le Y combinator. Je pense que, probablement, la meilleure possible, des analogies, des concepts ont été déjà établi par d'autres answerers. Personnellement, j'ai toujours aimé être confronté à la véritable origine, la nouveauté radicale d'une idée, sur une belle analogie. Je trouve les plus grandes analogies inapproprié et confuse.
- Bonjour, l'identité du combinator λ x . x, comment êtes-vous aujourd'hui?
InformationsquelleAutor
3

Un combinateur de point fixe (ou point fixe de l'opérateur) est une fonction d'ordre supérieur qui calcule un point fixe d'autres fonctions. Cette opération est pertinent dans le langage de programmation théorie car elle permet la mise en œuvre de la récursivité dans la forme d'une règle de réécriture, sans le soutien explicite de la langue du moteur d'exécution. (src Wikipedia)

InformationsquelleAutor Thomas Wagner

La ce-opérateur peut vous simplifier la vie:

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

Alors, vous évitez la fonction supplémentaire:

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

Enfin, vous appelez fac(5).

InformationsquelleAutor Tires

0

Je pense que la meilleure façon de répondre à cette est de choisir une langue, comme le 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));
    }
}
```
Maintenant réécrire afin qu'il n'utilise pas le nom de la fonction à l'intérieur de la fonction, mais encore l'appelle récursivement.

Le seul endroit où le nom de la fonction factorial doit être considéré est sur le site d'appel.

Astuce: vous ne pouvez pas utiliser des noms de fonctions, mais vous pouvez utiliser des noms de paramètres.

Travailler sur le problème. Ne pas le regarder. Une fois que vous le résoudre, vous comprendrez ce problème le y combinator en résout.
- Êtes-vous sûr qu'il ne crée plus de problèmes qu'elle n'en résout?
- Noctis, pouvez-vous préciser votre question? Demandez-vous si la notion de y combinator lui-même crée plus de problèmes qu'elle n'en résout, ou parlez-vous précisément que j'ai choisi pour illustrer l'aide de JavaScript en particulier, ou mon spécifiques de mise en œuvre ou ma recommandation de l'apprendre par la découverte de vous-même comme je l'ai décrit?
InformationsquelleAutor zumalifeguard

Vous devez vous connecter pour publier un commentaire.

Ce qui est un Y-combinator?

De de Merde à Moins Merdique

Fix -

Trois fonctions

Découlant `Y` (non inclus)

La forme de `Y`

Pourquoi ne `(Y f)` travail?

Anonyme récursivité

Lambda calcul

Combinators

Y