trận đấu Incomplete với VÀ mẫu

Question

tôi đã xác định một cấu trúc cây biểu hiện trong F # như sau:

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 

tôi muốn để có thể khá-in cây biểu hiện vì vậy tôi đã làm như sau:

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 

Tuy nhiên, tôi không thực sự thích cách tiếp cận failwith cho hàm operator vì nó không an toàn trong thời gian biên dịch. Vì vậy, tôi viết lại nó như là một mô hình hoạt động:

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

Bây giờ tôi có thể viết lại chức năng format của tôi đẹp như sau:

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 

tôi cho rằng, kể từ khi F # là ma thuật, mà điều này chỉ có thể làm việc. Thật không may, trình biên dịch cảnh báo tôi về các kết quả mẫu không hoàn chỉnh, vì không thể thấy bất kỳ thứ gì khớp với Unary(x) cũng sẽ khớp với Operator(op) và bất kỳ thứ gì khớp với Binary(x, y) cũng sẽ khớp với Operator(op). Và tôi xem xét các cảnh báo như vậy là xấu như lỗi trình biên dịch. Vì vậy, câu hỏi của tôi là: Có một lý do cụ thể tại sao điều này không hoạt động (như tôi đã để lại một số chú giải phép thuật ở đâu đó hoặc có điều gì đó mà tôi không thấy)? Có cách giải quyết đơn giản nào tôi có thể sử dụng để có được loại an toàn tôi muốn không? Và có một vấn đề cố hữu với kiểu kiểm tra biên dịch thời gian này hay là một thứ gì đó mà F # có thể thêm vào trong một số bản phát hành trong tương lai?

Answer 1

Nếu bạn mã sự tuyệt chủng giữa các thuật ngữ nền tảng và cụm từ phức tạp trong hệ thống kiểu, bạn có thể tránh kiểm tra thời gian chạy và biến chúng trở thành mẫu khớp hoàn chỉnh.

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 

cũng vậy, bạn nên tránh boxing nếu bạn muốn an toàn kiểu. Nếu bạn thực sự muốn cả hai trường hợp, hãy tạo hai mẫu. Hoặc, như được thực hiện ở đây, chỉ cần thực hiện một phép chiếu cho loại bạn cần sau này. Bằng cách này bạn tránh boxing và thay vào đó bạn trả lại những gì bạn cần cho in ấn.

Answer 2

Tôi nghĩ bạn có thể làm cho operator một chức năng bình thường thay vì một mẫu đang hoạt động. Bởi vì toán tử chỉ là một hàm cung cấp cho bạn một chuỗi toán tử cho một số expr, trong đó có unary, binary và terminal là các loại biểu thức và do đó có ý nghĩa đối với đối sánh mẫu trên chúng.

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

tôi tìm ra giải pháp tốt nhất là để cơ cấu lại ban đầu loại defintion của bạn:

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

Tất cả các loại chức năng sau đó có thể được viết trên UnOp và BinOp loại bao gồm việc lựa chọn nhà khai thác. Bạn thậm chí có thể muốn chia BinOp thành toán tử số học và so sánh trong tương lai.

Ví dụ: tôi đã sử dụng phương pháp này trong bài viết (không miễn phí) "Language-oriented programming: The Term-level Interpreter " (2008) trong F# Journal.