如何修复OCAML中元组模式匹配的递归调用报错

错误根因 #

• 类型不匹配：你声明的encodeHelper第三个参数类型为('a * int) option，要求该参数只能是None或者被Some包裹的('a * int)元组，你在所有递归调用位置都直接传入了裸元组，没有加Some构造器，因此触发类型错误。
• 变量未定义：第5行hd1::tl, None分支中使用了未声明的变量k，此处应该取当前遍历到的列表头部元素hd1。
  另外原代码第4行的as currElement没有实际作用，可以直接删除。

修复后完整代码 #

let rec encodeHelper (l : 'a list) (curr : ('a * int) list) (currElement : ('a * int) option) =
   match l, currElement with 
   | [], None -> curr
   | [], Some(k) -> curr @ [(fst k, snd k)]
   | hd1::tl, None -> encodeHelper tl curr (Some (hd1, 1))
   | hd::tl, Some(k) -> 
      let element_ = fst k and
      amount = snd k in
      if element_ = hd
         then encodeHelper tl curr (Some (element_, amount + 1))
      else
         encodeHelper tl (curr @ [(element_, amount)]) (Some (hd, 1))

可选优化建议 #

当前代码使用@拼接列表的时间复杂度为O(n)，累计递归调用后整体效率较低，如果需要优化可以先把元素塞到列表头部，遍历完成后统一反转，性能会更好。

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