如何在OCaml中无递归实现List.length并修复类型错误？

你的代码报错核心原因是：第一个fold_left调用生成的是函数列表而非整数列表。Fun.const 1返回的是类型为'a -> int的函数（不管输入是什么都返回1），而非直接的整数1，导致变量i的类型是('a -> int) list，和后续求和fold_left需要的int list类型不匹配。

修复方案一：高效的单次遍历实现 #

直接通过fold_left的累加器完成计数，无需生成中间列表，这是最优的非递归实现：

(* given *)
type 'a list =
  | []
  | (::) of 'a * 'a list
let nil : 'a list = []
let cons (hd : 'a) (tl : 'a list): 'a list = hd :: tl

let length (ls : 'a list): int =
  List.fold_left (fun acc _ -> acc + 1) 0 ls

这里累加器acc初始值为0，每遍历一个元素就加1，遍历完成后直接得到列表长度，时间复杂度O(n)，空间复杂度O(1)。

修复方案二：生成整数列表后求和（冗余但符合你的思路） #

如果你坚持要通过生成列表再求和的方式实现，只需把Fun.const 1替换为直接的整数1，确保中间列表是int list类型：

let length (ls : 'a list): int =
  let i = List.fold_left (fun x _ -> 1 :: x) [] ls in
  List.fold_left (fun x y -> x + y) 0 i

这种方式会先遍历列表生成全是1的列表，再遍历一次求和，时间复杂度O(n)，空间复杂度O(n)，属于冗余实现，但能解决类型错误问题。

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