F#类型和基本计算的动态评估

Question

试着习惯F#我尝试了一些小例子,我的下一步是为逻辑计算/评估编写一些函数,现在我有了这个结构

type Expr =
    | True
    | False
    | Not of Expr
    | And of Expr * Expr

它应该是显而易见的我想达到的目标:能够封装喜欢不同的功能Not,并And像一个计算中使用And(And(True, Not(False)), True),但目前我不明白(这是我第一次wrinting这种"复杂"的功能代码)如何使用这个结构并编写正确的方法,例如我可以编写用于评估

let evalLogic (expr : Expr) : bool =
    match expr with
    | True  -> true
    | False -> false
    | _     -> false (* eval the expression which is not "atomic" *)

然后作为一种方法

let And (left : Expr , right : Expr ) : Expr =
    let value = evalLogic(left) && evalLogic(right)
    match value with
    | true  -> True
    | false -> False

但我知道这是垃圾,而不是正确的实现方式!你能给我一个如何实现预期行为的提示并描述如何扩展它吗？

Answer 1

当编写功能代码来表示和计算表达式的典型模式是定义表达式的类型为区分联合(就像你一样!),然后写一个函数,表达式并返回结果.您的逻辑表达式将计算为布尔值,因此您需要一个函数:

evalLogic : Expr -> bool

在函数中,您需要为每个可能的表达式编写一个案例.你的样本句柄False和TrueBluepixy的代码显示了其余部分.一般的想法是函数可以递归地评估所有子表达式 - 如果你有And(e1, e2),那么你可以评估e1和e2两个布尔值,然后组合它们(使用&&).

您的And功能不需要,因为整个评估都是在evalLogic功能中完成的.这是在功能样式中执行操作的典型方式(因为表达式类型不会经常更改).但是,您还可以使用以下方法支持更多二进制操作:

type Expr = 
  | Constant of bool
  | Unary of Expr * (bool -> bool)
  | Binary of Expr * Expr * (bool -> bool -> bool)

这里的想法是表达式是常量或某些二元或一元逻辑运算符的应用.例如,要表示true && not false,您可以写:

Binary(Constant(true), Unary(Constant(false), not), (&&))

现在表达式树也带有应该使用的函数,因此评估只需要调用函数(并且您可以轻松地使用所有标准逻辑运算符).例如,这样的情况Binary如下:

let rec evalLogic e =
  // pattern matching
  |  Binary(e1, e2, op) -> op (evalLogic e1) (evalLogic e2)