Quand j'ai touché Haskell après avoir écrit "Représentation de base du calcul lambda utilisant l'expression Python lambda" pour diverses raisons, il a exécuté une fonction récursive anonyme. Étant donné que le combinateur de points immobile fix était ridiculement facile à écrire, j'ai essayé de voir si cela pouvait être fait dans d'autres langages de programmation de la même manière, mais c'était aussi facile, j'ai donc écrit un nouvel article sous forme de note de synthèse.
Je sais qu'il y a plus de contenus de ce type sur Qiita, les livres et le net autant que le nombre d'étoiles, mais ce genre d'histoire est dominé par les combinateurs Y (en fait, l'article original). J'espère que vous pouvez le considérer comme l'un des nombreux documents de référence pour les personnes qui s'y intéressent. Tsukkomi accueille les demandes d'édition.
Le combinateur de points d'immobilité fait référence à la fonction $ g $ pour laquelle $ f (g (f)) = g (f) $ est valable. Dans cet article, le nom de Haskell, «fix», est utilisé comme nom de fonction du combinateur de points immobile.
Haskell（GHC）
Le combinateur de points inamovibles est défini selon l'équation.
python
Prelude> fix f = f (fix f)
Les résultats de la vérification des opérations à l'aide de la fonction anonyme qui calcule le nombre de Fibonacci sont les suivants. La fonction anonyme est intentionnellement organisée.
python
Prelude> fix (\fib -> \f1 -> \f2 -> \n -> if n == 0 then f1 else fib f2 (f1+f2) (n-1)) 0 1 40
102334155
Prelude> map (fix (\fib -> \f1 -> \f2 -> \n -> if n == 0 then f1 else fib f2 (f1+f2) (n-1)) 0 1) [0..10]
[0,1,1,2,3,5,8,13,21,34,55]
Prelude> map (fix (\fib -> \f1 -> \f2 -> \n -> if n == 0 then f1 else fib f2 (f1+f2) (n-1)) 0 1) [0,10..50]
[0,55,6765,832040,102334155,12586269025]
Scheme（Gauche）
Le combinateur de points inamovibles est défini selon l'équation.
python
gosh> (define (fix f) (f (fix f)))
fix
Les résultats de la vérification des opérations à l'aide de la fonction anonyme qui calcule le nombre de Fibonacci sont les suivants. ** * Attention: Dangereux selon l'environnement d'exécution! ** **
python
gosh> ((((fix (lambda (fib) (lambda (n) (lambda (f1) (lambda (f2) (if (= n 0) f1 (((fib (- n 1)) f2) (+ f1 f2)))))))) 40) 0) 1)
;Ne s'affiche pas pour toujours → Résiliation forcée
[Effectuez d'abord l'évaluation des arguments](https://ja.wikipedia.org/wiki/%E8%A9%95%E4%BE%A1%E6%88%A6%E7%95%A5#%E5%80 En raison de la spécification de% A4% E5% 91% BC% E3% 81% B3), pour (f (fix f)), (fix f) est exécuté avant f et il tombe dans une boucle infinie. , Il semble que la mémoire a été consommée.
Puisque le même phénomène se produit dans le combinateur Y, l'expression lambda avec le deuxième argument «x», qui est l'argument original de la fonction récursive anonyme, est «(fix f)», comme dans la conversion vers le combinateur Z qui fonctionne réellement. En englobant et en créant (lambda (x) ((fix f) x)), l'exécution est différée jusqu'à ce que (fix f) soit réellement nécessaire. Notez que les arguments de Haskell ne sont pas évalués tant qu'ils ne sont pas réellement nécessaires (l'une des fonctions d'évaluation des délais), donc un tel problème ne se produit pas.
python
gosh> (define (fix f) (f (lambda (x) ((fix f) x))))
fix
Les résultats de la vérification du fonctionnement du combinateur de points d'immobilité réécrit à l'aide d'une fonction anonyme qui calcule le nombre de Fibonacci sont les suivants.
python
gosh> ((((fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (((fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) 40)
102334155
gosh> (map (((fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (((fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) (iota 11))
(0 1 1 2 3 5 8 13 21 34 55)
gosh> (map (((fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (((fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) (iota 6 0 10))
(0 55 6765 832040 102334155 12586269025)
Python（Python3，Python2） Puisqu'on sait que l'évaluation d'argument est effectuée en premier, le combinateur de points d'immobilité est défini avec le même contenu que la définition de Schéma réécrite. Il est à noter qu'il n'est pas recommandé pour PEP8 d'assigner directement une expression lambda à une variable, et la méthode de description générale consiste à renvoyer une fonction définie en interne (avec une fermeture) ** retourner une fonction **. Faites une définition.
python
>>> def fix(f):
... def ret(x):
... return fix(f)(x)
... return f(ret)
...
>>>
Les résultats de la vérification des opérations à l'aide de la fonction anonyme qui calcule le nombre de Fibonacci sont les suivants.
python
>>> fix(lambda fib: lambda f1: lambda f2: lambda n: f1 if n == 0 else fib(f2)(f1+f2)(n-1))(0)(1)(40)
102334155
>>> list(map(fix(lambda fib: lambda f1: lambda f2: lambda n: f1 if n == 0 else fib(f2)(f1+f2)(n-1))(0)(1), range(11)))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>>> list(map(fix(lambda fib: lambda f1: lambda f2: lambda n: f1 if n == 0 else fib(f2)(f1+f2)(n-1))(0)(1), range(0,51,10)))
[0, 55, 6765, 832040, 102334155, 12586269025]
Ruby（CRuby，JRuby） Ce qui suit est le résultat de la vérification de l'opération à l'aide du combinateur de points immobiles avec le même contenu que la définition de schéma réécrite et la fonction anonyme qui calcule le nombre de Fibonacci.
python
fix = -> f { f.( -> x { fix.(f).(x) }) }
p fix.(-> fib { -> f1 { -> f2 { -> n { n == 0 ? f1 : fib.(f2).(f1+f2).(n-1) } } } }).(0).(1).(40)
# => 102334155
p (0..10).map { |x| fix.(-> fib { -> f1 { -> f2 { -> n { n == 0 ? f1 : fib.(f2).(f1+f2).(n-1) } } } }).(0).(1).(x) }
# => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
p (0..50).step(10).map { |x| fix.(-> fib { -> f1 { -> f2 { -> n { n == 0 ? f1 : fib.(f2).(f1+f2).(n-1) } } } }).(0).(1).(x) }
# => [0, 55, 6765, 832040, 102334155, 12586269025]
JavaScript（Node.js） Ce qui suit est le résultat de la vérification de l'opération à l'aide du combinateur de points immobiles avec le même contenu que la définition de schéma réécrite et la fonction anonyme qui calcule le nombre de Fibonacci.
fix = f => f(x => fix(f)(x))
console.log(fix(fib => f1 => f2 => n => n == 0 ? f1 : fib(f2)(f1+f2)(n-1))(0)(1)(40))
// => 102334155
console.log([...Array(11).keys()].map(fix(fib => f1 => f2 => n=> n == 0 ? f1 : fib(f2)(f1+f2)(n-1))(0)(1)))
// => [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]
console.log([...Array(6)].map((v,k)=>k*10).map(fix(fib => f1 => f2 => n=> n == 0 ? f1 : fib(f2)(f1+f2)(n-1))(0)(1)))
// => [ 0, 55, 6765, 832040, 102334155, 12586269025 ]
Scala（Scala 2.11 + Java VM 12） Dans Scala, les arguments de fonction (bien que le mécanisme soit différent de Haskell) ne sont pas évalués tant qu'ils ne sont pas réellement nécessaires, vous devez donc simplement écrire la définition du combinateur d'immobilité tel quel, mais c'est aussi un langage fortement typé, des arguments et des valeurs de retour. Le type de doit être spécifié à l'avance. Ici, la définition avec le même contenu que la définition de schéma réécrite est effectuée, y compris la saisie. Le type est spécifié au moment de l'appel réel.
python
scala> def fix[T1, T2](f:(T1=>T2)=>(T1=>T2))(x:T1):T2=f(fix(f))(x)
fix: [T1, T2](f:(T1=>T2)=>(T1=>T2))(x:T1)T2
Les résultats de la vérification des opérations à l'aide de la fonction anonyme qui calcule le nombre de Fibonacci sont les suivants.
scala> fix[BigInt,(BigInt => (BigInt => BigInt))](fib=>f1=>f2=>n=>if(n==0)f1elsefib(f2)(f1+f2)(n-1))(0)(1)(40)
res0: BigInt = 102334155
scala> (0 to 10).map(fix[Int,(Int => (Int => Int))](fib=>f1=>f2=>n=>if(n==0)f1elsefib(f2)(f1+f2)(n-1))(0)(1))
res1: scala.collection.immutable.IndexedSeq[Int] = Vector(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55)
scala> (0 to 50 by 10).map(fix[BigInt,(BigInt => (Int => BigInt))](fib=>f1=>f2=>n=>if(n==0)f1elsefib(f2)(f1+f2)(n-1))(0)(1))
res2: scala.collection.immutable.IndexedSeq[BigInt] = Vector(0, 55, 6765, 832040, 102334155, 12586269025)
Perl（perl 5） Ce qui suit est le résultat de la vérification de l'opération à l'aide du combinateur de points immobiles avec le même contenu que la définition de schéma réécrite et la fonction anonyme qui calcule le nombre de Fibonacci.
python
sub fix {
my $f = shift;
return $f->( sub { my $x = shift; return fix($f)->($x); })
};
print fix( sub { my $fib = shift; return sub { my $o = shift; return sub { my $p = shift; return sub { my $n = shift; return $n == 0 ? $o : $fib->($p)->($o + $p)->($n - 1); }; }; }; })->(0)->(1)->(40), "\n";
# => 102334155
@r = map { fix( sub { my $fib = shift; return sub { my $o = shift; return sub { my $p = shift; return sub { my $n = shift; return $n == 0 ? $o : $fib->($p)->($o + $p)->($n - 1); }; }; }; })->(0)->(1)->($_) } (0..10);
print "@r ", "\n"; # => 0 1 1 2 3 5 8 13 21 34 55
@r = map { fix( sub { my $fib = shift; return sub { my $o = shift; return sub { my $p = shift; return sub { my $n = shift; return $n == 0 ? $o : $fib->($p)->($o + $p)->($n - 1); }; }; }; })->(0)->(1)->($_) } (0,10,20,30,40,50);
print "@r ", "\n"; # => 0 55 6765 832040 102334155 12586269025
PHP（PHP 7.3，PHP 7.4） Ce qui suit est le résultat de la vérification de l'opération à l'aide du combinateur de points immobiles avec le même contenu que la définition de schéma réécrite et la fonction anonyme qui calcule le nombre de Fibonacci. Depuis 7.4, une définition de fonction anonyme plus simple est devenue possible, elle est donc montrée avec la notation jusqu'à 7.3.
<?php
// for PHP 7.3
function fix73($f) {
return $f(function($x) use ($f) { return fix73($f)($x); });
};
echo fix73(
function($g) {
return function($f1) use ($g) {
return function($f2) use ($f1,$g) {
return function($n) use ($f2,$f1,$g) {
return $n == 0 ? $f1 : $g($f2)($f1+$f2)($n-1);
};
};
};
}
)(0)(1)(40) . PHP_EOL;
// => 102334155
foreach(array_map(
fix73(
function($g) {
return function($f1) use ($g) {
return function($f2) use ($f1,$g) {
return function($n) use ($f2,$f1,$g) {
return $n == 0 ? $f1 : $g($f2)($f1+$f2)($n-1);
};
};
};
}
)(0)(1), range(0,10)) as $v) { print($v); echo ' '; } echo "\n";
// => 0 1 1 2 3 5 8 13 21 34 55
foreach(array_map(
fix73(
function($g) {
return function($f1) use ($g) {
return function($f2) use ($f1,$g) {
return function($n) use ($f2,$f1,$g) {
return $n == 0 ? $f1 : $g($f2)($f1+$f2)($n-1);
};
};
};
}
)(0)(1), range(0,50,10)) as $v) { print($v); echo ' '; } echo "\n";
// => 0 55 6765 832040 102334155 12586269025
// for PHP 7.4
function fix74($f) { return $f( fn($x) => fix74($f)($x)); }
echo fix74(fn($g) => fn($f1) => fn($f2) => fn($n) => $n == 0 ? $f1 : $g($f2)($f1+$f2)($n-1))(0)(1)(40) . PHP_EOL;
// => 102334155
foreach(array_map(fix74(fn($g) => fn($f1) => fn($f2) => fn($n) => $n == 0 ? $f1 : $g($f2)($f1+$f2)($n-1))(0)(1), range(0,10)) as $v) { print($v); echo ' '; } echo "\n";
// => 0 1 1 2 3 5 8 13 21 34 55
foreach(array_map(fix74(fn($g) => fn($f1) => fn($f2) => fn($n) => $n == 0 ? $f1 : $g($f2)($f1+$f2)($n-1))(0)(1), range(0,50,10)) as $v) { print($v); echo ' '; } echo "\n";
// => 0 55 6765 832040 102334155 12586269025
Julia（Version 1.0.5） Ce qui suit est le résultat de la vérification de l'opération à l'aide du combinateur de points immobiles avec le même contenu que la définition de schéma réécrite et la fonction anonyme qui calcule le nombre de Fibonacci.
julia> fix(f) = f(x -> fix(f)(x))
fix (generic function with 1 method)
julia> fix(g -> f1 -> f2 -> n -> n == 0 ? f1 : g(f2)(f1+f2)(n-1))(0)(1)(40)
102334155
julia> map(fix(g -> f1 -> f2 -> n -> n == 0 ? f1 : g(f2)(f1+f2)(n-1))(0)(1), 0:10)
11-element Array{Int64,1}:
0
1
1
2
3
5
8
13
21
34
55
julia> map(fix(g -> f1 -> f2 -> n -> n == 0 ? f1 : g(f2)(f1+f2)(n-1))(0)(1), 0:10:50)
6-element Array{Int64,1}:
0
55
6765
832040
102334155
12586269025
Common Lisp（SBCL 2.0.0） Ce qui suit est le résultat de la vérification de l'opération à l'aide du combinateur de points immobiles avec le même contenu que la définition de schéma réécrite et la fonction anonyme qui calcule le nombre de Fibonacci.
* (defun fix (f) (funcall f (lambda (x) (funcall (fix f) x))))
FIX
* (funcall (funcall (funcall (fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (funcall (funcall (funcall fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) 40)
102334155
* (mapcar (funcall (funcall (fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (funcall (funcall (funcall fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) '(0 1 2 3 4 5 6 7 8 9 10))
(0 1 1 2 3 5 8 13 21 34 55)
* (mapcar (funcall (funcall (fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (funcall (funcall (funcall fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) '(0 10 20 30 40 50))
(0 55 6765 832040 102334155 12586269025)
Puisqu'elle doit avoir une portée statique, activez lexical-binding. À part cela, c'est la même chose que Common Lisp.
*** Welcome to IELM *** Type (describe-mode) for help.
ELISP> (setq lexical-binding t)
t
ELISP> (defun fix (f) (funcall f (lambda (x) (funcall (fix f) x))))
fix
ELISP> (funcall (funcall (funcall (fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (funcall (funcall (funcall fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) 40)
102334155 (#o606277313, #x6197ecb)
ELISP> (defun map (f l)
(if (null l) '()
(cons (funcall f (car l)) (map f (cdr l)))))
map
ELISP> (map (funcall (funcall (fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (funcall (funcall (funcall fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) '(0 1 2 3 4 5 6 7 8 9 10))
(0 1 1 2 3 5 8 13 21 34 55)
ELISP> (map (funcall (funcall (fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (funcall (funcall (funcall fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) '(0 10 20 30 40 50))
(0 55 6765 832040 102334155 12586269025)
Dans le langage R, les arguments de fonction ne sont pas évalués tant qu'ils ne sont pas réellement nécessaires (évaluation retardée), de sorte que la définition du combinateur de points immobile peut être décrite telle quelle.
> fix <- function(f) { f(fix(f)) }
Les résultats de la vérification des opérations à l'aide de la fonction anonyme qui calcule le nombre de Fibonacci sont les suivants.
> fix(function(fib) { function(f1) { function(f2) { function(n) { if (n == 0) f1 else fib(f2)(f1+f2)(n-1) } } } })(0)(1)(40)
[1] 102334155
> Map(fix(function(fib) { function(f1) { function(f2) { function(n) { if (n == 0) f1 else fib(f2)(f1+f2)(n-1) } } } })(0)(1), list(0,1,2,3,4,5,6,7,8,9,10))
[[1]]
[1] 0
[[2]]
[1] 1
[[3]]
[1] 1
[[4]]
[1] 2
[[5]]
[1] 3
[[6]]
[1] 5
[[7]]
[1] 8
[[8]]
[1] 13
[[9]]
[1] 21
[[10]]
[1] 34
[[11]]
[1] 55
> Map(fix(function(fib) { function(f1) { function(f2) { function(n) { if (n == 0) f1 else fib(f2)(f1+f2)(n-1) } } } })(0)(1), list(0,10,20,30,40,50))
[[1]]
[1] 0
[[2]]
[1] 55
[[3]]
[1] 6765
[[4]]
[1] 832040
[[5]]
[1] 102334155
[[6]]
[1] 12586269025
"Fonction anonyme" dans la programmation est une fonction. Fait référence à une définition de fonction qui n'a que des arguments sans nom. Puisqu'il n'est pas nécessaire d'utiliser la syntaxe de définition de fonction, il est possible de recevoir la définition de fonction comme argument "[Fonction d'ordre supérieur](https://ja.wikipedia.org/wiki/%E9%AB%98%E9%9A%8E%E9%96] Il est souvent utilisé pour ajouter un petit processus arbitraire à "% A2% E6% 95% B0)". Les fonctions d'ordre supérieur incluent celles qui peuvent renvoyer la définition de fonction en tant que valeur de retour.
Le plus gros inconvénient des fonctions anonymes est qu'elles définissent une "fonction récursive" car il n'y a pas de nom de fonction. Pour ce faire et pour le faire, il faut une méthode spéciale. En tant que méthode, préparez une fonction d'ordre supérieur distincte qui vous permet de vous appeler avec le nom de votre argument, ou autorisez l'environnement d'exécution à se souvenir automatiquement de l'emplacement de la fonction anonyme et à s'appeler avec un nom spécial. Il y a quelque chose (Wikipedia "Anonymous Recurrence" référence).
Dans cet article, en tant que fonction d'ordre supérieur pour la récurrence anonyme, "[Fudo Point Combinator](https://ja.wikipedia.org/wiki/%E4%B8%8D%E5%8B%95%E7%82%B9%" E3% 82% B3% E3% 83% B3% E3% 83% 93% E3% 83% 8D% E3% 83% BC% E3% 82% BF) »se concentre sur la définition. Il existe diverses fonctions dans le combinateur de points d'immobilité, et la plus célèbre est souvent représentée comme une fonction anonyme combinateur Y. % E5% 8B% 95% E7% 82% B9% E3% 82% B3% E3% 83% B3% E3% 83% 93% E3% 83% 8D% E3% 83% BC% E3% 82% BF # Y % E3% 82% B3% E3% 83% B3% E3% 83% 93% E3% 83% 8D% E3% 83% BC% E3% 82% BF). Cet article décrit un combinateur de points inamovible qui peut être défini sans accorder une attention particulière au combinateur Y. Ce qui suit est un exemple de la description du combinateur Z en Python, qui rend le combinateur Y disponible dans le langage de pré-évaluation des arguments.
print(
(lambda f:
(lambda x: f(lambda y: x(x)(y)))
(lambda x: f(lambda y: x(x)(y)))
)
(lambda fib: lambda f1: lambda f2: lambda n:
f1 if n == 0 else fib(f2)(f1+f2)(n-1)
)(0)(1)(40)
)
# => 102334155
En ce qui concerne l'exécution d'une fonction anonyme par le combinateur de points d'immobilité, le premier argument de la fonction anonyme est le nom de la fonction anonyme elle-même pour appeler la fonction anonyme elle-même, et le deuxième argument est l'argument original requis par la fonction anonyme. Puisqu'un seul argument original est supposé, dans cet exemple d'exécution, la fonction anonyme est manuellement "[curry](https://ja.wikipedia.org/wiki/%] en utilisant la fonction de la fonction d'ordre supérieur. E3% 82% AB% E3% 83% AA% E3% 83% BC% E5% 8C% 96) », et après avoir rendu possible l'appel de plusieurs arguments avec une seule spécification d'argument, ajustez l'ordre d'application des arguments. Et une description plus simple est faite. * Référence: "Aide-mémoire Curry"
fixer