Vereinheitlichung mit rekursiven Datentypen

Question

Nach dem suggestion rekursive Datentypen für eine verschachtelte Struktur wie ein Baum zu verwenden Ich habe versucht, recsurive Datatyep in einem Testprogramm zu arbeiten, sondern stieß auf (noch eine, sehr kryptisch für mich) Fehler.

Mein Programm ist dies:

datatype 'a tree = 
    Leaf of { value : 'a } 
| Node of { value : 'a, left: 'a tree, right: 'a tree } 


fun recursivetreebuilder a n = 
    if n = 0 
    then 
     Leaf a 
    else 
     Node (a, recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1)) 

So wird die Funktion soll einen binären Baum der Tiefe n, aufzubauen, indem rekursiv selbst mit verringert n s bis n Aufruf ist 0.

Aber ich Ich bekomme diesen Fehler:

Can't unify {left: 'a tree, right: 'a tree, value: 'a} with {value: 'b} * 
(Int32.int/int -> 'c) * (Int32.int/int -> 'c) (Field 1 missing) Found near if 
<(n, 0) then Leaf(a) else Node(a, recursivetreebuilder(...), ......) 

Mit rekursiven Datentypen sollte eine andere Vereinheitlichung iss gelöst werden wenn geschachtelte Listen verwendet werden. Vielleicht sollte ich sehen können, wo das Problem die Erklärung zu meiner anderen Frage gegeben hat, aber ich noch nicht.

Auf welches "Feld 1" bezieht sich der Compiler und warum kann es nicht vereinheitlichen, wenn rekursive Datentypen dazu dienen sollten, verschiedene "Untertypen" desselben Datentyps zu vereinheitlichen?

bearbeiten

mehrere der vorgeschlagenen Strukturen ausprobiert, aber immer noch Fehler bekommen. Zum Beispiel für

datatype 'a tree = 
    Leaf of 'a 
    | Node of 'a tree * 'a tree 


fun recursivetreebuilder a n = 
    if n < 0 
    then 
     Leaf (a) 
    else 
     Node (recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1)) 

bekomme ich

val printList = fn : Int.int list -> unit 
Error- in 'recon_bintree.sml', line 12. 
Can't unify 'a with 'a * Int32.int/int (Type variable to be unified occurs in type) Found near if 
<(n, 0) then Leaf(a) else 
Node(recursivetreebuilder(a, ...), recursivetreebuilder(...)) 
Error- in 'recon_bintree.sml', line 12. 
Can't unify 'a with 'a * Int32.int/int (Type variable to be unified occurs in type) Found near if 
<(n, 0) then Leaf(a) else 
Node(recursivetreebuilder(a, ...), recursivetreebuilder(...)) 
Error- in 'recon_bintree.sml', line 12. 
Can't unify 'a tree with Int32.int/int -> 'b (Incompatible types) Found near if 
<(n, 0) then Leaf(a) else 
Node(recursivetreebuilder(a, ...), recursivetreebuilder(...)) 
Error- in 'recon_bintree.sml', line 12. 
Can't unify 'a tree with Int32.int/int -> 'b (Incompatible types) Found near if 
<(n, 0) then Leaf(a) else 
Node(recursivetreebuilder(a, ...), recursivetreebuilder(...)) 
Exception- Fail "Static errors (pass2)" raised 

Answer 1

Es gibt zwei Probleme hier.

Das erste Problem ist, dass — zum Beispiel — { value : 'a, left: 'a tree, right: 'a tree } ein Record-Typ ist, während (a, recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1)) ein Tupel eher als ein Rekord. Sie passen also nicht zusammen; Es ist so, als würde man eine real an eine Funktion übergeben, die eine int erwartet.

(Pedantic beiseite: technisch Tupeln tatsächlich sind Aufzeichnungen, aber sehr spezifische Art; (a, b, c) ist syntaktischer Zucker für { 1 = a, 2 = b, 3 = c } Für die meisten praktischen Zwecke können Sie denken von Tupeln und Aufzeichnungen ebenso wie zwei ähnliche, aber komplett-getrennt. Wegen Arten zu kombinieren. aber jetzt wissen Sie, warum die Fehlermeldung an „Feld 1“ bezeichnet.)

das zweite Problem ist, dass Sie die Funktion currying sind deklarieren zu verwenden (fun recursivetreebuilder a n = ...), aber dann versuchen Sie anrufen es mit einem Tupel (recursivetreebuilder(a, n-1)).

---

Ein Ansatz ist, mit Ihrer Datentypdefinition zu bleiben, und die Funktion hält currying verwenden und alles ändern, diese Entscheidungen zu entsprechen:

datatype 'a tree = 
    Leaf of { value : 'a } 
| Node of { value : 'a, left: 'a tree, right: 'a tree } 

fun recursivetreebuilder a n = 
    if n = 0 
    then 
     Leaf { value = a} 
    else 
     Node { value = a, 
      left = recursivetreebuilder a (n-1), 
      right = recursivetreebuilder a (n-1) } 

oder Ihre Datentypdefinition ändern, um die Datensatztypen zu beseitigen, und ändern Sie die Funktion, um das Curry zu beseitigen:

datatype 'a tree = 
    Leaf of 'a 
| Node of 'a * 'a tree * 'a tree 

fun recursivetreebuilder (a, n) = 
    if n = 0 
    then 
     Leaf a 
    else 
     Node (a, recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1)) 

oder mix-and-match die oben genannten. (Das Update für das Record-vs.-Tupel-Problem ist unabhängig von der Behebung für das Currying-Tupel-Problem.Übrigens)

---

, ich denke, es ist ein Fehler Wert sowohl im Leaf Fall und im Fall Node aufzunehmen. Mit Ihrer aktuellen Definition ist es unmöglich, einen Baum zu haben, der genau 0 oder genau 2 Elemente enthält.

Stattdessen denke ich, Sie entweder leer Blätter haben sollte:

datatype 'a tree = 
    Leaf 
| Node of 'a * 'a tree * 'a tree 

oder Knoten, die aber keine Werte haben ihre eigenen Kind-Knoten:

datatype 'a tree = 
    Leaf of 'a 
| Node of 'a tree * 'a tree 

oder zu beseitigen, die Unterscheidung zwischen Blättern und Knoten und machen die Kinder optional:

datatype 'a tree = 
    Node of 'a * 'a tree option * 'a tree option