Неполное совпадение с и модели

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 

Тем не менее, мне не очень нравится подход failwith для функции operator, так как он не безопасен во время компиляции. Так что я переписал его в качестве активного шаблона:

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 

также, imo, вам следует избегать бокса, если вы хотите быть безопасным. Если вы действительно хотите оба случая, сделайте два шаблона. Или, как сделано здесь, просто сделайте проецирование к типу, который вам нужен позже. Таким образом вы избегаете бокса, и вместо этого вы возвращаете то, что вам нужно для печати.

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.