OCaml中如何使用fold_left实现指定长度子列表索引查找

完全可以用fold_left实现和你现有逻辑一致的函数。
你写的原生递归函数逻辑很清晰：从传入的起始索引开始遍历元素为整型列表的列表，遇到第一个长度等于目标值的子列表就返回当前索引，遍历完所有元素都没匹配到就抛出Failure "Not found"异常。
用fold_left实现的核心思路是在折叠过程中维护二元组状态：第一个元素记录当前遍历位置的索引，第二个元素用option类型存储已经找到的匹配结果——一旦找到符合条件的子列表，后续遍历就不再更新结果字段，实现和原递归提前返回等价的效果。

实现代码 #

let search x lst start_idx =
  let (_, result) =
    List.fold_left
      (fun (curr_idx, found) sub ->
        match found with
        | Some _ -> (curr_idx + 1, found)
        | None ->
          if List.length sub = x then
            (curr_idx + 1, Some curr_idx)
          else
            (curr_idx + 1, None))
      (start_idx, None)
      lst
  in
  match result with
  | Some idx -> idx
  | None -> raise (Failure "Not found")
;;

运行效果 #

和你原函数的调用方式、返回结果完全一致：

utop # search 2 [ [1;2];[1;2;3] ] 0 ;;
- : int = 0

如果平时使用都是从索引0开始查找，也可以把起始索引参数内置，简化调用方式：

let search x lst =
  (* 内置初始索引为0 *)
  let (_, result) = List.fold_left
    (fun (curr_idx, found) sub ->
      match found with
      | Some _ -> (curr_idx + 1, found)
      | None -> if List.length sub = x then (curr_idx + 1, Some curr_idx) else (curr_idx + 1, None))
    (0, None)
    lst
  in
  match result with
  | Some idx -> idx
  | None -> raise (Failure "Not found")
;;

这个版本调用时不需要手动传末尾的0参数，直接写search 2 [ [1;2];[1;2;3] ]就能得到同样的返回值。

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