Ich war ein bisschen verwirrt von der Dokumentation für fix
(obwohl ich glaube zu verstehen, was es jetzt tun soll), also habe ich mir den Quellcode angesehen. Das hat mich verwirrter gemacht:
fix :: (a -> a) -> a
fix f = let x = f x in x
Wie genau gibt dies einen Fixpunkt zurück?
Ich habe beschlossen, es an der Kommandozeile auszuprobieren:
Prelude Data.Function> fix id
...
Und es hängt dort. Nun, um fair zu sein, das ist auf meinem alten Macbook, das ziemlich langsam ist. Diese Funktion kann jedoch nicht zu rechenintensiv sein, da alles, was an id übergeben wird, dasselbe zurückgibt (ganz zu schweigen davon, dass es keine CPU-Zeit verbraucht). Was mache ich falsch?
haskell
fixpoint-combinators
letrec
Jason Baker
quelle
quelle
fix error
ghci eingeben und sich gut fühlen können."fix
alsfix f = f (fix f)
. Kurz, einfach, funktioniert und ist identisch mit der mathematischen Definition.fix (1:) !! (10^8)
. Das Original macht es in konstantem Speicher, Ihr Original nimmt linearen Speicher (was es auch ein bisschen langsamer macht). Das heißt, die Verwendung von let "bindet einen engeren Knoten" und ermöglicht die Erzeugung einer kreisförmigen Datenstruktur, während Ihre dies nicht tut.fix
! hat mirfix
sehr geholfen zu verstehen .Antworten:
Du machst nichts falsch.
fix id
ist eine Endlosschleife.Wenn wir sagen, dass dies
fix
den kleinsten Fixpunkt einer Funktion zurückgibt, meinen wir dies im Sinne der Domänentheorie . Wirdfix (\x -> 2*x-1)
also nicht zurückkehren1
, denn obwohl dies1
ein fester Punkt dieser Funktion ist, ist es nicht der geringste in der Domänenreihenfolge.Ich kann die Domain-Reihenfolge nicht in ein oder zwei Absätzen beschreiben, daher verweise ich Sie auf den obigen Link zur Domänentheorie. Es ist ein ausgezeichnetes Tutorial, leicht zu lesen und sehr aufschlussreich. Ich empfehle es sehr.
Für die Ansicht aus 10.000 Fuß
fix
ist eine Funktion höherer Ordnung, die die Idee der Rekursion codiert . Wenn Sie den Ausdruck haben:Was zu der unendlichen Liste führt
[1,1..]
, könnte man mit folgenden Worten sagenfix
:(Oder einfach
fix (1:)
), was besagt, finde mich einen festen Punkt der(1:)
Funktion, IOW einen Wertx
, derx = 1:x
... genau wie wir oben definiert haben. Wie Sie aus der Definition sehen können,fix
ist nichts weiter als diese Idee - Rekursion in einer Funktion gekapselt.Es ist auch ein wirklich allgemeines Konzept der Rekursion - Sie können auf diese Weise jede rekursive Funktion schreiben, einschließlich Funktionen, die polymorphe Rekursion verwenden . So zum Beispiel die typische Fibonacci-Funktion:
Kann folgendermaßen geschrieben werden
fix
:Übung: Erweitern Sie die Definition von, um
fix
zu zeigen, dass diese beiden Definitionen vonfib
äquivalent sind.Lesen Sie zum besseren Verständnis die Domänentheorie. Es ist wirklich cooles Zeug.
quelle
fix id
:fix
Nimmt eine Funktion vom Typa -> a
und gibt einen Wert vom Typ zurücka
. Daid
es für jeden polymorph ista
,fix id
hat es den Typa
, dh jeden möglichen Wert. In Haskell ist der einzige Wert, der ein beliebiger Typ sein kann, der untere Wert ⊥ und nicht von einer nicht terminierenden Berechnung zu unterscheiden. Sofix id
entsteht genau das, was es soll, der unterste Wert. Die Gefahrfix
besteht darin, dass wenn ⊥ ein fester Punkt Ihrer Funktion ist, es per Definition der am wenigsten feste Punkt ist und daherfix
nicht endet.undefined
ist auch ein Wert von jedem Typ. Sie können definierenfix
als :fix f = foldr (\_ -> f) undefined (repeat undefined)
._Y f = f (_Y f)
.Ich behaupte nicht, das überhaupt zu verstehen, aber wenn das jemandem hilft ... dann yippee.
Betrachten Sie die Definition von
fix
.fix f = let x = f x in x
. Der umwerfende Teil ist der, derx
definiert ist alsf x
. Aber denken Sie eine Minute darüber nach.Da x = fx, können wir den Wert von
x
auf der rechten Seite ersetzen , richtig? Also deshalb...Der Trick besteht also darin, zum Beenden
f
eine Art Struktur zu generieren, damit ein späteresf
Muster mit dieser Struktur übereinstimmen und die Rekursion beenden kann, ohne sich tatsächlich um den vollen "Wert" seines Parameters (?) Zu kümmern.Es sei denn, Sie möchten natürlich so etwas wie eine unendliche Liste erstellen, wie Luqui illustriert.
Die faktorielle Erklärung von TomMD ist gut. Die Typensignatur von Fix lautet
(a -> a) -> a
. Die Typensignatur für(\recurse d -> if d > 0 then d * (recurse (d-1)) else 1)
ist(b -> b) -> b -> b
mit anderen Worten ,(b -> b) -> (b -> b)
. Das können wir also sagena = (b -> b)
. Auf diese Weise übernimmt fix unsere Funktion, diea -> a
oder wirklich ist(b -> b) -> (b -> b)
, und gibt ein Ergebnis vom Typ zurücka
, mit anderen Worten,b -> b
mit anderen Worten, eine andere Funktion!Warten Sie, ich dachte, es sollte einen festen Punkt zurückgeben ... keine Funktion. Nun, irgendwie (da Funktionen Daten sind). Sie können sich vorstellen, dass es uns die endgültige Funktion gab, eine Fakultät zu finden. Wir haben ihm eine Funktion gegeben, die nicht weiß, wie man rekursiv arbeitet (daher ist einer der Parameter eine Funktion, die zum Rekursieren verwendet wird), und haben ihm
fix
beigebracht, wie man rekursiv arbeitet.Erinnern Sie sich, wie ich sagte,
f
dass eine Art Struktur erzeugt werden muss, damit ein späteresf
Muster übereinstimmen und enden kann? Nun, das ist nicht genau richtig, denke ich. TomMD hat gezeigt, wie wir erweitern können,x
um die Funktion anzuwenden und zum Basisfall zu gelangen. Für seine Funktion verwendete er ein Wenn / Dann, und das ist die Ursache für die Beendigung. Nach wiederholten Ersetzungen wird derin
Teil der gesamten Definition vonfix
schließlich nicht mehr in Bezug auf definiert,x
und dann ist er berechenbar und vollständig.quelle
Sie benötigen eine Möglichkeit, den Fixpunkt zu beenden. Wenn Sie Ihr Beispiel erweitern, ist es offensichtlich, dass es nicht fertig wird:
Hier ist ein echtes Beispiel für die Verwendung von Fix (Hinweis: Ich verwende Fix nicht oft und war wahrscheinlich müde / machte mir keine Sorgen um lesbaren Code, als ich dies schrieb):
WTF, sagst du! Ja, aber hier gibt es einige wirklich nützliche Punkte. Zunächst sollte Ihr erstes
fix
Argument normalerweise eine Funktion sein, bei der es sich um den "Rückfall" handelt, und das zweite Argument sind die Daten, auf die reagiert werden soll. Hier ist der gleiche Code wie bei einer benannten Funktion:Wenn Sie immer noch verwirrt sind, ist Fakultät möglicherweise ein einfacheres Beispiel:
Beachten Sie die Bewertung:
Oh, hast du das gerade gesehen? Das
x
wurde eine Funktion in unsererthen
Branche.Oben müssen Sie sich erinnern
x = f x
, daher die beiden Argumentex 2
am Ende statt nur2
.Und ich werde hier aufhören!
quelle
fix
mir tatsächlich Sinn gemacht. Meine Antwort hängt weitgehend davon ab, was Sie bereits gesagt haben.id x
reduziert sich nur aufx
(was sich dann wieder auf reduziertid x
). -fact
Wenn dann im zweiten Sample ( ) derx
Thunk zum ersten Mal gezwungen wird, wird der resultierende Wert gespeichert und wiederverwendet. Die Neuberechnung von(\recurse ...) x
würde mit einer Nicht-Sharing- Definition erfolgeny g = g (y g)
, nicht mit dieser Sharing-fix
Definition. - Ich habe die Testversion hier bearbeitet - Sie können sie gerne verwenden, oder ich kann die Bearbeitung vornehmen, wenn Sie zustimmen.fix id
reduziert wird, wirdlet x = id x in x
auch der Wert der Anwendungid x
innerhalb deslet
Rahmens (Thunk) erzwungen, sodass er auf reduziert wirdlet x = x in x
, und dies führt zu Schleifen. Schaut so aus.fix
und Y ist in Haskell sehr klar und wichtig. Ich sehe nicht, was gut ist, wenn die falsche Reduktionsreihenfolge angezeigt wird, wenn die richtige noch kürzer, viel klarer und leichter zu befolgen ist und richtig widerspiegelt, was tatsächlich vor sich geht.So wie ich es verstehe, findet es einen Wert für die Funktion, so dass es dasselbe ausgibt, was Sie ihm geben. Der Haken ist, es wird immer undefiniert gewählt (oder eine Endlosschleife, in haskell sind undefinierte und unendliche Schleifen gleich) oder was auch immer die undefiniertesten enthält. Zum Beispiel mit id,
Wie Sie sehen können, ist undefiniert ein fester Punkt
fix
. Wenn Sie dies stattdessen tun (\ x-> 1: x).So
fix
kann nicht undefiniert holen. Um es ein bisschen mehr mit Endlosschleifen zu verbinden.Wieder ein kleiner Unterschied. Was ist der Fixpunkt? Lass es uns versuchen
repeat 1
.Es ist das Gleiche! Da dies der einzige Fixpunkt ist,
fix
muss man sich darauf festlegen. Sorryfix
, keine Endlosschleifen oder undefiniert für dich.quelle