'Unpacking' 没有 case 语句的 SML 数据类型中的数据

Question

我有一个 SML 程序，它代表一种语言，其表达式由值组成：

datatype Value = IntVal of int
               | ListVal of Value list

datatype Exp = Const of Value
             | Plus of Exp * Exp
             | Minus of Exp * Exp
             | Times of Exp * Exp

我还在编写一个 eval 函数，将表达式转换为值。如果表达式是加号表达式（例如 Plus (Const (IntVal 1), Const (IntVal 1)) 表示 1+1），我只想取出存储在 IntVal 中的整数并将它们加在一起并 return 那个。

但据我所知，我必须有一个看似多余的 case 语句，只有一个 case 才能得到 IntVal 数据类型中的整数：

(*Evaluates an Exp and returns a Value*)
fun eval e =
  (*Evaluate different types of Exp*)
  case e of
      (*If it's a constant, then just return the Value*)
      Const v => v
      (*If it's a Plus, we want to add together the two Values*)
    | Plus (x,y) =>
         (*Case statement with only one case that seems redundant*)
         case (eval x, eval y) of
            (IntVal xVal, IntVal yVal) => IntVal (xVal + yVal)

没有简单的方法来简化这个吗？我想做这样的事情，这当然不是有效的 SML:

fun eval e =
  case e of
      Const v => v
    | Plus (x,y) => IntVal (eval x + eval x)

Answer 1

如果你想让你的 eval 函数变成 return 一个 int 并且你还没有弄清楚如何从 Value 得到一个 int它使用 ListVal 构造函数——仅提供与您的预期定义涵盖的情况相对应的模式就足够了。

fun eval (Const (IntVal v)) = v
|   eval (Plus (e1,e2)) = eval(e1) + eval(e2)
|   eval (Minus (e1,e2)) = eval(e1) - eval(e2)
|   eval (Times (e1,e2)) = eval(e1) * eval(e2);

SML/NJ 给出 Warning: match nonexhaustive - 但如果它符合您的意图，那么您可以忽略警告。

上面的代码 return 是 int。如果你想要 return 看起来像的值IntVal 3 然后你可以定义 3 个函数，这些函数采用 IntVals 和 return IntVals 对应于它们的和、差和乘积，并在右侧使用这些函数以上定义。

Answer 2

是的，至少有两种方法可以简化它：异常或 monad。

您遇到的问题是 eval (Const (ListVal [...])) 没有有意义的整数值。为了确保这仍然是一个 总函数 （所有输入值都会产生一个输出值，而不是 partial function），它的类型可以表示为：

val eval : Exp -> int option

您可以通过使用异常最轻松地实现这一点：

local
  fun eval' (Const (IntVal v)) = v
    | eval' (Const (ListVal _)) = raise Domain
    | eval' (Plus (e1, e2)) = eval' e1 + eval' e2
    | eval' (Minus (e1, e2)) = eval' e1 - eval' e2
    | eval' (Times (e1, e2)) = eval' e1 * eval' e2
in
  fun eval e = SOME (eval' e) handle Domain => NONE
end

或者您可以通过使递归函数复杂化来实现：

fun eval (Const (IntVal v)) = SOME v
  | eval (Const (ListVal _)) = NONE
  | eval (Plus (e1, e2)) =
    (case (eval e1, eval e2) of
          (SOME v1, SOME v2) => SOME (v1+v2)
        | _ => NONE)
  | eval (Minus (e1, e2)) =
    (case (eval e1, eval e2) of
          (SOME v1, SOME v2) => SOME (v1-v2)
       |  _ => NONE)
  | eval (Times (e1, e2)) =
    (case (eval e1, eval e2) of
          (SOME v1, SOME v2) => SOME (v1*v2)
        | _ => NONE)

显然这并不容易或漂亮。

改进此代码的一种方法是将常见的重复模式抽象为一个函数：

fun evalBinop (f, e1, e2) =
    case (eval e1, eval e2) of
         (SOME v1, SOME v2) => SOME (f (v1, v2))
       | _ => NONE
and eval (Const (IntVal v)) = SOME v
  | eval (Const (ListVal _)) = NONE
  | eval (Plus (e1, e2)) = evalBinop (op+, e1, e2)
  | eval (Minus (e1, e2)) = evalBinop (op-, e1, e2)
  | eval (Times (e1, e2)) = evalBinop (op*, e1, e2)

这里evalBinop依赖于对eval的回调，所以我让他们相互递归。我还依赖于将二元运算符解释为将元组作为参数的函数。

一项改进是制作更通用的辅助函数来处理 'a 选项 类型：

infix 3 >>=
fun NONE >>= _ = NONE
  | (SOME a) >>= f = f a

fun liftM2 f (opt1, opt2) =
    opt1 >>= (fn x1 => opt2 >>= (fn x2 => SOME (f (x1, x2))))

fun eval (Const (IntVal v)) = SOME v
  | eval (Const (ListVal _)) = NONE
  | eval (Plus (e1, e2)) = liftM2 (op+) (eval e1, eval e2)
  | eval (Minus (e1, e2)) = liftM2 (op-) (eval e1, eval e2)
  | eval (Times (e1, e2)) = liftM2 (op* ) (eval e1, eval e2)

此时，>>= 和 liftM2 是有用的函数，它们不依赖于计算表达式或应用整数运算符的概念。它们不存在于 Standard ML 的库中，但它们应该存在。此时我顺带re-invented monads.

最后一个改进是添加了一点语法糖，这很可能是矫枉过正：

infix 7 **
infix 6 ++
infix 6 --
val op** = liftM2 op*
val op++ = liftM2 op+
val op-- = liftM2 op-

fun eval (Const (IntVal v)) = SOME v
  | eval (Const (ListVal _)) = NONE
  | eval (Plus (e1, e2)) = eval e1 ++ eval e2
  | eval (Minus (e1, e2)) = eval e1 -- eval e2
  | eval (Times (e1, e2)) = eval e1 ** eval e2

（一些示例确切地说明了 >>= 和 liftM2 的作用...）

(* 'x >>= f' means:
 *     if x is 'NONE', just return NONE
 *     if x is 'SOME a', apply f to a, and expect f to return either 'SOME b' or 'NONE' *)
(* For example, this should give 'SOME 4': *)
val example_1 = SOME 3 >>= (fn x => SOME (x+1))

(* And these should both give 'NONE': *)
val example_2 = NONE >>= (fn x => SOME (x+1))
val example_3 = SOME 3 >>= (fn x => NONE)

(* If 'f : t1 * t2 -> t3', then 'liftM2 f : t1 option * t2 option -> t3 option' *)
val _ = op+ : int * int -> int
val _ = liftM2 op+ : int option * int option -> int option

(* For example *)
val example_4 = liftM2 op+ (SOME 3, SOME 4)  (* gives SOME 7 *)
val example_5 = liftM2 op- (SOME 10, NONE)   (* gives NONE *)
val example_6 = liftM2 op* (NONE, SOME 5)    (* gives NONE *)

'Unpacking' 没有 case 语句的 SML 数据类型中的数据

'Unpacking' the data in an SML DataType without a case statement

functional-programming

sml

ml