Rekursive Typcodierung auf System F (und anderen reinen Typsystemen)

Ich studiere reine Typensysteme, insbesondere die Berechnung von Konstruktionen, und versuche, eine Codierung für rekursive Typen darauf zu verwenden, was laut Philip Wadler möglich ist . Als Beispiel verwende ich die Morte Haskell-Bibliothek , um Scott-Ziffern zu codieren, wie sie von Cardelli angegeben wurden .

Eine Zusammenfassung der Codierung lautet als solche: bei einem (positiven) rekursiven Typ ...

... wir können es als Typ auf System F codieren als ...

... oder unter Verwendung der Notation von reinen Typsystemen (mit einem expliziten ) ...$F$

... da ein Typkonstruktor ist ( ist der Typ der Typen).$F$$*$

Um eine solche zu kodieren, müssen wir drei Funktionen erklären, , und , nach Wadler und durch Cardelli auf der Codierung für Scott Zeichen verwendet.$fold$$in$$out$

Falz: Alle X. (FX -> X) -> T -> X.

fold = \ X. \ k: FX -> X. \ t: T. t X k

in: FT -> T.

in = \ s: F T. \ X. \ k: FX -> X. k (F (Falte X k) s).

(Wo ist .)$T$$Lfix\ X. F\ X$

Es ist trivial, die wie angegeben zu schreiben . Aber wenn versucht wird, die Funktion zu schreiben , scheint sie nicht typecheck zu sein. Der Ausdruck hat den Typ , und sollte vom Typ . Dann schließen wir, dass vom Typ (sieht aus wie a ). Dies ist keine Typprüfung, da es sich um einen Typkonstruktor handelt (vom Typ ).$fold$$in$$(fold\ X\ k)$$T\rightarrow X$$(F\ (fold\ X\ k)\ s)$$F\ X$$F$$(T\rightarrow X)\rightarrow F\ T\rightarrow F\ X$fmapF$*\rightarrow*$

Das sieht nicht nach einem Tippfehler aus ... vermisse ich etwas?

In der Kategorietheorie gibt es eine Konvention, dass dasselbe Symbol für einen Typkonstruktor und die Kartenfunktion über diesem Typkonstruktor verwendet wird. Wenn also f: X -> Y, dann F f: FX -> F Y.