Rosetta Stone: combinateur Y

Question

Le Y combinator est défini comme:

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

L'utilisation de ce combinator, vous pouvez écrire récursive lambda fonctions ou d'intercepter les méthodes récursives avec un code personnalisé.

Comment est le Y combinator écrits dans des langues différentes?

Je serais curieux de voir le Y combinator définis et utilisés pour mettre en œuvre une fonction factorielle récursive. Par exemple, en F#:

let rec y f x = f (y f) x
let factorial = y (fun f -> function 0 -> 1 | n -> n * f(n - 1))

Essayez de limiter vos réponses à une langue, une seule réponse.

Answer 1

PostScript

Le Y combinator comme un nom de fonction avec pas explicite des variables liaisons (pressé pour tenir sur une seule ligne :D):

{[{[exch{dup exec exec}aload pop]cvx exec}aload pop 10 9 roll exch]cvx dup exec}

En fait, c'est l'applicatif ordre de Y combinator, adapté de Régime.

Comme exemple, voici comment l'utiliser pour calculer la factorielle d'un nombre entier non négatif:

%%% Read from stdin (input should be a nonnegative integer)
(%stdin) run

%%% Factorializer -- a function that takes a function as input;
%%% this computes the factorial by doing everything except the recursive step
%%% and then calling the input function as the recursive step
{[{dup 0 eq exch {1} exch [exch dup 1 sub exec mul} aload pop
[6 1 roll 16 15 roll 3 1 roll] cvx {aload pop] cvx ifelse} aload pop] cvx}

%%% Y combinator -- takes the factorializer as input and returns a function that
%%% computes the factorial of any nonnegative integer
{[{[exch {dup exec exec} aload pop] cvx exec} aload pop 10 9 roll exch]
cvx dup exec}

%%% Apply Y combinator to factorializer to produce factorial function;
%%% then apply factorial function to input number and print the result
exec exec =

Utilisation: $ echo 20 | gs -q -dNODISPLAY -dNOPROMPT -dBATCH thisfile.ps

Sortie: 2432902008176640000

Pas de itératif de boucles, pas de noms de fonctions, pas même variable locale liaisons.*

PostScript est l'ultime langage de programmation fonctionnel.

*Vous pouvez également utiliser l'un de ces PostScript, mais ce nameless version est vraiment cool.

Answer 2

Haskell

 y f = f (y f)
 

Avec type

 y :: (a -> a) -> a
 

Usage:

 fact = y (\f n -> if n <= 1 then 1 else n * f (n - 1))
 

Answer 3

Voici un combinateur Y à argument unique en C #:

 public static Func<T, U> YCombinator<T, U>(Func<Func<T, U>, Func<T, U>> f) {
  return yc => x => f(yc(yc)(f))(x);
}
 

Votre exemple factoriel ressemblerait à ceci:

 Func<Func<int, int>, Func<int, int>> factorial =
  (inject) => (x) => x == 0 ? 1 : x * inject(x - 1);
 

---

Ce n'est pas le seul moyen de le faire, bien sûr. Voici un exemple beaucoup plus complet.

Answer 4

Version R basée sur The Little Schemer :

 Y <- function (fun) (function (f) f(f))(function (f) fun(function (x) f(f)(x)))
 

Exemple rapide:

 factorial <- function (fun) (function (x) if (x < 2) 1 else x * fun(x - 1))
Y(factorial)(5)    # should return 120
 

Answer 5

Version Ruby basée sur ma version R:

 def Y
  lambda {|f| f.call(f)}.call(lambda {|f| yield lambda {|x| f.call(f).call(x)}})
end
 

Exemple:

 def factorial
  lambda {|x| x < 2 ? 1 : x * yield(x - 1)}
end

Y {|f| factorial &f}.call(5)    # should return 120