Project

General

Profile

Download (3.09 KB) Statistics
| Branch: | Tag: | Revision:
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