メモ化関数

memorize2.ml

let ( >> ) f g x = g (f x)

let collatz f = function
  | 1L -> 1
  | n when Int64.rem n 2L = 0L -> 1 + f (Int64.div n 2L)
  | n when Int64.rem n 2L = 1L -> 1 + f (Int64.add (Int64.mul 3L n) 1L)

let rec memorize cache f n =
  try Hashtbl.find cache n with
  | Not_found ->
      let result = f (memorize cache f) n in
      Hashtbl.add cache n result;
      result

let rec maximum acc f = function
  | 1 -> acc
  | n ->
      if f n > f acc then maximum n f (n - 1)
      else maximum acc f (n - 1)

let maximum = maximum 1

let _ =
  let cache = Hashtbl.create 2000000 in
  print_int (maximum (Int64.of_int >> memorize cache collatz) 1000000);
  print_newline ()