F # Binärbaum Insert-Typ Fehler

Question

Ich arbeite an einer einfachen BST-Implementierung in F # und habe einen Stolperstein getroffen, den ich nicht finden kann.

Dieser Code:

type BST = 
| Empty 
| TreeNode of int * BST * BST 

let rec insert value tree = function 
    | Empty -> TreeNode(value, Empty, Empty) 
    | TreeNode(hd, left, right) as node -> 
     if hd = value then node 
     elif value < hd then TreeNode(hd, insert value left, right) 
     else TreeNode(hd, left, insert value right) 

Ergebnisse in dem folgenden Fehler:

error FS0001: This expression was expected to have 
type 
'BST'  

but here has type 
'BST -> BST' 

, die zu diesen beiden Codezeilen bezieht

elif value < hd then TreeNode(hd, insert value left, right) 
else TreeNode(hd, left, insert value right) 

speziell die rekursive Aufrufe ... insert value left, ... und ... insert value right)

Ich verstehe F # gut genug, um zu verstehen, warum dies ein Problem für den Compiler ist. Wenn es ausgeführt wird, sollte dieser Wert nicht einfach BST eingeben? Ist das nicht der Sinn dieser Art von Rekursion?

Answer 1

let f = function 
| ... 

entspricht:

let f x = 
    match x with 
    | ... 

so definieren Sie insert 3 Parameter zu nehmen, anstatt die beiden Sie beabsichtigen. Ihr insert hat den Typ int -> 'a -> BST -> BST, so dass Sie dem rekursiven Aufruf nicht genügend Parameter zur Verfügung stellen, daher der Fehler. Da Sie über die Struktur des Baumes entsprechen mögen, entfernen Sie die tree Parameter heißen

let rec insert value = function 
    | Empty -> TreeNode(value, Empty, Empty) 
    | TreeNode(hd, left, right) as node -> 
     if hd = value then node 
     elif value < hd then TreeNode(hd, insert value left, right) 
     else TreeNode(hd, left, insert value right)