Project

General

Profile

Download (3.11 KB) Statistics
| Branch: | Tag: | Revision:
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;;
(8-8/9)