Computing Length

Naive recursive length: nlength

let rec nlength = function
  | [] -> 0
  | x :: xs -> 1 + nlength xs
(* val nlength : 'a list -> int = <fun> *)

This is polymorphic and applies to all lists regardless of element type. A trace:

nlength [a; b; c] => 1 + nlength [b; c]
                  => 1 + (1 + nlength [c])
                  => 1 + (1 + (1 + nlength []))
                  => 1 + (1 + (1 + 0))
                  => 3

Like nsum, this function is not tail-recursive. The additions nest — 1 + (1 + (1 + 0)) — requiring O(n) space on the call stack.

Iterative length with accumulator: addlen

let rec addlen n = function
  | [] -> n
  | x :: xs -> addlen (n + 1) xs
(* val addlen : int -> 'a list -> int = <fun> *)

The function keyword introduces an extra (unnamed) argument that is pattern-matched. The integer accumulator n tracks the count so far:

addlen 0 [a; b; c] => addlen 1 [b; c]
                    => addlen 2 [c]
                    => addlen 3 []
                    => 3

The recursive calls do not nest — this is iterative and uses O(1) space.

Wrapper function

The efficient length function wraps addlen with an initial accumulator of zero:

let length xs = addlen 0 xs
(* val length : 'a list -> int = <fun> *)

Comparison

Function	Recursion	Time	Space
nlength	Nested (not tail-recursive)	O(n)	O(n)
addlen/length	Iterative (tail-recursive)	O(n)	O(1)

Both functions take O(n) time because you must examine each element to count it — there is no way around that. The accumulator improves space complexity only.

Why nlength is “naive”

The function nlength has the same flaw as nsum: it builds up deferred work (the 1 + expressions) that cannot be resolved until the base case is reached. For a list of length 10000, the call stack holds 10000 pending additions — a stack overflow waiting to happen. The iterative version addlen resolves the addition immediately (n + 1) and passes the result forward.