OCaml类型识别错误疑问：为何expr元素被判定为map类型？

先看你的代码：

module Value =
struct
  type t = Int of int
end

module M = Map.Make(String)

type expr = 
  | Num of int
  | Add of expr * expr

type t = Value.t M.t (* Value.t is Int of int *)

let rec add_map (st: string list) (e: expr list) (s: t): t =
  match st with
  | [] -> s
  | s1::st -> 
    match e with
    | e1::e -> 
      M.add s1 e1 s; 
      add_map st e s;;

错误原因 #

代码里存在明确的类型不匹配：

• s的类型是t，也就是Value.t M.t（键为string，值为Value.t）
• M.add的签名是string -> 'a -> 'a M.t -> 'a M.t，结合s的类型，这里的'a被固定为Value.t，所以M.add的第二个参数必须是Value.t类型
• 但你传入的e1是expr类型（来自expr list），和Value.t完全不兼容

OCaml的错误提示看起来像是把e1识别为t类型，其实是类型推断过程中因不匹配产生的误导性提示——因为函数返回值是t，OCaml会强制M.add的结果是t，反向推断e1应该是Value.t，但你声明e是expr list，两者冲突，才出现这种看似矛盾的错误信息。

解决方法 #

需要把expr类型转换成Value.t类型，先写一个求值函数计算表达式结果：

let rec eval_expr (e: expr): Value.t =
  match e with
  | Num n -> Value.Int n
  | Add (e1, e2) ->
    match eval_expr e1, eval_expr e2 with
    | Value.Int a, Value.Int b -> Value.Int (a + b)

然后修改add_map函数，传入转换后的值：

let rec add_map (st: string list) (e: expr list) (s: t): t =
  match st with
  | [] -> s
  | s1::st_rest -> 
    match e with
    | e1::e_rest -> 
      let value = eval_expr e1 in
      let new_s = M.add s1 value s in
      add_map st_rest e_rest new_s
    | [] -> s (* 处理st和e长度不一致的情况，避免崩溃 *)

这样M.add的第二个参数就变成了Value.t类型，和s的类型匹配，错误即可消失。

内容的提问来源于stack exchange，提问作者newb hi