Niekompletne mecz z I wzory

Question

Mam zdefiniowane struktury drzewa wyrażenie w F # następująco:

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 

Chciałem móc całkiem-print drzewo wyrażenie tak zrobiłem następujące:

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 

Jednak nie podoba mi się podejście failwith dla funkcji operator, ponieważ nie jest to bezpieczne w czasie kompilacji. Więc przepisał go jako aktywnego wzoru:

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

Teraz mogę przepisać mój format funkcję pięknie następująco:

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 

Przypuszczałem, ponieważ F # jest magia, że ​​to po prostu działa. Niestety, kompilator ostrzega mnie przed niekompletnymi dopasowaniami do wzorca, ponieważ nie widzi, że cokolwiek pasującego do Unary(x) będzie również pasowało do Operator(op), a wszystko, co pasuje do Binary(x, y), będzie również pasować do Operator(op). I uważam, że takie ostrzeżenia są tak złe, jak błędy kompilatora.

Moje pytania brzmią: czy istnieje konkretny powód, dla którego to nie działa (jak zostawiłem gdzieś magiczną adnotację, czy jest coś, czego po prostu nie widzę)? Czy istnieje prosty sposób obejścia tego problemu, aby uzyskać pożądany rodzaj bezpieczeństwa? I czy jest jakiś nieodłączny problem z tym typem sprawdzania podczas kompilacji, czy jest to coś, co F # może dodać w przyszłym wydaniu?

Answer 1

Po zakodowaniu przeznaczenia między terminami naziemnymi i złożonymi w systemie tekstowym można uniknąć sprawdzania w czasie wykonywania i sprawić, aby były kompletnymi dopasowaniami do wzorca.

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 

również, imo, powinieneś unikać boksowania, jeśli chcesz być bezpieczny w użyciu. Jeśli naprawdę chcesz obu przypadków, wykonaj dwa schematy. Lub, jak to zrobiono tutaj, po prostu wykonaj projekcję do typu, którego potrzebujesz później. W ten sposób unikasz boksowania, a zamiast tego zwracasz to, czego potrzebujesz do drukowania.

Answer 2

Myślę, że można sprawić, by operator była normalną funkcją, a nie aktywnym wzorcem. Ponieważ operator jest po prostu funkcją, która daje ci ciąg znaków operatora dla expr, gdzie jako unary, binary i terminal są typy ekspresji, a więc ma sens, aby dopasować do nich wzorce.

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

znajdę najlepszym rozwiązaniem jest, aby zrestrukturyzować swój oryginalny typ Definition:

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

Różne funkcje mogą być napisane w ciągu UnOp i BinOp typów, w tym operatorów wybierających. Możesz nawet w przyszłości rozdzielić operatora na operatory arytmetyczne i porównania.

Na przykład użyłem tego podejścia w (niewolnym) artykule "Language-oriented programming: The Term-level Interpreter " (2008) w F# Journal.