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

Я определил структуру дерева выражений в 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# может добавить в какой-то будущий выпуск?

Источник

3 ответа

Решение

Если вы закодируете назначение между основными терминами и сложными терминами в систему типов, вы можете избежать проверки во время выполнения и сделать их полными совпадениями шаблонов.

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, вы должны избегать бокса, если вы хотите быть типобезопасными. Если вы действительно хотите оба случая, сделайте два шаблона. Или, как это сделано здесь, просто сделайте прогноз на нужный вам тип позже. Таким образом вы избегаете бокса, а вместо этого возвращаете то, что нужно для печати.

Источник

Я считаю, что лучшее решение - это изменить исходное определение типа:

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 в арифметику и операторы сравнения в будущем.

Например, я использовал этот подход в (несвободной) статье "Языково-ориентированное программирование: переводчик терминов" (2008) в F# Journal.

Источник

Я думаю, что вы можете сделать 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
Источник
Другие вопросы по тегам