(** Programmation Avancée, TP2, exercice 1 *)

class fact = object (self)
  method compute n =
    if n = 0 then 1 else n * self#compute (n-1)
end

class fibo = object (self)
  method compute n =
    Printf.printf "fibo#compute %d\n" n ;
    if n <= 1 then 1 else
      self#compute (n-2) + self#compute (n-1)
end


module type T = sig
  class c : object
    method compute : int -> int
  end
end

module Memo (M:T) : T = struct
  class c = object
    inherit M.c as super
    val memo = Hashtbl.create 100
    method compute n =
      try Hashtbl.find memo n with Not_found ->
        let r = super#compute n in
          Hashtbl.add memo n r ;
          r
  end
end

let () =
  let module M = Memo(struct class c = fibo end) in
  Printf.printf "Fibo mémoisé: %d\n" ((new M.c)#compute 6) ;
  let module M = Memo(struct class c = fact end) in
  Printf.printf "Fact mémoisé: %d\n" ((new M.c)#compute 6)