length function without recursion ocaml

I'm trying to rewrite the List.length function without using recursion. Here's my code:

(* 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 =
  let i = fold_left(fun x y -> Fun.const 1 :: y) [] ls in
  fold_left(fun x y -> x + y) 0 i

OCaml gave me an error on the last line fold_left(fun x y -> x + y) 0 i and saying my i here has type ('a -> int) list but an expression was expected of type int list, is there any way I can fix this? Thank you!


  • It's not entirely clear to me what you are trying to achieve with Fun.const, but you can actually achieve length with a single fold_left:

    let length l =
      fold_left (fun acc _ -> acc+1) 0 l