Wie verwende ich fix und wie funktioniert es?

86

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?

Jason Baker
quelle
68
Die Streichantwort lautet: "Fix hat keinen wirklichen Nutzen, es ist nur da, damit Sie fix errorghci eingeben und sich gut fühlen können."
Thomas M. DuBuisson
3
@ TomMD - Lustig. Ich werde mich daran erinnern, wenn mich jemals jemand fragt, was das Problem bewirkt und ich mich ornery fühle. :-)
Jason Baker
2
Ich schreibe normalerweise fixals fix f = f (fix f). Kurz, einfach, funktioniert und ist identisch mit der mathematischen Definition.
Newacct
20
@newacct, ja, so denke ich auch darüber. Aber der hier kann zu effizienteren Strukturen führen. Sie können den Unterschied sehen, wenn Sie beispielsweise bewerten 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.
Luqui
22
Du hättest es auch neu erfinden können fix! hat mir fixsehr geholfen zu verstehen .
Fredoverflow

Antworten:

88

Du machst nichts falsch. fix idist eine Endlosschleife.

Wenn wir sagen, dass dies fixden kleinsten Fixpunkt einer Funktion zurückgibt, meinen wir dies im Sinne der Domänentheorie . Wird fix (\x -> 2*x-1)also nicht zurückkehren 1, denn obwohl dies 1ein 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ß fixist eine Funktion höherer Ordnung, die die Idee der Rekursion codiert . Wenn Sie den Ausdruck haben:

let x = 1:x in x

Was zu der unendlichen Liste führt [1,1..], könnte man mit folgenden Worten sagen fix:

fix (\x -> 1:x)

(Oder einfach fix (1:)), was besagt, finde mich einen festen Punkt der (1:)Funktion, IOW einen Wert x, der x = 1:x... genau wie wir oben definiert haben. Wie Sie aus der Definition sehen können, fixist 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:

fib n = if n < 2 then n else fib (n-1) + fib (n-2)

Kann folgendermaßen geschrieben werden fix:

fib = fix (\f -> \n -> if n < 2 then n else f (n-1) + f (n-2))

Übung: Erweitern Sie die Definition von, um fixzu zeigen, dass diese beiden Definitionen von fibäquivalent sind.

Lesen Sie zum besseren Verständnis die Domänentheorie. Es ist wirklich cooles Zeug.

luqui
quelle
32
Hier ist eine verwandte Denkweise fix id: fixNimmt eine Funktion vom Typ a -> aund gibt einen Wert vom Typ zurück a. Da ides für jeden polymorph ist a, fix idhat es den Typ a, 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. So fix identsteht genau das, was es soll, der unterste Wert. Die Gefahr fixbesteht darin, dass wenn ⊥ ein fester Punkt Ihrer Funktion ist, es per Definition der am wenigsten feste Punkt ist und daher fixnicht endet.
John L
4
@JohnL in Haskell undefinedist auch ein Wert von jedem Typ. Sie können definieren fixals : fix f = foldr (\_ -> f) undefined (repeat undefined).
Didest
1
@Diego Ihr Code entspricht _Y f = f (_Y f).
Will Ness
23

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, der xdefiniert ist als f x. Aber denken Sie eine Minute darüber nach.

x = f x

Da x = fx, können wir den Wert von xauf der rechten Seite ersetzen , richtig? Also deshalb...

x = f . f $ x -- or x = f (f x)
x = f . f . f $ x -- or x = f (f (f x))
x = f . f . f . f . f . f . f . f . f . f . f $ x -- etc.

Der Trick besteht also darin, zum Beenden feine Art Struktur zu generieren, damit ein späteres fMuster 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 -> bmit anderen Worten , (b -> b) -> (b -> b). Das können wir also sagen a = (b -> b). Auf diese Weise übernimmt fix unsere Funktion, die a -> aoder wirklich ist (b -> b) -> (b -> b), und gibt ein Ergebnis vom Typ zurück a, mit anderen Worten, b -> bmit 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 fixbeigebracht, wie man rekursiv arbeitet.

Erinnern Sie sich, wie ich sagte, fdass eine Art Struktur erzeugt werden muss, damit ein späteres fMuster übereinstimmen und enden kann? Nun, das ist nicht genau richtig, denke ich. TomMD hat gezeigt, wie wir erweitern können, xum 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 der inTeil der gesamten Definition von fixschließlich nicht mehr in Bezug auf definiert, xund dann ist er berechenbar und vollständig.

