partita incompleta con e modelli

Question

ho definito una struttura ad albero espressione in F # come segue:

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 

volevo essere in grado di pretty-print l'albero di espressione così ho fatto la seguente:

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 

Tuttavia, non mi piace l'approccio failwith per la funzione operator poiché non è sicuro in fase di compilazione. Così ho riscritto come un modello attivo:

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

ora posso riscrivere la mia funzione format splendidamente come segue:

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 

ho assunto, in quanto F # è magia, che questo sarebbe solo lavorare. Sfortunatamente, il compilatore mi avvisa delle corrispondenze di pattern incomplete, perché non può vedere che tutto ciò che corrisponde allo Unary(x) corrisponderà anche allo Operator(op) e qualsiasi cosa corrispondente allo Binary(x, y) corrisponderà anche allo Operator(op). E considero gli avvertimenti come quello essere pessimi come errori del compilatore.

Quindi le mie domande sono: C'è una ragione specifica per cui questo non funziona (come ho lasciato qualche annotazione magica da qualche parte o c'è qualcosa che non vedo)? C'è una soluzione semplice che potrei usare per ottenere il tipo di sicurezza che voglio? E c'è un problema inerente con questo tipo di controllo in fase di compilazione, o è qualcosa che F # potrebbe aggiungere in qualche versione futura?

Answer 1

Se si codifica la distinzione tra termini di terra e termini complessi nel sistema di tipi, è possibile evitare il controllo di runtime e renderli corrispondenze di modello complete.

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 

anche, imo, si dovrebbe evitare il pugilato se si vuole essere sicuro per il tipo. Se vuoi davvero entrambe le cause, crea due schemi. Oppure, come fatto qui, basta fare una proiezione per il tipo che ti servirà in seguito. In questo modo si evita la boxe e si restituisce invece ciò che è necessario per la stampa.

Answer 2

Penso che si possa rendere operator una funzione normale piuttosto che un modello attivo. Perché l'operatore è solo una funzione che ti dà una stringa operatore per un expr, dove come unary, binary e terminal sono tipi di espressione e quindi ha senso associare il modello su di essi.

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

trovo la soluzione migliore è quella di ristrutturare il vostro tipo di defintion originale:

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

Tutti i tipi di funzioni possono essere scritti nel corso degli UnOp e BinOp tipi compresi gli operatori selezione. Potresti persino voler dividere lo BinOp in operatori aritmetici e di confronto in futuro.

Ad esempio, ho utilizzato questo approccio nell'articolo (non libero) "Language-oriented programming: The Term-level Interpreter " (2008) nel numero F# Journal.