Warum wird meine Typdefinition als zyklisch abgelehnt, wenn sie als Variante deklariert wird, aber ansonsten akzeptiert? - Typen, funktionale Programmierung, Ocaml, ml, zyklisch

Ich habe mit der Verwendung von OCaml herumgespielt und einige der Datenstrukturen in Chris Okasakis rein funktionalen Datenstrukturen implementiert und bin auf diese Typdefinition gestoßen:

 type tree = Node of int * int * tree list;;

Ich habe nicht gedacht, dass das Tag benötigt wird, da es sich nicht um einen Union-Typ handelt. Daher habe ich versucht, das Tag zu entfernen. Es wurde jedoch der folgende Fehler angezeigt:

# type tree = int * int * tree list;;
Characters 5-33:
type tree = int * int * tree list;;
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Error: The type abbreviation tree is cyclic

Warum passiert dies bei zwei scheinbar äquivalenten Typdefinitionen?

Antworten:

8 für die Antwort № 1

In ML-ähnlichen Sprachen ist die Definition von aEin rekursiver Typ ist ein Typ, bei dem die Rekursion keinen Variantentyp durchläuft. Dies ist eine pragmatische Definition in dem Sinne, dass sie zu einer nützlicheren Typprüfung führt.

Rekursive Typen können nicht geändert werden. Sie können die Unterstützung für rekursive Typen in OCaml mit aktivieren -rectypes Flagge.

$ ocaml -rectypes
OCaml version 4.02.1

# type tree = int * int * tree list;;
type tree = int * int * tree list
# let x: tree = (3, 3, [(4, 4, [])]);;
val x : tree = (3, 3, [(4, 4, [])])

Alle üblichen starken Tippgarantien sindIst vorhanden, wenn rekursive Typen aktiviert sind. Der Hauptnachteil ist, dass viele unbeabsichtigte Programme akzeptiert werden. Mit anderen Worten ist das Vorhandensein eines rekursiven Typs oft ein Hinweis auf einen Programmierfehler.

---

1 für die Antwort № 2

Die erste Typdefinition definiert einen neuen Typ. Wenn Sie den Konstruktornamen weglassen, wird statt des Definierens eines neuen Typs eine Typabkürzung eingeführt. Standardmäßig dürfen Typabkürzungen nicht rekursiv sein, da dies normalerweise nicht gemeint ist.

Sie können eine beliebige Syntax für die Typdefinition verwenden, die einen neuen Typ definiert, um rekursive Typen zu erstellen, nicht nur Varianten. Aufzeichnungen werden zum Beispiel auch funktionieren

type tree = { node : int * int * tree list }

oder noch besser

type tree = {
value : int;
depth : int;
children : tree list;
}

(Anmerkung: Feldnamen wurden willkürlich gewählt, da ich ihren ursprünglichen Zweck nicht kenne.)

Zusammenfassend werden Summentypen nicht nur verwendet, um nicht zusammenhängende Typenmengen einzuführen, sondern auch, um neue Typen zu erstellen.

 type t = Constr x

führt Typ ein t, die mit einem Konstruktor erstellt werden können Constr aus Werten vom Typ x.

---