#load "unix.cma";;
Unix.gettimeofday;;
Unix.gettimeofday ();;
let time f a =
  let s = Unix.gettimeofday () in
  let ret = f a in
  (ret, Unix.gettimeofday () -. s);;
let rec fib n = if n < 2 then n else (fib (n - 1) + fib (n - 2));;
fib 20;;
time fib 20;;
time fib 35;;
let rec fibpair n = if n < 1 then (0, 1) else
  let (f1, f2) = fibpair (n - 1) in (f2, f1 + f2);;
fibpair 20;;
fibpair 35;;
let fib2 n = fst (fibpair n);;
fib2 35;;
time fib2 35;;

let sum xs = List.fold_left (+.) 0. xs;;
let average xs = sum xs /. float_of_int (List.length xs);;
let rec ns = if n = 0 then [] else (float_oif_int n) :: (ns (n - 1));;
let rec ns n = if n = 0 then [] else (float_oif_int n) :: (ns (n - 1));;
let rec ns n = if n = 0 then [] else (float_of_int n) :: (ns (n - 1));;
ns 50;;
average (ns 100000);;
let rec sumlen = function
  [] -> (0., 0)
| h :: t -> let (s,l) = sumlen t in (s +. h, l + 1);;
let average1 l = let (s,l) = sumlen l in s /. float_of_int l;;
average1 (ns 100000);;
time average1 (ns 100000);;
time average (ns 100000);;
time average1 (ns 1000000);;
time average (ns 1000000);;

let rec range m n = if m >= n then []
  else m :: range (m + 1) n;;
let range_tl m n =
  let rec range acc m n =
    if m >= n then acc else range ((n - 1) :: acc) m (n - 1) in
  range [] m n;;
range 5 10;;
range_tl 5 10;;
range 5 1000000;;
range_tl 5 1000000;;
range 5 100000;;
time (range 5) 100000;;
snd (time (range 5) 100000);;
snd (time (range_tl 5) 100000);;
let rec rev = function [] -> [] | h :: t -> rev t @ [h];;
let rec rev2 acc = function [] -> acc | h :: t -> rev (h :: acc) t;;
let rec rev2 acc = function [] -> acc | h :: t -> rev2 (h :: acc) t;;
rev (range_tl 5 100000);;
rev (range_tl 5 1000);;
rev2 [] (range_tl 5 1000);;
time rev (range_tl 5 1000);;
snd (time rev (range_tl 5 1000));;
snd (time (rev2 []) (range_tl 5 1000));;
let rev3 l = List.fold_left (fun sf h -> h :: sf) [] l;;
snd (time rev3 (range_tl 5 1000));;