Algorithmus W unter Verwendung von Rekursionschemata

Question

Ich wollte in der Lage sein, den Inferenzalgorithmus nach Hindley-Milner mit Festkomma-Datentypen und Rekursionschemata zu formulieren. alle Details neben den eigentlichen Rekursion Teile Ohne Berücksichtigung: baut

w env term = case term of 
    Lam n e -> lam (w (modify1 env) e) 
    App a b -> app (w (modify2 env) a) (w (modify3 env) b) 
    ... 

Der Algorithmus eine Umgebungsdatenstruktur env wie es rekursiv den Baum durchläuft, bis er die Blätter erreicht. Dann verwendet es diese Information, da es das Ergebnis wieder aufbaut.

Ohne den env Teil könnte dies einfach mit cata implementiert werden. Kann dies (mit env) im Allgemeinen unter Verwendung von Rekursionschemata durchgeführt werden?

Answer 1

Ja gerade das Ziel der Env -> a

eine Funktion cata machen - luqui

Ja, aber Sie müssen wahrscheinlich cata mit einem übergeordneten Trägertyp verwenden, Berechnen einer Aktion, die die Umgebung ändern und möglicherweise fehlschlagen kann.

- pigworker

Answer 2

Ohne das env Teil, das leicht mit Cata umgesetzt werden könnten. Kann dies (mit env) im Allgemeinen unter Verwendung von Rekursionssystemen durchgeführt werden?

Was Sie suchen, ist ein chronomorphism. Dies ermöglicht Ihnen, Rekursion mit sowohl Ergebnisse aus der Zukunft und der Vergangenheit zu tun. Es ist nicht so benutzerfreundlich wie es klingt, aber es ist die kanonische Art, Dinge mit Rekursionschemata zu tun.