Wie funktioniert diese Definition von ArrowLoop.loop?

Question

Die Funktionsinstanz für ArrowLoop enthält

loop :: ((b,d) -> (c,d)) -> (b -> c) 
loop f b = let (c,d) = f (b,d) in c 

Zuerst habe ich ein Problem mit der Signatur haben: Wie können wir b -> c von (b,d) -> (c,d) erhalten möglicherweise? Ich meine, die c im resultierenden Tupel kann von beiden Elementen des Eingangs abhängen, wie ist es möglich, den Einfluss von d "abzuschneiden"?

Zweitens bekomme ich nicht, wie die let hier funktioniert. Enthält keine (c,d) = f (b,d) eine zyklische Definition für d? Woher kommt d? Um ehrlich zu sein, bin ich überrascht, dass dies eine gültige Syntax ist, da es aussieht, als würden wir d neu definieren.

Ich meine in der Mathematik würde dies Sinn machen, z.B. f könnte eine komplexe Funktion sein, aber ich würde nur den reellen Teil b liefern, und ich würde den imaginären Teil d so wählen müssen, dass er sich nicht ändert, wenn ich f (b, d) auswerte, was es machen würde eine Art Fixpunkt. Aber wenn diese Analogie gilt, muss der Ausdruck let irgendwie nach diesem festen Punkt für d "suchen" (und es könnte mehr als eins geben). Das sieht für mich fast magisch aus. Oder denke ich zu kompliziert?

Answer 1

Dies funktioniert genauso die Standarddefinition von fix Werke:

fix f = let x = f x in x 

das heißt, es ist ein Fixpunkt in der exact same way fix does finden: rekursiv.

Betrachten Sie als ein triviales Beispiel beispielsweise loop (\((),xs) -> (xs, 1:xs))(). Dies ist genau wie fix (\xs -> 1:xs); Wir ignorieren unsere Eingabe und verwenden den d-Ausgang (hier xs) als Hauptausgang. Das Extra-Element in dem Tupel, das loop hat, enthält nur den Eingabeparameter und den Ausgabewert, da die Pfeile nicht curren können. Berücksichtigen Sie, wie Sie eine faktorielle Funktion mit fix definieren würden - Sie würden am Ende Curry verwenden, aber wenn Sie Pfeile verwenden, würden Sie den zusätzlichen Parameter und die Ausgabe verwenden, die Ihnen loop gibt.

Grundsätzlich bindet loop einen Knoten, geben einen Pfeil Zugriff auf einen Hilfsausgang von sich selbst, genau wie fix bindet einen Knoten, wodurch eine Funktion Zugriff auf seinen eigenen Ausgang als Eingang.

Answer 2

"Suche nach dem Fixpunkt" ist genau was dies tut. Das ist Haskells Faulheit in Aktion. Weitere Informationen finden Sie unter Wikipedia.