Écrire un générateur de générateur aléatoire linéaire. L'invocation engendre_alea a b c retourne une fonction prenant un paramètre n et le convertissant en un entier de [0...n[
Testez ainsi votre solution:
let alea1 = engendre_alea 17 251 16384 and alea2 = engendre_alea 16001 253 16384 in for i = 0 to 50 do print_int (alea1 100); print_string ", "; print_int (alea2 100); print_string ", " done;; 51, 53, 18, 58, 21, 15, 84, 24, 35, 85, 74, 14, 21, 79, 16, 12, 39, 81, 54, 18, 49, 7, 48, 32, 79, 25, 42, 70, 89, 67, 96, 16, 23, 17, 70, 86, 41, 91, 76, 48, 87, 73, 90, 34, 21, 6 3, 72, 28, 71, 61, 50, 46, 13, 83, 84, 72, 75, 97, 18, 6, 33, 51, 12, 48, 99, 97, 10, 98, 65, 67, 56, 72, 43, 45, 26, 70, 9, 31, 32, 60, 7, 41, 50, 74, 81, 59, 24, 96, 91, 85, 98, 26, 65, 19, 16, 80, 79, 77, 54, 26, 77, 43, - : unit = ()
Une Sexpression Lisp est composée de paires pointées (une structure de données modifiable comportant un fils gauche (le car) et un fils droit (le cdr)), de symboles ou de nombres et du marqueur Nil désignant la Sexpression vide. Écrire le type les décrivant.
Écrire les fonctions de base, à savoir car, cdr, cons, rplaca , rplacd, consp et nullp.
Écrire une fonction imprimant des Sexpressions. On se donnera les quelques expressions suivantes:
let cons0 = cons (Symbole "hux") Nil;; cons0 : sexpr = Paire \camlbslash{}{car = Symbole "hux"; cdr = Nil\camlbslash{}} let cons1 = cons (Nombre 1) (Symbole "foo");; cons1 : sexpr = Paire \camlbslash{}{car = Nombre 1; cdr = Symbole "foo"\camlbslash{}} let cons3 = cons (Symbole "Bar") cons0;; cons3 : sexpr = Paire \camlbslash{}{car = Symbole "Bar"; cdr = Paire \camlbslash{}{car = Symbole "hux"; cdr = Nil\camlbslash{}}\camlbslash{}} let cons2 = cons cons3 Nil;; cons2 : sexpr = Paire \camlbslash{}{car = Paire \camlbslash{}{car = Symbole "Bar"; cdr = Paire \camlbslash{}{car = Symbole "hux"; cdr = Nil\camlbslash{}}\camlbslash{}}; cdr = Nil\camlbslash{}} let cons4 = cons cons1 cons3;; cons4 : sexpr = Paire \camlbslash{}{car = Paire \camlbslash{}{car = Nombre 1; cdr = Symbole "foo"\camlbslash{}}; cdr = Paire \camlbslash{}{car = Symbole "Bar"; cdr = Paire \camlbslash{}{car = Symbole "hux"; cdr = Nil\camlbslash{}}\camlbslash{}}\camlbslash{}}
Tâchez d'imprimer ainsi les listes suivantes:
print cons0;; (hux)- : unit = () print cons1;; (1 . foo)- : unit = () print cons2;; ((Bar hux))- : unit = () print cons3;; (Bar hux)- : unit = () print cons4;; ((1 . foo) Bar hux)- : unit = ()
Écrire les fonctions append et reverse sur les Sexpressions.
Créez une liste infinie (circulaire) et écrire une fonction capable de l'imprimer. Si l'on suppose que la liste infinie est (0 1 0 1 0 1 ...) alors tâchez de créer puis d'imprimer ce qui précède.
control-C permet de tuer les calculs en cours et de revenir à la boucle d'interaction de Caml.
Écrire un prédicat d'égalité sur les Sexpressions. egal sexpr1 sexpr2 retourne Vrai si les expressions sont similaires. On négligera le cas des structures infinies.