The Beauty of Functional Programming

fp.ml

(* syntactically defining cons as list concat *)
let cons a b = a::b

(* sum without foldr *)
let rec sum lst =
  match lst with
  | [] -> 0
  | h::t -> h + sum t

(* general case, foldr *)
let rec foldr f lst a =
  match lst with
  | [] -> a
  | h::t -> f h (foldr f t a)

(* add (+) *)
let add a b = a + b

(* sum built with foldr *)
let foldr_sum lst = foldr add lst 0

(* mult built with foldr *)
let mult a b = a * b
let foldr_mult lst = foldr mult lst 1

let count a n = n + 1
let foldr_length lst = foldr count lst 0

let rec length lst =
  match lst with
  | [] -> 0
  | h::t -> 1 + length t

let doubleandcons n lst = cons (2 * n) lst
let doubleall lst = foldr doubleandcons lst []

let double n = 2 * n
let fandcons f el lst = cons (f el) lst
let doubleandcons = fandcons double

let rec map f lst =
  match lst with
  | [] -> []
  | h::t -> f h :: map f t

let foldr_map f lst = foldr (fandcons f) lst []
let doubleall lst = map double lst

Demonstrating the power of functional programming and general purpose functions by building up map using foldr.
A couple of examples of foldr sprinkled in there.