(** 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


(** Question 2 *)

class memo_fibo = object (self)
  inherit fibo 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

let () =
  Printf.printf "Calcul naif: %d\n" ((new fibo)#compute 6) ;
  Printf.printf "Calcul mémoisé: %d\n" ((new memo_fibo)#compute 6)


(** Question 3 *)

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

(** Noter qu'on peut appliquer le foncteur sur une classe c qui contient
  * d'autres méthodes que #compute (par sous-typage) mais que la classe
  * renvoyée par le foncteur n'aura de toute façon que la méthode #compute.
  * Il ne me semble pas évident de corriger cela. *)

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


(** Question 3'
  *
  * Variante plus pragmatique, inspirée d'une suggestion d'Adrien Husson:
  * on continue d'écrire chaque classe mémoisée à la main (ce n'est donc
  * pas vraiment générique) mais on limite la quantité de code à recopier.
  * La fonction make_memo est une bonne idée facilement adaptable pour
  * mémoiser en programmation fonctionnelle. *)

let make_memo () =
  let memo = Hashtbl.create 47 in
    fun f n ->
      try Hashtbl.find memo n with Not_found ->
        let r = f n in
          Hashtbl.add memo n r ;
          r

class memo_fibo' = object
  inherit fibo as super
  val memoizer = make_memo ()
  method compute n = memoizer super#compute n
end

class memo_fact' = object
  inherit fact as super
  val memoizer = make_memo ()
  method compute n = memoizer super#compute n
end

let () =
  Printf.printf "Fibo mémoisé (variante): %d\n" ((new memo_fibo')#compute 6) ;
  Printf.printf "Fact mémoisé (variante): %d\n" ((new memo_fact')#compute 6)