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