如何修正OCaml代码以得到预期的正确输出结果？

原代码 #

let a = ref 0

type t = 
  | Int of string
  | Add of t * t

let rec makestring_t = function
  | Int a -> a
  | Add (b, c) ->
    incr a;
    "(Add" ^ string_of_int !a ^ 
    " (" ^ makestring_t b ^ 
    " " ^ makestring_t c ^ "))"

let () = 
  let a = Add (Int "1", Add (Int "2", Int "3")) in 
  print_string (makestring_t a)

当前输出 #

(Add2 (1 (Add2 (2 3))))

期望输出 #

(Add1 (1 (Add2 (2 3))))

问题原因 #

核心问题是OCaml的字符串拼接运算符^为右结合，表达式会从右往左计算。外层Add分支中，string_of_int !a的计算会滞后于递归调用makestring_t c，导致内层Add的incr a修改了全局计数器的值，最终外层编号也被覆盖为2。此外全局引用变量易被意外修改，多次调用会导致计数器累积。

解决方案 #

方案1：最小修改（保存当前计数器值） #

在Add分支中，递增计数器后立即将当前值存入局部变量，避免后续递归修改影响当前编号：

let a = ref 0

type t = 
  | Int of string
  | Add of t * t

let rec makestring_t = function
  | Int a -> a
  | Add (b, c) ->
    incr a;
    let current_num = !a in  (* 保存当前计数器值，隔离后续修改 *)
    "(Add" ^ string_of_int current_num ^ 
    " (" ^ makestring_t b ^ 
    " " ^ makestring_t c ^ "))"

let () = 
  let expr = Add (Int "1", Add (Int "2", Int "3")) in  (* 重命名局部变量避免混淆 *)
  print_string (makestring_t expr)

方案2：函数式实现（参数传递计数器） #

消除全局变量，将计数器作为函数参数传递，彻底避免副作用：

type t = 
  | Int of string
  | Add of t * t

let rec makestring_t counter = function
  | Int a -> a
  | Add (b, c) ->
    incr counter;
    let current_num = !counter in
    let b_str = makestring_t counter b in
    let c_str = makestring_t counter c in
    "(Add" ^ string_of_int current_num ^ " (" ^ b_str ^ " " ^ c_str ^ "))"

let () = 
  let expr = Add (Int "1", Add (Int "2", Int "3")) in 
  print_string (makestring_t (ref 0) expr)

两种方案均可得到期望输出：

(Add1 (1 (Add2 (2 3))))

内容的提问来源于stack exchange，提问作者wang kai