5

我在 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# 可能会在将来的某个版本中添加？

4

3 回答 3

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，如果你想保证类型安全，你应该避免拳击。如果您真的想要两种情况，请制作两种模式。或者，就像这里所做的那样，只需对您稍后需要的类型进行投影。这样您就可以避免装箱，而是返回打印所需的内容。

于 2013-08-05T04:17:32.373 回答
2

我认为您可以制作operator正常功能而不是活动模式。因为 operator 只是一个函数，它为您提供一个运算符字符串，expr其中 asunary和是表达式类型，因此对它们进行模式匹配是有意义的。binaryterminal

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
于 2013-08-05T04:29:26.707 回答
2

我发现最好的解决方案是重构你原来的类型定义：

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将来拆分为算术和比较运算符。

例如，我在F# Journal的（非免费）文章“面向语言的编程：术语级解释器”（2008 年）中使用了这种方法。

于 2013-08-06T00:04:13.280 回答