OCaml无高阶函数实现字符列表连续重复计数的方法

核心开发目标 #

• 输入：OCaml 字符列表，典型测试输入为 ['a'; 'a'; 'a'; 'a'; 'a'; 'b'; 'b'; 'b'; 'a'; 'd'; 'd'; 'd'; 'd']
• 输出：连续重复字符的计数元组列表，目标输出为 [(5, 'a'); (3, 'b'); (1, 'a'); (4, 'd')]
• 约束：实现过程不允许使用 fold、map 等高阶函数，适配OCaml不可变列表的遍历特性，不模拟C/Python的随机下标访问数组的操作逻辑

历次迭代的错误实现与问题定位 #

第一版：不完整的while循环实现 #

let to_run_length (lst : char list) : (int * char) list =
  match lst with
  | [] -> []
  | h :: t ->
      let count = int 0 in
      while t <> [] do
        if h = t then count := count + 1;
      done;

存在问题：

• 语法错误：引用初始化写法错误，let count = int 0 不符合OCaml语法，正确写法应为 let count = ref 0
• 类型不匹配：直接拿字符h和列表t做相等判断，静态类型检查无法通过
• 逻辑缺失：while循环内没有指针位移逻辑，无法逐节点遍历列表，且没有定义函数返回值

第二版：结合List.nth的引用计数实现 #

let rec to_run_length (lst : char list) : (int * char) list =
  let n = ref 0 in
  match lst with
  | [] -> []
  | h :: t ->
      if h = List.nth t 0 then n := !n + 1;
      (!n, h) :: to_run_length t

存在问题：

• 越界异常：递归到列表末尾时，剩余子列表t为空，List.nth t 0 会直接触发下标越界报错
• 逻辑失效：每次递归调用都会重新初始化引用n为0，无法累计连续字符的计数

第三版：无守卫条件的嵌套模式匹配实现 #

let rec to_run_length (lst : char list) : (int * char) list =
  match lst with
  | [] -> []
  | h :: t ->
      match to_run_length t with
      | [] -> []
      | (n, c) :: tail ->
          if h <> c then to_run_length t else (n + 1, c) :: tail

存在问题：

• 分支逻辑错误：当当前字符h和子列表递归结果的首字符c不相等时，直接返回to_run_length t，会丢失当前h对应的游程条目，输出结构完全不符合预期

最终可运行实现 #

let rec to_run_length (lst : char list) : (int * char) list =
  match lst with
  | [] -> []
  | h :: t ->
      match to_run_length t with
      | (n, c) :: tail when h = c -> (n + 1, h) :: tail
      | tail -> (1, h) :: tail

正确实现的核心逻辑要点 #

• 递归方向选择：从列表尾部向前递归处理，不需要额外维护可变引用，也不需要逐下标遍历的越界判断
• 守卫条件作用：当当前处理的字符h，与递归处理剩余子列表得到的游程首字符c完全一致时，直接将对应游程的计数加1，合并到结果中
• 新游程分支：如果递归返回的结果不满足“首字符与当前h相同”的条件（包括子列表递归结果为空、首字符与h不同两类场景），就将当前h作为计数为1的新游程，拼接到结果最前面
• 列表特性适配：完全依赖模式匹配解构列表结构，没有使用高阶函数、没有使用随机下标访问，符合入门阶段的代码约束

内容的提问来源于stack exchange，提问作者dauði