Dan Burton
quelle
Vielen Dank. Dies ist eine sehr nützliche und praktische Erklärung.
Kizzx2
16

Sie benötigen eine Möglichkeit, den Fixpunkt zu beenden. Wenn Sie Ihr Beispiel erweitern, ist es offensichtlich, dass es nicht fertig wird:

fix id
--> let x = id x in x
--> id x
--> id (id x)
--> id (id (id x))
--> ...

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):

(fix (\f h -> if (pred h) then f (mutate h) else h)) q

WTF, sagst du! Ja, aber hier gibt es einige wirklich nützliche Punkte. Zunächst sollte Ihr erstes fixArgument 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:

getQ h
      | pred h = getQ (mutate h)
      | otherwise = h

Wenn Sie immer noch verwirrt sind, ist Fakultät möglicherweise ein einfacheres Beispiel:

fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 5 -->* 120

Beachten Sie die Bewertung:

fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 3 -->
let x = (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x in x 3 -->
let x = ... in (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 3 -->
let x = ... in (\d -> if d > 0 then d * (x (d-1)) else 1) 3

Oh, hast du das gerade gesehen? Das xwurde eine Funktion in unserer thenBranche.

let x = ... in if 3 > 0 then 3 * (x (3 - 1)) else 1) -->
let x = ... in 3 * x 2 -->
let x = ... in 3 * (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 2 -->

Oben müssen Sie sich erinnern x = f x, daher die beiden Argumente x 2am Ende statt nur 2.

let x = ... in 3 * (\d -> if d > 0 then d * (x (d-1)) else 1) 2 -->

Und ich werde hier aufhören!

Thomas M. DuBuisson
quelle
Ihre Antwort hat fixmir tatsächlich Sinn gemacht. Meine Antwort hängt weitgehend davon ab, was Sie bereits gesagt haben.
Dan Burton
@Thomas beide Reduktionssequenzen sind falsch. :) id xreduziert sich nur auf x(was sich dann wieder auf reduziert id x). - factWenn dann im zweiten Sample ( ) der xThunk zum ersten Mal gezwungen wird, wird der resultierende Wert gespeichert und wiederverwendet. Die Neuberechnung von (\recurse ...) xwürde mit einer Nicht-Sharing- Definition erfolgen y 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.
Will Ness
Wenn er fix idreduziert wird, wird let x = id x in xauch der Wert der Anwendung id xinnerhalb des letRahmens (Thunk) erzwungen, sodass er auf reduziert wird let x = x in x, und dies führt zu Schleifen. Schaut so aus.
Will Ness
Richtig. Meine Antwort verwendet gleiches Denken. Das Zeigen der Reduktion a la Haskell, die sich mit der Bewertungsreihenfolge befasst, dient nur dazu, das Beispiel ohne echten Gewinn zu verwirren.
Thomas M. DuBuisson
1
Die Frage ist sowohl mit haskell als auch mit letrec gekennzeichnet (dh mit rekursivem let mit Teilen). Die Unterscheidung zwischen fixund 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.
Will Ness
2

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,

λ <*Main Data.Function>: id undefined
*** Exception: Prelude.undefined

Wie Sie sehen können, ist undefiniert ein fester Punkt fix. Wenn Sie dies stattdessen tun (\ x-> 1: x).

λ <*Main Data.Function>: undefined
*** Exception: Prelude.undefined
λ <*Main Data.Function>: (\x->1:x) undefined
[1*** Exception: Prelude.undefined

So fixkann nicht undefiniert holen. Um es ein bisschen mehr mit Endlosschleifen zu verbinden.

λ <*Main Data.Function>: let y=y in y
^CInterrupted.
λ <*Main Data.Function>: (\x->1:x) (let y=y in y)
[1^CInterrupted.

Wieder ein kleiner Unterschied. Was ist der Fixpunkt? Lass es uns versuchen repeat 1.

λ <*Main Data.Function>: repeat 1
[1,1,1,1,1,1, and so on
λ <*Main Data.Function>: (\x->1:x) $ repeat 1
[1,1,1,1,1,1, and so on

Es ist das Gleiche! Da dies der einzige Fixpunkt ist, fixmuss man sich darauf festlegen. Sorry fix, keine Endlosschleifen oder undefiniert für dich.

PyRulez
quelle