OCaml类型错误求助：表达式类型为'a list却期望'b->'c

错误提示翻译 #

该表达式类型为 'a list，但期望类型为 'b -> 'c

错误原因 #

你的aux递归函数在处理空列表分支时，错误地将列表l1当作函数来调用（l1 l2）。但l1是用来收集小于等于x元素的列表，并非函数，OCaml因此抛出类型不匹配的错误。

修正后的代码 #

let separe l x = 
  let rec aux l1 l2 l x = 
    match l with
    | [] -> (l1, l2)  (* 返回两个列表组成的元组，而非函数调用 *)
    | t::q when t <= x -> aux (t::l1) l2 q x
    | t::q -> aux l1 (t::l2) q x 
  in aux [] [] l x

补充说明 #

当前代码通过头插法收集元素，最终返回的l1和l2是原顺序的逆序。如果需要保持原列表的元素顺序，可以在返回时反转两个列表：

let separe l x = 
  let rec aux l1 l2 l x = 
    match l with
    | [] -> (List.rev l1, List.rev l2)
    | t::q when t <= x -> aux (t::l1) l2 q x
    | t::q -> aux l1 (t::l2) q x 
  in aux [] [] l x

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