不完全匹配和模式

Question

我如下定義在F＃表達式目錄樹結構：

type Num = int 
type Name = string 
type Expr = 
    | Con of Num 
    | Var of Name 
    | Add of Expr * Expr 
    | Sub of Expr * Expr 
    | Mult of Expr * Expr 
    | Div of Expr * Expr 
    | Pow of Expr * Expr 
    | Neg of Expr 

我希望能夠漂亮地打印的表達式樹，所以我做了以下內容：

let (|Unary|Binary|Terminal|) expr = 
    match expr with 
    | Add(x, y) -> Binary(x, y) 
    | Sub(x, y) -> Binary(x, y) 
    | Mult(x, y) -> Binary(x, y) 
    | Div(x, y) -> Binary(x, y) 
    | Pow(x, y) -> Binary(x, y) 
    | Neg(x) -> Unary(x) 
    | Con(x) -> Terminal(box x) 
    | Var(x) -> Terminal(box x) 

let operator expr = 
    match expr with 
    | Add(_) -> "+" 
    | Sub(_) | Neg(_) -> "-" 
    | Mult(_) -> "*" 
    | Div(_) -> "/" 
    | Pow(_) -> "**" 
    | _ -> failwith "There is no operator for the given expression." 

let rec format expr = 
    match expr with 
    | Unary(x) -> sprintf "%s(%s)" (operator expr) (format x) 
    | Binary(x, y) -> sprintf "(%s %s %s)" (format x) (operator expr) (format y) 
    | Terminal(x) -> string x 

但是，我不太喜歡operator函數的failwith方法，因爲它不是編譯時安全的。所以我重寫了它作爲有效模式：

let (|Operator|_|) expr = 
    match expr with 
    | Add(_) -> Some "+" 
    | Sub(_) | Neg(_) -> Some "-" 
    | Mult(_) -> Some "*" 
    | Div(_) -> Some "/" 
    | Pow(_) -> Some "**" 
    | _ -> None 

現在我可以漂亮重寫我的format功能如下：

let rec format expr = 
    match expr with 
    | Unary(x) & Operator(op) -> sprintf "%s(%s)" op (format x) 
    | Binary(x, y) & Operator(op) -> sprintf "(%s %s %s)" (format x) op (format y) 
    | Terminal(x) -> string x 

我假設，因爲F＃是神奇的，這將只是工作。不幸的是，編譯器會提示我關於不完整的模式匹配，因爲它看不到匹配Unary(x)的任何內容也會匹配Operator(op)，並且匹配Binary(x, y)的任何內容也將匹配Operator(op)。我認爲這樣的警告與編譯錯誤一樣糟糕。

所以我的問題是：有沒有一個特定的原因，爲什麼這不起作用（像我離開了一些神奇的註釋關閉某處或有什麼，我只是沒有看到）？有沒有一種簡單的解決方法可以用來獲得我想要的安全類型？這種編譯時檢查存在固有的問題，還是F＃可能在未來版本中添加的東西？

Answer 1

如果將基礎條件和複雜條件之間的命令編碼到類型系統中，則可以避免運行時檢查並使它們成爲完整模式匹配。

type Num = int 
type Name = string 

type GroundTerm = 
    | Con of Num 
    | Var of Name 
type ComplexTerm = 
    | Add of Term * Term 
    | Sub of Term * Term 
    | Mult of Term * Term 
    | Div of Term * Term 
    | Pow of Term * Term 
    | Neg of Term 
and Term = 
    | GroundTerm of GroundTerm 
    | ComplexTerm of ComplexTerm 


let (|Operator|) ct = 
    match ct with 
    | Add(_) -> "+" 
    | Sub(_) | Neg(_) -> "-" 
    | Mult(_) -> "*" 
    | Div(_) -> "/" 
    | Pow(_) -> "**" 

let (|Unary|Binary|) ct = 
    match ct with 
    | Add(x, y) -> Binary(x, y) 
    | Sub(x, y) -> Binary(x, y) 
    | Mult(x, y) -> Binary(x, y) 
    | Div(x, y) -> Binary(x, y) 
    | Pow(x, y) -> Binary(x, y) 
    | Neg(x) -> Unary(x) 

let (|Terminal|) gt = 
    match gt with 
    | Con x -> Terminal(string x) 
    | Var x -> Terminal(string x) 

let rec format expr = 
    match expr with 
    | ComplexTerm ct -> 
     match ct with 
     | Unary(x) & Operator(op) -> sprintf "%s(%s)" op (format x) 
     | Binary(x, y) & Operator(op) -> sprintf "(%s %s %s)" (format x) op (format y) 
    | GroundTerm gt -> 
     match gt with 
     | Terminal(x) -> x 

另外，如果你想要類型安全，你應該避免拳擊。如果你真的想要這兩種情況，請製作兩種模式。或者，就像這裏所做的那樣，只需稍後進行投影即可。這樣你可以避免拳擊，而是返回你需要打印的東西。

Answer 2

我認爲你可以使operator成爲一個正常的功能，而不是一個活動模式。因爲運算符只是一個函數，它爲您提供expr的運算符字符串，其中unary，binary和terminal是表達式類型，因此對它們進行模式匹配是有意義的。

let operator expr = 
    match expr with 
    | Add(_) -> "+" 
    | Sub(_) | Neg(_) -> "-" 
    | Mult(_) -> "*" 
    | Div(_) -> "/" 
    | Pow(_) -> "**" 
    | Var(_) | Con(_) -> "" 


let rec format expr = 
    match expr with 
    | Unary(x) -> sprintf "%s(%s)" (operator expr) (format x) 
    | Binary(x, y) -> sprintf "(%s %s %s)" (format x) (operator expr) (format y) 
    | Terminal(x) -> string x 

Answer 3

我找到了最好的解決方法是調整你的原稿類型確定指標：

type UnOp = Neg 
type BinOp = Add | Sub | Mul | Div | Pow 
type Expr = 
    | Int of int 
    | UnOp of UnOp * Expr 
    | BinOp of BinOp * Expr * Expr 

的功能種種可以寫在UnOp和BinOp類型，包括選擇經營者。您甚至可能希望在將來將BinOp分解爲算術和比較運算符。

例如，我在（非免費）物品"Language-oriented programming: The Term-level Interpreter "（2008）的F# Journal中使用了此方法。