20131021:TP:OCaml:More:Records
Sommaire
Implémentation des files
Pour cette première partie, nous allons implémenter des files FIFO en se basant sur la structure classique des listes circulaires.
Pour ce faire, nous aurons besoin de:
- d'une structure de liste modifiables;
- de valeur qui se référencent elles même.
Pour toute la section courante (file) nous travaillerons dans un module que nous nommerons MyQueue et dont voici le fichier d'interface (myQueue.mli):
(* Interface for module MyQueue *) (* Opaque Abstract Type *) type 'a queue (* Operations *) val create : unit -> 'a queue val is_empty : 'a queue -> bool val length : 'a queue -> int val push : 'a queue -> 'a -> unit val take : 'a queue -> 'a
Bases
Voici un type pour des listes modifiables (structurellement, nous n'avons pas besoin de changer le contenu):
type 'a cell = { content : 'a; mutable next : 'a cell; }
Le type est polymorphe et le champ next est modifiable. Par contre, nous ne pouvons pas représenter une liste vide avec ce type. Comme la liste vide n'existe pas, on ne peut représenter que des listes circulaires avec.
Voici maintenant des exemples de listes circulaires construites avec ce type:
(* une liste de 1 element *) let rec l1 = { content = 42; next = l1; } (* une liste a 2 elements *) let rec l2 = { content = 1; next = { content = 2; next = l2; }; }
À titre d'exercice, on va écrire une fonction qui prend une liste classique et renvoie une liste circulaire avec les mêmes éléments.
- Écrire la fonction suivante:
val build_circular : 'a list -> 'a cell
Des files
Pour la construction des files, nous allons ajouter une sentinelle avec la taille et on utilisera le type 'a option pour régler le problème de la file vide. Voici le type avec la fonction de création:
type 'a queue = { mutable size : int; mutable cell : 'a cell option; } let create () = { size = 0; cell = None; }
Le type 'a option est un type prédéfini très simpe, permettant de renvoyer rien ou quelque chose. Voici sa définition:
type 'a option = | None | Some of 'a
On rappelle la construction des files:
- les éléments sont chaînées dans l'ordre d'arrivée, chaque élément (sauf le plus récent) pointe sur l'élément arrivé après lui;
- l'entrée de la liste pointe sur l'élément le plus récent (celui-ci pointe sur le plus ancien, la liste est circulaire);
- l'ajout d'élément se fait entre l'élément le plus récent (le point d'entrée) et le plus ancien (le suivant du point d'entrée);
- l'élément partant est toujours le suivant du point d'entrée (c'est le plus ancien).
Voici une version en pseudo code des deux opérations principales:
push(q, x) {
q.size <- q.size + 1;
if q is empty then {
q.cell <- new circular cell with x;
} else {
q.cell.next <- new cell with x and q.cell.next;
q.cell <- q.cell.next;
}
}
// precondition: q.size > 0
take(q) {
res = q.cell.next.content;
q.size <- q.size - 1;
if q.size = 0 then {
q.cell <- empty cell;
} else {
q.cell.next <- q.cell.next.next;
}
return res;
}
Vous pouvez maintenant adapter ces opérations à notre type (attention le champ cell est un type option !)
- Écrire les fonctions suvantes:
val is_empty : 'a queue -> bool val length : 'a queue -> int val push : 'a queue -> 'a -> unit val take : 'a queue -> 'a
Test simple
Pour tester une file, le plus simple est d'y insérer une série de valeurs (dont l'ordre est facile à retrouver) et de les re-sortir pour vérifier l'ordre.
Voici un petit module de test (à mettre dans le fichier test_MyQueue.ml pour valider votre module MyQueue.
(* Testing MyQueue *) (* file: test_MyQueue.ml *) let main () = let q = MyQueue.create () in begin for i=0 to 10 do MyQueue.push q i done; while not (MyQueue.is_empty q) do Printf.printf "%d\n" (MyQueue.take q) done; exit 0; end let _ = main ()
Maintenant, vous devriez pouvoir compiler et tester (voici un exemple avec ocamlbuild):
unshell> ls myQueue.ml myQueue.mli test_MyQueue.ml unshell> ocamlbuild test_MyQueue.native [compiler doing its job] unshell> ./test_MyQueue.native 0 1 2 3 4 5 6 7 8 9 10 unshell>
Indexation de caractères
Notre objectif maintenant est d'indexer les caractères apparaissant dans un text: nous voulons stocker, dans un tableau de files, la suite des positions occupées par chaque caractère.
Dans ce tableau d'index, l'on doit trouver à la case i la file contenant les positions du caractère de code ASCII i.
- Écrire les fonctions suivantes:
(* build an empty index (array 256 cell with an empty queue) *) val create_index : unit -> 'a MyQueue.queue array (* add_entry index c pos : add pos to the queue for char c *) val add_entry : 'a MyQueue.queue array -> char -> 'a -> unit (* build_index s : traverse the string s and return the index with pos for all char *) val build_index : string -> int MyQueue.queue array
Voici un peu de code pour un test simple:
(* char_index.ml *) let create_index () = (* FIX ME *) let add_entry index c pos = (* FIX ME *) let build_index text = (* FIX ME *) let read_file name = let rec reader accu cin = try reader (accu ^ (input_line cin) ^ "\n") cin with | End_of_file -> accu in reader "" (open_in name) let simple_output index = begin Format.printf "@[<b>"; for i = 0 to 255 do Format.printf "| %-7s : %3d@;" (Printf.sprintf "%C" (Char.chr i)) (MyQueue.length index.(i)) done; Format.printf "@]@."; end let main () = begin if Array.length Sys.argv < 2 then begin Printf.eprintf "Need a file name\n"; exit 1; end; let index = build_index (read_file Sys.argv.(1)) in simple_output index; exit 0 end let _ = main ()
Et maintenant, testez :
unshell> ls
_build/ char_index.ml myQueue.ml myQueue.mli test_MyQueue.ml test_MyQueue.native
unshell> ocamlbuild -clean
Finished, 0 targets (0 cached) in 00:00:00.
00:00:00 0 (0 ) STARTING
unshell> ocamlbuild char_index.native
Finished, 8 targets (0 cached) in 00:00:00
unshell> ./char_index.native myQueue.mli
| '\000' : 0 | '\001' : 0 | '\002' : 0 | '\003' : 0
| '\004' : 0 | '\005' : 0 | '\006' : 0 | '\007' : 0
| '\b' : 0 | '\t' : 0 | '\n' : 11 | '\011' : 0
| '\012' : 0 | '\r' : 0 | '\014' : 0 | '\015' : 0
| '\016' : 0 | '\017' : 0 | '\018' : 0 | '\019' : 0
| '\020' : 0 | '\021' : 0 | '\022' : 0 | '\023' : 0
| '\024' : 0 | '\025' : 0 | '\026' : 0 | '\027' : 0
| '\028' : 0 | '\029' : 0 | '\030' : 0 | '\031' : 0
| ' ' : 45 | '!' : 0 | '"' : 0 | '#' : 0
| '$' : 0 | '%' : 0 | '&' : 0 | '\'' : 8
| '(' : 3 | ')' : 3 | '*' : 6 | '+' : 0
| ',' : 0 | '-' : 6 | '.' : 0 | '/' : 0
| '0' : 0 | '1' : 0 | '2' : 0 | '3' : 0
| '4' : 0 | '5' : 0 | '6' : 0 | '7' : 0
| '8' : 0 | '9' : 0 | ':' : 5 | ';' : 0
| '<' : 0 | '=' : 0 | '>' : 6 | '?' : 0
| '@' : 0 | 'A' : 1 | 'B' : 0 | 'C' : 0
| 'D' : 0 | 'E' : 0 | 'F' : 0 | 'G' : 0
| 'H' : 0 | 'I' : 1 | 'J' : 0 | 'K' : 0
| 'L' : 0 | 'M' : 1 | 'N' : 0 | 'O' : 2
| 'P' : 0 | 'Q' : 1 | 'R' : 0 | 'S' : 0
| 'T' : 1 | 'U' : 0 | 'V' : 0 | 'W' : 0
| 'X' : 0 | 'Y' : 0 | 'Z' : 0 | '[' : 0
| '\\' : 0 | ']' : 0 | '^' : 0 | '_' : 1
| '`' : 0 | 'a' : 19 | 'b' : 2 | 'c' : 3
| 'd' : 1 | 'e' : 26 | 'f' : 2 | 'g' : 1
| 'h' : 2 | 'i' : 5 | 'j' : 0 | 'k' : 1
| 'l' : 8 | 'm' : 2 | 'n' : 6 | 'o' : 5
| 'p' : 6 | 'q' : 7 | 'r' : 5 | 's' : 4
| 't' : 12 | 'u' : 19 | 'v' : 5 | 'w' : 0
| 'x' : 0 | 'y' : 4 | 'z' : 0 | '{' : 0
| '|' : 0 | '}' : 0 | '~' : 0 | '\127' : 0
| '\128' : 0 | '\129' : 0 | '\130' : 0 | '\131' : 0
| '\132' : 0 | '\133' : 0 | '\134' : 0 | '\135' : 0
| '\136' : 0 | '\137' : 0 | '\138' : 0 | '\139' : 0
| '\140' : 0 | '\141' : 0 | '\142' : 0 | '\143' : 0
| '\144' : 0 | '\145' : 0 | '\146' : 0 | '\147' : 0
| '\148' : 0 | '\149' : 0 | '\150' : 0 | '\151' : 0
| '\152' : 0 | '\153' : 0 | '\154' : 0 | '\155' : 0
| '\156' : 0 | '\157' : 0 | '\158' : 0 | '\159' : 0
| '\160' : 0 | '\161' : 0 | '\162' : 0 | '\163' : 0
| '\164' : 0 | '\165' : 0 | '\166' : 0 | '\167' : 0
| '\168' : 0 | '\169' : 0 | '\170' : 0 | '\171' : 0
| '\172' : 0 | '\173' : 0 | '\174' : 0 | '\175' : 0
| '\176' : 0 | '\177' : 0 | '\178' : 0 | '\179' : 0
| '\180' : 0 | '\181' : 0 | '\182' : 0 | '\183' : 0
| '\184' : 0 | '\185' : 0 | '\186' : 0 | '\187' : 0
| '\188' : 0 | '\189' : 0 | '\190' : 0 | '\191' : 0
| '\192' : 0 | '\193' : 0 | '\194' : 0 | '\195' : 0
| '\196' : 0 | '\197' : 0 | '\198' : 0 | '\199' : 0
| '\200' : 0 | '\201' : 0 | '\202' : 0 | '\203' : 0
| '\204' : 0 | '\205' : 0 | '\206' : 0 | '\207' : 0
| '\208' : 0 | '\209' : 0 | '\210' : 0 | '\211' : 0
| '\212' : 0 | '\213' : 0 | '\214' : 0 | '\215' : 0
| '\216' : 0 | '\217' : 0 | '\218' : 0 | '\219' : 0
| '\220' : 0 | '\221' : 0 | '\222' : 0 | '\223' : 0
| '\224' : 0 | '\225' : 0 | '\226' : 0 | '\227' : 0
| '\228' : 0 | '\229' : 0 | '\230' : 0 | '\231' : 0
| '\232' : 0 | '\233' : 0 | '\234' : 0 | '\235' : 0
| '\236' : 0 | '\237' : 0 | '\238' : 0 | '\239' : 0
| '\240' : 0 | '\241' : 0 | '\242' : 0 | '\243' : 0
| '\244' : 0 | '\245' : 0 | '\246' : 0 | '\247' : 0
| '\248' : 0 | '\249' : 0 | '\250' : 0 | '\251' : 0
| '\252' : 0 | '\253' : 0 | '\254' : 0 | '\255' : 0
unshell>
