Bonne explication de "Combinators" (Pour les non matheux)

Question

Quelqu'un a une bonne explication de "combinators" (Y-combinators etc. et non PAS la société)

Je suis à la recherche pour l'une pour la pratique programmeur qui comprend la récursivité et les fonctions d'ordre supérieur, mais n'a pas une forte la théorie ou de la formation en mathématiques.

(Notez que je parle de ces choses : http://en.wikipedia.org/wiki/Y_combinator )

Answer 1

Reginald Braithwaite (aka Raganwald) a été écrit sur une belle série sur les combinators en Ruby sur son nouveau blog, homoiconic.

Alors qu'il n'a pas (à ma connaissance) de regarder le Y combinator lui-même, il ne regarde les autres combinators, par exemple:

• le Kestrel
• le Muguet
• le Cardinal
• les Récalcitrants Kestrel
• d'autres Oiseaux Bizarres

et un peu de posts sur comment vous pouvez utiliser eux.

Answer 2

J'ai donné ce que je pense, un très bon et relativement courte explication du Y combinator sur le Boston Perlmongers liste tout à l'heure. Les exemples de code ont été en JavaScript, mais il devrait être facile de les traduire en toute langue que vous souhaitez. Lire cela et de revenir vers moi si cette explication fonctionne pour vous.

Answer 3

Citation Wikipedia:

Un combinateur est une fonction d'ordre supérieur qui n'utilise que la fonction de demande et la définition antérieure combinators pour définir un résultat à partir de ses arguments.

Maintenant, qu'est-ce que cela signifie? Cela signifie un combinator est une fonction (sortie est déterminé uniquement par son entrée) dont l'entrée comprend une fonction comme argument.

Ce ne des fonctions, telles ressemble et à quoi servent-ils? Voici quelques exemples:

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

Ici, o est un combinateur qui prend dans les 2 fonctions , f et g, et retourne une fonction comme résultat, la composition de l' f avec g, à savoir l' f o g.

Combinators peut être utilisé pour masquer la logique. Disons que nous avons un type de données NumberUndefinedoù NumberUndefined peut prendre une valeur numérique Num x ou d'une valeur en Undefinedoù x d'un Number. Maintenant, nous voulons construire l'addition, la soustraction, la multiplication et la division pour ce nouveau type numérique. La sémantique est la même que pour ceux de l' Number sauf si Undefined est une entrée, la sortie doit également être Undefined et en divisant par le nombre 0 la sortie est également Undefined.

On pourrait écrire les codes ci-dessous:

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)

Remarquez comment l'ont tous la même logique concernant l' Undefined des valeurs d'entrée. Seule division un peu plus. La solution consiste à extraire de la logique en faisant un combinateur.

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

Ceci peut être généralisé dans le soi-disant Maybe monade que les programmeurs utilisent dans les langages fonctionnels comme Haskell, mais je ne vais pas y aller.

Answer 4

Un combinateur est fonction à n variables libres. Que signifie, entre autres choses, que le combinateur n'a pas de dépendances sur les choses de l'extérieur de la fonction, uniquement sur les paramètres de la fonction.

À l'aide de F# c'est ma compréhension de combinators:

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

Dans le cas ci-dessus, la somme est un combinateur parce que les deux a et b sont liés à des paramètres de la fonction.

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

La fonction ci-dessus n'est pas un combinator, car il utilise sum, ce qui n'est pas une variable liée (c'est à dire qu'il ne vient pas de l'un des paramètres).

Nous pouvons faire somme3 un combinateur par un simple passage de la fonction somme comme l'un des paramètres:

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

De cette façon, sumFunc est lié , et donc l'ensemble de la fonction est un combinateur.

Donc, c'est ma compréhension de combinators. Leur signification, d'autre part, toujours en m'échappe. Comme d'autres l'ont souligné, point fixe combinators permettent d'exprimer une fonction récursive sans explicit de la récursivité. I. e. au lieu d'appeler lui-même le recusrsive appels de fonction lambda qui est transmis en tant que l'un des arguments.

Ici est l'un des plus compréhensible combinator dérivations que j'ai trouvé:

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