OCaml列表压缩问题：修复compress函数的Failure "nth"异常

原代码问题分析 #

你写的compress函数抛出Failure "nth"异常，核心问题有两点：

1. 逻辑错误：List.filteri的回调中，List.nth list i就是当前遍历的元素el，compare结果永远为0，过滤条件永远不满足，最终会返回空列表。
2. 索引越界：如果你的本意是比较当前元素与前一个元素（比如写List.nth list (i-1)），当i=0时，i-1=-1是无效索引，直接触发nth函数的异常。

你的需求是移除连续重复的元素，只保留每个连续重复序列的首个元素，以下是两种正确的实现方式：

递归实现（最直观） #

let rec compress = function
  | [] -> []
  | [x] -> [x]
  | x :: y :: rest ->
      if x = y then compress (x :: rest)
      else x :: compress (y :: rest)

逻辑说明 #

• 空列表直接返回空；单个元素的列表直接返回自身。
• 当列表有至少两个元素时：
  • 如果第一个元素x和第二个元素y相同，跳过y，继续处理x与剩余列表的组合。
  • 如果不同，保留x，继续处理y与剩余列表的组合。

基于fold_left的实现 #

let compress list =
  let folder acc el =
    match acc with
    | [] -> [el]
    | last :: _ -> if last = el then acc else el :: acc
  in
  List.rev (List.fold_left folder [] list)

逻辑说明 #

• 用fold_left遍历列表，累积结果到acc中（初始为空）。
• 每次遍历元素el时，检查acc的最后一个元素：
  • 如果acc为空，直接将el加入。
  • 如果el和acc的最后一个元素相同，不修改acc。
  • 如果不同，将el加入acc的头部。
• 最后反转acc，得到正确顺序的结果。

测试验证 #

调用函数测试你的输入列表：

compress ["a"; "a"; "a"; "c"; "b"; "c"; "c"; "a"; "a"; "d"; "x"; "e"; "e"; "e"]

返回结果为：["a"; "c"; "b"; "c"; "a"; "d"; "x"; "e"]，完全符合需求。

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