| 1 |
2de7fa82
|
ploc
|
(* Le type abstrait des tables utilisées dans la memoization des fonctions. *)
|
| 2 |
|
|
(* Permet de mémoriser des appels de fonctions efficacement sous la forme *)
|
| 3 |
|
|
(* de couples (argument de type 'a, résultat de type 'b). *)
|
| 4 |
|
|
(* Chaque table devra être associée à une fonction unique. *)
|
| 5 |
ca7ff3f7
|
Lélio Brun
|
type ('a, 'b) t
|
| 6 |
2de7fa82
|
ploc
|
|
| 7 |
|
|
(* Création d'une table vide. *)
|
| 8 |
|
|
(* Paramètres : *)
|
| 9 |
|
|
(* - aucun *)
|
| 10 |
|
|
(* Résultat : *)
|
| 11 |
|
|
(* - une table vide destinée à mémoriser uniquement les appels *)
|
| 12 |
|
|
(* d'une fonction quelconque. *)
|
| 13 |
ca7ff3f7
|
Lélio Brun
|
val create : unit -> ('a, 'b) t
|
| 14 |
2de7fa82
|
ploc
|
|
| 15 |
ca7ff3f7
|
Lélio Brun
|
val reset : ('a, 'b) t -> unit
|
| 16 |
2de7fa82
|
ploc
|
|
| 17 |
|
|
(* Utilisation d'une version "memoizée" d'une fonction à un paramètre. *)
|
| 18 |
|
|
(* Paramètres : *)
|
| 19 |
|
|
(* - une table t de mémoization : ('a, 'b) t *)
|
| 20 |
|
|
(* - une fonction f à mémoizer : 'a -> 'b *)
|
| 21 |
|
|
(* Précondition : *)
|
| 22 |
|
|
(* - le paramètre f doit être l'identificateur d'une fonction définie *)
|
| 23 |
|
|
(* auparavant. Les fonctions "dynamiques" (fun x -> ...) sont interdites. *)
|
| 24 |
|
|
(* Résultat : *)
|
| 25 |
|
|
(* - une fonction au contrat identique à celui de la fonction f, *)
|
| 26 |
|
|
(* mais dont la complexité en temps est quasi-linéaire, au prix d'une *)
|
| 27 |
|
|
(* occupation mémoire importante néanmoins. *)
|
| 28 |
|
|
(* Erreur : *)
|
| 29 |
|
|
(* - exception Failure levée en cas d'utilisation d'une même table *)
|
| 30 |
|
|
(* avec plusieurs fonctions différentes. *)
|
| 31 |
ca7ff3f7
|
Lélio Brun
|
val apply : ('a, 'b) t -> ('a -> 'b) -> 'a -> 'b
|
| 32 |
2de7fa82
|
ploc
|
|
| 33 |
|
|
(* Utilisation d'une version "memoizée" d'une fonction à deux paramètres. *)
|
| 34 |
|
|
(* Paramètres : *)
|
| 35 |
|
|
(* - une table t de mémoization : ('a * 'b, 'c) t *)
|
| 36 |
|
|
(* - une fonction f à mémoizer : 'a -> 'b -> 'c *)
|
| 37 |
|
|
(* Résultat : *)
|
| 38 |
|
|
(* - une fonction au contrat identique à celui de la fonction f, *)
|
| 39 |
|
|
(* mais dont la complexité en temps est quasi-linéaire, au prix d'une *)
|
| 40 |
|
|
(* occupation mémoire importante néanmoins. *)
|
| 41 |
|
|
(* Erreur : *)
|
| 42 |
|
|
(* - exception Failure levée en cas d'utilisation d'une même table *)
|
| 43 |
|
|
(* avec plusieurs fonctions différentes. *)
|
| 44 |
ca7ff3f7
|
Lélio Brun
|
val apply2 : ('a * 'b, 'c) t -> ('a -> 'b -> 'c) -> 'a -> 'b -> 'c
|
| 45 |
2de7fa82
|
ploc
|
|
| 46 |
ca7ff3f7
|
Lélio Brun
|
val apply3 :
|
| 47 |
|
|
('a * 'b * 'c, 'd) t -> ('a -> 'b -> 'c -> 'd) -> 'a -> 'b -> 'c -> 'd
|
| 48 |
2de7fa82
|
ploc
|
|
| 49 |
ca7ff3f7
|
Lélio Brun
|
val fold : ('a, 'b) t -> ('a -> 'b -> 'c -> 'c) -> 'c -> 'c
|