Als ich Haskell aus verschiedenen Gründen berührte, nachdem ich "Grundlegende Darstellung der Lambda-Berechnung mit Python-Lambda-Ausdruck" geschrieben hatte, wurde eine anonyme rekursive Funktion ausgeführt. Da der unbewegliche Punktkombinator fix lächerlich einfach zu schreiben war, habe ich versucht zu prüfen, ob er in anderen Programmiersprachen auf die gleiche Weise ausgeführt werden kann, aber es war auch einfach, also habe ich einen neuen Artikel als zusammenfassendes Memo geschrieben.
Ich weiß, dass es auf Qiita, Büchern und im Netz mehr solcher Inhalte gibt als die Anzahl der Sterne, aber diese Art von Geschichte wird von Y-Kombinatoren dominiert (tatsächlich der Originalartikel). Ich hoffe, Sie können es sich als eines der vielen Referenzmaterialien von Menschen vorstellen, die daran interessiert sind. Tsukkomi freut sich über Bearbeitungsanfragen.
Der Immobilitätspunktkombinator bezieht sich auf die Funktion $ g $, für die $ f (g (f)) = g (f) $ gilt. In diesem Artikel wird Haskells Name "fix" als Funktionsname des Kombinators für unbewegliche Punkte verwendet.
Haskell（GHC）
Der unbewegliche Punktkombinator wird gemäß der Gleichung definiert.
python
Prelude> fix f = f (fix f)
Die Ergebnisse der Operationsprüfung unter Verwendung der anonymen Funktion, die die Fibonacci-Zahl berechnet, sind wie folgt. Die anonyme Funktion wird absichtlich kuratiert.
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）
Der unbewegliche Punktkombinator wird gemäß der Gleichung definiert.
python
gosh> (define (fix f) (f (fix f)))
fix
Die Ergebnisse der Operationsprüfung unter Verwendung der anonymen Funktion, die die Fibonacci-Zahl berechnet, sind wie folgt. ** * Achtung: Je nach Ausführungsumgebung gefährlich! ** **.
python
gosh> ((((fix (lambda (fib) (lambda (n) (lambda (f1) (lambda (f2) (if (= n 0) f1 (((fib (- n 1)) f2) (+ f1 f2)))))))) 40) 0) 1)
;Nicht für immer angezeigt → Zwangsbeendigung
[Führen Sie zuerst eine Argumentbewertung durch](https://ja.wikipedia.org/wiki/%E8%A9%95%E4%BE%A1%E6%88%A6%E7%95%A5#%E5%80 Aufgrund der Angabe von% A4% E5% 91% BC% E3% 81% B3) wird für "(f (Fix f))" (Fix f) "vor" f "ausgeführt und fällt in eine Endlosschleife. Es scheint, dass der Speicher verbraucht wurde.
Da im Y-Kombinator das gleiche Phänomen auftritt, ist der Lambda-Ausdruck mit dem zweiten Argument "x", das das ursprüngliche Argument der anonymen rekursiven Funktion ist, "(fix f)" wie bei der Konvertierung in den tatsächlich arbeitenden Z-Kombinator. Durch Einschließen und Erstellen von "(Lambda (x) ((Fix f) x))" wird die Ausführung verschoben, bis "(Fix f)" tatsächlich benötigt wird. Beachten Sie, dass die Argumente von Haskell erst ausgewertet werden, wenn sie tatsächlich benötigt werden (eine der Verzögerungsauswertungsfunktionen), sodass ein solches Problem nicht auftritt.
python
gosh> (define (fix f) (f (lambda (x) ((fix f) x))))
fix
Die Ergebnisse der Überprüfung des Betriebs des umgeschriebenen Kombinators für Immobilitätspunkte unter Verwendung einer anonymen Funktion, die die Fibonacci-Zahl berechnet, sind wie folgt.
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） Da bekannt ist, dass die Argumentbewertung zuerst durchgeführt wird, wird der Kombinator für Immobilitätspunkte mit demselben Inhalt wie die umgeschriebene Schemadefinition definiert. Es sollte beachtet werden, dass es für PEP8 nicht empfohlen wird, einer Variablen direkt einen Lambda-Ausdruck zuzuweisen, und die allgemeine Beschreibungsmethode besteht darin, eine intern definierte Funktion (mit einem Abschluss) zurückzugeben ** eine Funktion zurückzugeben **. Machen Sie eine Definition.
python
>>> def fix(f):
... def ret(x):
... return fix(f)(x)
... return f(ret)
...
>>>
Die Ergebnisse der Betriebsbestätigung unter Verwendung einer anonymen Funktion, die die Fibonacci-Zahl berechnet, sind wie folgt.
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） Das Folgende ist das Ergebnis der Überprüfung der Operation unter Verwendung des Kombinators für unbewegliche Punkte mit demselben Inhalt wie die neu geschriebene Schemadefinition und der anonymen Funktion, die die Fibonacci-Zahl berechnet.
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） Das Folgende ist das Ergebnis der Überprüfung der Operation unter Verwendung des Kombinators für unbewegliche Punkte mit demselben Inhalt wie die neu geschriebene Schemadefinition und der anonymen Funktion, die die Fibonacci-Zahl berechnet.
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） In Scala werden Funktionsargumente (obwohl sich der Mechanismus von Haskell unterscheidet) erst ausgewertet, wenn sie tatsächlich benötigt werden. Schreiben Sie daher einfach die Definition des Immobilitätskombinators so wie er ist, aber es handelt sich auch um eine stark typisierte Sprache sowie die Argumente und Rückgabewerte Der Typ von muss im Voraus angegeben werden. Hier wird die Definition mit demselben Inhalt wie die neu geschriebene Schemadefinition einschließlich der Eingabe durchgeführt. Der Typ wird zum Zeitpunkt des tatsächlichen Anrufs angegeben.
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
Die Ergebnisse der Betriebsbestätigung unter Verwendung einer anonymen Funktion, die die Fibonacci-Zahl berechnet, sind wie folgt.
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） Das Folgende ist das Ergebnis der Überprüfung der Operation unter Verwendung des Kombinators für unbewegliche Punkte mit demselben Inhalt wie die neu geschriebene Schemadefinition und der anonymen Funktion, die die Fibonacci-Zahl berechnet.
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） Das Folgende ist das Ergebnis der Überprüfung der Operation unter Verwendung des Kombinators für unbewegliche Punkte mit demselben Inhalt wie die neu geschriebene Schemadefinition und der anonymen Funktion, die die Fibonacci-Zahl berechnet. Seit 7.4 ist eine einfachere anonyme Funktionsdefinition möglich geworden, die zusammen mit der Notation bis 7.3 angezeigt wird.
<?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） Das Folgende ist das Ergebnis der Überprüfung der Operation unter Verwendung des Kombinators für unbewegliche Punkte mit demselben Inhalt wie die neu geschriebene Schemadefinition und der anonymen Funktion, die die Fibonacci-Zahl berechnet.
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） Das Folgende ist das Ergebnis der Überprüfung der Operation unter Verwendung des Kombinators für unbewegliche Punkte mit demselben Inhalt wie die neu geschriebene Schemadefinition und der anonymen Funktion, die die Fibonacci-Zahl berechnet.
* (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)
Da ein statischer Bereich erforderlich ist, aktivieren Sie "lexikalische Bindung". Davon abgesehen ist es dasselbe wie 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)
In der R-Sprache werden Funktionsargumente erst ausgewertet, wenn sie tatsächlich benötigt werden (verzögerte Auswertung), sodass die Definition des Kombinators für unbewegliche Punkte so beschrieben werden kann, wie sie ist.
> fix <- function(f) { f(fix(f)) }
Die Ergebnisse der Operationsprüfung unter Verwendung der anonymen Funktion, die die Fibonacci-Zahl berechnet, sind wie folgt.
> 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
"Anonyme Funktion" in der Programmierung ist eine Funktion. Bezieht sich auf eine Funktionsdefinition, die nur Argumente ohne Namen enthält. Da die Funktionsdefinitionssyntax nicht verwendet werden muss, kann die Funktionsdefinition als Argument "[Funktion höherer Ordnung](https://ja.wikipedia.org/wiki/%E9%AB%98%E9%9A%8E%E9%96] empfangen werden. Es wird oft verwendet, um "% A2% E6% 95% B0)" einen kleinen willkürlichen Prozess hinzuzufügen. Zu Funktionen höherer Ordnung gehören Funktionen, die die Funktionsdefinition als Rückgabewert zurückgeben können.
Der größte Nachteil anonymer Funktionen besteht darin, dass sie eine Funktion "rekursiv" definieren, da kein Funktionsname vorhanden ist. Sowohl dafür als auch dafür ist eine spezielle Methode erforderlich. Bereiten Sie als Methode eine separate Funktion höherer Ordnung vor, mit der Sie sich mit dem Namen Ihres Arguments aufrufen können, oder ermöglichen Sie der Ausführungsumgebung, sich automatisch den Speicherort der anonymen Funktion zu merken und sich selbst mit einem speziellen Namen aufzurufen. Es gibt etwas (Wikipedia "Anonyme Wiederholung" Referenz).
In diesem Artikel wird als Funktion höherer Ordnung für anonyme Wiederholungen "[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) “konzentriert sich auf die Definition. Es gibt verschiedene Funktionen im Kombinator für Immobilitätspunkte, und die bekannteste wird häufig als anonyme Funktion [Y-Kombinator] angezeigt (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 # Y. % E3% 82% B3% E3% 83% B3% E3% 83% 93% E3% 83% 8D% E3% 83% BC% E3% 82% BF). Dieser Artikel beschreibt einen unbeweglichen Punktkombinator, der definiert werden kann, ohne dem Y-Kombinator besondere Aufmerksamkeit zu schenken. Das Folgende ist ein Beispiel für die Beschreibung des Z-Kombinators in Python, wodurch der Y-Kombinator in der Sprache der Argumentvorbewertung verfügbar gemacht wird.
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
In Bezug auf die Ausführung einer anonymen Funktion durch den Immobilitätspunktkombinator ist das erste Argument der anonymen Funktion der Name für die anonyme Funktion selbst, um die anonyme Funktion selbst aufzurufen, und das zweite Argument ist das ursprüngliche Argument, das von der anonymen Funktion benötigt wird. Da in diesem Ausführungsbeispiel nur ein ursprüngliches Argument angenommen wird, wird die anonyme Funktion manuell "[curried](https://ja.wikipedia.org/wiki/%]" unter Verwendung der Funktion der Funktion höherer Ordnung verwendet. E3% 82% AB% E3% 83% AA% E3% 83% BC% E5% 8C% 96) “und nachdem Sie mehrere Argumente mit nur einer Argumentspezifikation aufgerufen haben, passen Sie die Anwendungsreihenfolge der Argumente an. Und eine einfachere Beschreibung wird gemacht. * Referenz: "Curry-Spickzettel"