Ich habe versucht, das maximale Subsequenz-Problem zu lösen und eine Neato-Lösung gefunden
%Vor% Sie rufen die Wrapperfunktion msss auf, die dann f aufruft, was wiederum die Arbeit erledigt.
Die Lösung ist gut und afaik funktioniert einwandfrei. Wenn ich aus irgendeinem Grund das maximale Subsequenz-Summenproblem im Produktionscode lösen müsste, würde ich es so machen.
Aber diese Wrapper-Funktion nervt mich wirklich. Ich liebe es, wie in Haskell, wenn Sie hartnäckig genug sind, können Sie Ihr gesamtes Programm in einer einzigen Zeile schreiben, um den Punkt, dass ein Programm ist eigentlich nur ein großer Ausdruck wirklich nach Hause fahren. Also dachte ich, ich würde versuchen, die Wrapper-Funktion für die zusätzliche Herausforderung zu eliminieren.
Ich stoße jetzt auf das klassische Problem: Wie mache ich anonyme Rekursion? Wie macht man Rekursion, wenn man Funktionen nicht benennen kann? Zum Glück haben die Computerväter dieses Problem vor langer Zeit gelöst, indem sie Fixed-Point Combinators gefunden haben, wobei das bekannteste das
Ich habe verschiedene Versuche unternommen, um einen Y-Kombinator einzurichten, aber sie können den Compiler nicht umgehen.
%Vor%gibt nur
%Vor%
Der Wechsel von f (y y f) zu f (y f) ergibt nur
%Vor%
Ich habe versucht, einen anderen Ansatz zu wählen, indem ich den Kombinator nur extern definiere, aber das funktioniert immer noch nicht und erfüllt meine Herausforderung, es in einem Ausdruck zu tun, nicht wirklich.
%Vor%Können Sie erkennen, was mit dem, was ich mache, nicht stimmt? Ich bin ratlos. Das Jammern über das Konstruieren unendlicher Typen macht mich wirklich nervös, weil ich, obwohl ich Haskell um diese Art von Sache drehte. Es hat unendliche Datenstrukturen, warum also das Problem mit unendlichen Typen? Ich vermute, dass es etwas mit diesem Paradox zu tun hat, das gezeigt hat, dass untypisiertes Lambda-Kalkül inkonsistent ist. Ich bin mir nicht sicher. Wäre gut, wenn jemand klären könnte.
Ich habe auch den Eindruck, dass Rekursion immer mit den Faltungsfunktionen dargestellt werden kann. Kann mir jemand zeigen, wie ich es schaffen könnte, indem ich einfach eine Falte benutze? Die Anforderung, dass der Code ein einzelner Ausdruck sein muss, steht immer noch.
Da der Y-Kombinator unendlich viele Typen benötigt, benötigen Sie Workarounds wie diese .
Aber ich würde Ihre msss -Funktion wie folgt schreiben:
Nun, lasst uns eine Minute darüber nachdenken. Welchen Typ hat dieser Lambda-Ausdruck?
%Vor% Nun ist f eine Funktion (a -> b) -> a -> b und x ist ein Wert b . Was macht y ? Nun, was wir gerade über f gesagt haben,
Da wir diesen Ausdruck auch auf sich selbst anwenden, wissen wir, dass y denselben Typ wie der gesamte Ausdruck hat. Dies ist der Teil, wo ich ein bisschen ratlos bin.
So y ist eine magische Funktion höherer Ordnung. Und es benötigt zwei Funktionen als Eingabe. Es ist also irgendwie wie y :: f1 -> f2 -> f3 . f2 hat die Form f und f3 hat den oben genannten Ergebnistyp.
Die Frage ist ... was ist f1 ? Nun, es muss gleich dem Typ von y sein. Siehst du, dass dies die Macht von Haskells Typsystem übersteigt? Der Typ ist in sich selbst definiert.
Wenn Sie einen in sich geschlossenen "Einzeiler" haben möchten, dann nehmen Sie stattdessen den Vorschlag von hammar:
%Vor% Obwohl imho, wenn max zulässig ist, sollte auch fix von Data.Function zulässig sein. Es sei denn, Sie sind in einem Prelude-only-Wettbewerb.
Tags und Links haskell functional-programming recursion y-combinator anonymous-recursion