next up previous
Next: Topographie de fonctions Up: Exercices en CAML Previous: Types

Sexpressions et altérations

Exercice 34

É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 = ()

Solution 34

let engendre_alea a b c =
  let seed = ref 0 in
   function n -> begin
                  seed := (b + a * !seed) mod c;
                  !seed mod n
                end;;
engendre_alea : int -> int -> int -> int -> int = <fun>

Notez la référence, comment on la lit et comment on la modifie. Notez aussi l'endroit où est initialisée seed assurant l'indépendance des deux exemples présentés.

Exercice 35

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.

Solution 35

type sexpr =
   Nombre of int
 | Symbole of string
 | Paire of paire_pointee
 | Nil
and paire_pointee = \camlbslash{}{mutable car : sexpr; 
                     mutable cdr : sexpr\camlbslash{}};;
Type sexpr defined.
Type paire_pointee defined.

Note la codéfinition des deux types: le premier est un type somme, le second un type enregistrement (pour record).

Exercice 36

Écrire les fonctions de base, à savoir car, cdr, cons, rplaca , rplacd, consp et nullp.

Solution 36

Les exemples qui suivent usent de multiples syntaxes différentes.

let car = function
   Paire \camlbslash{}{car=e; _\camlbslash{}} -> e
 | _                -> failwith "Pas une paire pointee";;
car : sexpr -> sexpr = <fun>
let cdr = function
   Paire \camlbslash{}{cdr=e\camlbslash{}} -> e
 | _             -> failwith "Pas une paire pointee";;
cdr : sexpr -> sexpr = <fun>
let cons x y = Paire \camlbslash{}{car=x; cdr=y\camlbslash{}};;
cons : sexpr -> sexpr -> sexpr = <fun>
let rplaca v e = 
  match v with
    Paire(p) -> p.car <- e; v
  | _        -> failwith "Pas une paire pointee";;
rplaca : sexpr -> sexpr -> sexpr = <fun>
let rplacd v e =
  match v with
    Paire p -> p.cdr <- e; v
  | _       -> failwith "Pas une paire pointee";;
rplacd : sexpr -> sexpr -> sexpr = <fun>
let consp = function
   Paire _ -> true
 | _       -> false;;
consp : sexpr -> bool = <fun>
let nullp = function
   Nil -> true
 | _   -> false;;
nullp : sexpr -> bool = <fun>

Notez la syntaxe de l'affectation dans un enregistrement.

Exercice 37

É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 = ()

Solution 37

let rec print = function
   Nombre(n)  -> print_int n
 | Symbole(s) -> print_string s
 | Nil        -> print_string "()"
 | Paire(p)   ->
     print_string "(";
     let rec print_liste = function \camlbslash{}{car=a; cdr=d\camlbslash{}} ->
       begin print a;
             match d with
               Nil       -> print_string ")"
             | Paire(pp) -> print_string " "; print_liste pp
             | _         -> print_string " . "; print d; print_string ")" 
       end in print_liste p;;
print : sexpr -> unit = <fun>

Exercice 38

Écrire les fonctions append et reverse sur les Sexpressions.

Solution 38

let rec lisp_append l1 l2 =
  if nullp l1 then l2
  else cons (car l1) (lisp_append (cdr l1) l2);;
lisp_append : sexpr -> sexpr -> sexpr = <fun>
let lisp_reverse l =
  let rec reverse l resultat =
    if consp l then reverse (cdr l) (cons (car l) resultat)
    else resultat in
  reverse l Nil;;
lisp_reverse : sexpr -> sexpr = <fun>

Exercice 39

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.

Solution 39

La fonction cprint qui suit est d'un style fortement Lispien, Pardonnez à l'auteur cet écart culturel trahissant ses origines!

let consinfini = cons (Nombre 1) (cons (Nombre 2) Nil);;
consinfini : sexpr =
 Paire \camlbslash{}{car = Nombre 1; cdr = Paire \camlbslash{}{car = Nombre 2; cdr = Nil\camlbslash{}}\camlbslash{}}
begin 
  rplacd (cdr consinfini) consinfini;
  car consinfini = car (cdr (cdr consinfini))
end;;
Toplevel input:
>  rplacd (cdr consinfini) consinfini;
>  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning: this expression has type sexpr,
but is used with type unit.
- : bool = true
let rec cprint e =
  let rec iterer e1 e2 bool =
     if consp e1
     then if e1 == e2
          then print_string "..."
          else begin
                cprint (car e1);
                if consp (cdr e1)
                then begin print_string " ";
                           iterer (cdr e1)
                                  (if bool then (cdr e2) else e2)
                                  (not bool)
                     end
                else if nullp (cdr e1)
                     then print_string ")"
                     else begin print_string " . ";
                                cprint (cdr e1);
                                print_string ")"
                          end
               end
     else print e1
  in if consp e
     then begin print_string "(";
                print (car e);
                print_string " ";
                iterer (cdr e) e true;
                print_string ")"
          end
     else print e;;
cprint : sexpr -> unit = <fun>
cprint cons1;;
(1 foo)- : unit = ()
cprint cons3;;
(Bar hux))- : unit = ()
cprint consinfini;;
(1 2 1 ...)- : unit = ()

Exercice 40

É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.

Solution 40

let rec egal sexpr1 sexpr2 =
  match (sexpr1, sexpr2) with
    (Nil, Nil)                -> true
  | (Paire \camlbslash{}{car=s11; cdr=s12\camlbslash{}}, Paire \camlbslash{}{car=s21; cdr=s22\camlbslash{}}) ->
        (egal s11 s21) & (egal s21 s22)
  | (Nombre n1, Nombre n2)    -> n1 = n2
  | (Symbole s1, Symbole s2)  -> s1 = s2
  | (_, _)                    -> false;;
egal : sexpr -> sexpr -> bool = <fun>


next up previous
Next: Topographie de fonctions Up: Exercices en CAML Previous: Types

© C. Queinnec fecit (Sat Feb 7 22:11:04 MET 1998)