Wie benutze ich Fix und wie funktioniert es?

Question

Ich war ein bisschen verwirrt über die Dokumentation für fix (Obwohl ich denke, ich verstehe, was es jetzt tun soll), also habe ich mir den Quellcode angesehen. Das ließ mich verwirrter:

fix :: (a -> a) -> a
fix f = let x = f x in x

Wie genau gibt dies einen Fixpunkt zurück?

Ich beschloss, es unter der Kommandozeile auszuprobieren:

Prelude Data.Function> fix id
...

Und es hängt dort. Um fair zu sein, ist dies auf meinem alten MacBook, das irgendwie langsam ist. Diese Funktion kann jedoch nicht sein zu Rechenintensiv, da etwas, das in ID überging, dasselbe zurückgibt (ganz zu schweigen davon, dass es keine CPU -Zeit isst). Was mache ich falsch?

Answer 1

Du machst nichts falsch. fix id ist eine unendliche Schleife.

Wenn wir das sagen fix Gibt den am wenigsten festen Punkt einer Funktion zurück, wir meinen das in der Domain -Theorie Sinn. So fix (\x -> 2*x-1) ist nicht werde zurückkehren 1, denn obwohl 1 ist ein fester Punkt dieser Funktion, es ist nicht das am wenigsten eine in der Domain -Bestellung.

Ich kann die Domain -Bestellung nicht in einem oder zwei Absätzen beschreiben, daher werde ich Sie auf den oben genannten Link der Domain -Theorie verweisen. Es ist ein ausgezeichnetes Tutorial, leicht zu lesen und ziemlich aufschlussreich. Ich empfehle es sehr.

Für die Aussicht von 10.000 Fuß, fix ist eine Funktion höherer Ordnung, die die Idee von codiert Rekursion. Wenn Sie den Ausdruck haben:

let x = 1:x in x

Dies führt zur unendlichen Liste [1,1..], man könnte dasselbe sagen, das gleiche verwendet fix:

fix (\x -> 1:x)

(Oder einfach fix (1:)), die sagt, finde mir einen festen Punkt der (1:) Funktion, einen Wert x so dass x = 1:x... genau wie wir oben definiert haben. Wie Sie aus der Definition sehen können, fix ist nichts weiter als diese Idee - Rekursion, die in eine Funktion eingekapselt sind.

Es ist auch ein wirklich allgemeines Konzept der Rekursion - Sie können jede rekursive Funktion auf diese Weise schreiben. einschließlich Funktionen, die die polymorphe Rekursion verwenden. Zum Beispiel die typische Fibonacci -Funktion:

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

Kann mit mithilfe von geschrieben werden fix Hier entlang:

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

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

Lesen Sie jedoch für ein vollständiges Verständnis über die Domänentheorie. Es ist wirklich cooles Zeug.

Answer 2

Ich behaupte nicht, das überhaupt zu verstehen, aber wenn dies jemandem hilft ... dann Yippee.

Betrachten Sie die Definition von fix. fix f = let x = f x in x. Der umwerfende Teil ist das x ist definiert als f x. Aber denken Sie für eine Minute darüber nach.

x = f x

Da x = fx dann können wir den Wert von ersetzen x Auf der rechten Seite davon, oder? 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 ist also, um zu beenden, f muss eine Art Struktur erzeugen, damit ein später f Kann Muster dieser Struktur übereinstimmen und die Rekursion beenden, ohne sich tatsächlich um den vollen "Wert" seines Parameters zu kümmern (?)

Es sei denn natürlich, Sie möchten so etwas wie eine unendliche Liste erstellen, wie Luqui illustrierte.

Tommds faktorielle Erklärung ist gut. Die Typ -Signatur von Fix ist (a -> a) -> a. Die Typsignatur 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). Also können wir das sagen a = (b -> b). Auf diese Weise nimmt Fix unsere Funktion, die ist a -> a, oder wirklich, (b -> b) -> (b -> b), und wird ein Ergebnis des Typs zurückgeben a, mit anderen Worten, b -> b, Mit anderen Worten, eine andere Funktion!

Warten Sie, ich dachte, es sollte einen Fixpunkt zurückgeben ... keine Funktion. Nun, sozusagen (da Funktionen Daten sind). Sie können sich vorstellen, dass es uns die endgültige Funktion für die Suche nach einem Fakultät gegeben hat. Wir gaben ihm eine Funktion, die nicht weiß, wie man sich wiederholt (daher ist einer der Parameter dafür eine Funktion, die zum Wiederaufnehmen verwendet wird), und fix lehrte es, wie man sich wiederholt.

Denken Sie daran, wie ich das gesagt habe f muss eine Art Struktur erzeugen, damit ein später f Kann Muster übereinstimmen und enden? Nun, das ist nicht genau richtig, denke ich. Tommd illustrierte, wie wir ausdehnen können x Um die Funktion anzuwenden und auf den Basisfall zu treten. Für seine Funktion benutzte er ein if/dann, und das verursacht eine Beendigung. Nach wiederholten Ersetzungen die in Teil der gesamten Definition von fix Hört schließlich auf, in Bezug auf definiert zu werden x Und dann ist es berechnet und vollständig.

Answer 3

Sie benötigen eine Möglichkeit, dass der Fixpoint endet. Erweitern Sie Ihr Beispiel Es ist offensichtlich, dass es nicht fertig ist:

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

Hier ist ein echtes Beispiel dafür, dass ich Fix verwendet habe (beachten Sie, dass ich Fix nicht oft verwende und wahrscheinlich müde / keine Sorgen über lesbare Code, als ich dies geschrieben habe):

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

WTF, sagst du! Ja, aber hier gibt es ein paar wirklich nützliche Punkte. Zuallererst dein erster fix Das Argument sollte normalerweise eine Funktion sein, die der Fall "Wiederholung" ist, und das zweite Argument sind die Daten, für die sie handeln müssen. Hier ist der gleiche Code wie eine benannte Funktion:

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

Wenn Sie immer noch verwirrt sind, ist Faktor 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? Dass x wurde eine Funktion in unserer then Zweig.

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

Im obigen müssen Sie sich erinnern x = f x, daher die beiden Argumente von x 2 am 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!

Answer 4

Wie ich es verstehe, findet es einen Wert für die Funktion, so dass es dasselbe ausgibt, was Sie ihm geben. Der Haken ist, dass er immer undefinierte (oder eine unendliche Schleife, in Haskell, undefinierte und unendliche Schleifen gleich auswählen wird) oder was auch immer die am meisten undefinierten. Zum Beispiel mit ID,

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

Wie Sie sehen können, ist undefiniert ein fester Punkt, also fix wird das auswählen. Wenn Sie stattdessen ( x-> 1: x).

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

So fix Ich kann nicht undefiniert auswählen. Um es ein bisschen mehr mit unendlichen Schleifen verbunden zu machen.

λ <*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, fix muss sich dagegen einsetzen. Es tut uns leid fix, keine unendlichen Schleifen oder undefiniert für Sie.