How could we compute the length of a list? Without worrying yet about what lambda-calculus implementation we're using for the list, the basic idea would be to define this recursively:
- the empty list has length 0
- any non-empty list has length 1 + (the length of its tail)
+> the empty list has length 0
+
+> any non-empty list has length 1 + (the length of its tail)
In OCaml, you'd define that like this: