INFO401 corr TD TP

Préliminaires

Pour afficher correctement dans le wiki, allez voir un peu comment on fait. Vous pouvez regarder par exemple sur le wiki du cours ou directement sur des articles de Wikipedia. La documentation de mediawiki se trouve ici.

Un truc important : pour rentrer du code Caml, il faut mettre les balises <source lang="ocaml">...</source>" autour de votre code. Allez par exemple voir le début de la section sur le TD1 et TP0.

Vous pouvez aller discuter des corrections dans les sujets de discussions associes...

Le TD1 et le TP0

Pour vous montrer un exemple de ce que j'attends, voila la correction de la fonction factorielle. (C'était facile...) J'ai volontairement mis beaucoup de commentaires...

La fonction factorielle (TD1, exercice 2, question 2)

Le but est de calculer la fonction $!n=1\times 2\times \cdots \times n$ par récurrence. La version typée est verbeuse de la fonction correspondante en Caml donne :

<source lang="ocaml"> (* fonction factorielle : c'est la factorielle habituelle des mathématiciens... *) let rec fact (n:int) : int =

 if (n>1)
 then  n * (fact (n-1))
 else 1      (* rq : pour que le programme ne boucle pas sur les valeurs négatives, on renvoie 1 dés que n<1 *)

</source>

Comme la fonction est récursive, il ne faut pas oublier le rec au début de la définition.

On aurait pu faire une autre version, qui fonctionne différemment sur les nombres négatifs :

<source lang="ocaml"> let rec fact' = function

  n when (n>0) -> n * fact' (n-1)
| n when (n<0) -> n * fact' (n+1)
| _ -> 1  (* si n n'est ni plus petit que 0 ni plus grand que 0, n est égal à 0, et on renvoie donc 1 *)

</source>

J'ai volontairement mis une version qui contient plusieurs choses que nous n'avons pas encore vues en cours :

• utilisation de "function" plutôt que fun,
• le symbole "|",
• le mot clé "when".

Vous devriez pouvoir comprendre ce que fait la fonction. Sinon, voici une version que vous auriez pu écrire :

<source lang="ocaml"> let rec fact_bis = fun n ->

 if (n=0)
 then 1
 else begin
   if (n>0)
   then n*fact_bis (n-1)
   else n*fact_bis (n+1)   (* dans ce cas, n est forcement négatif *)
 end

</source>

Les fonctions sommes

Il s'agit ici d'écrire la fonction qui va additionner les carrés des entiers de 1 jusqu'à un nombre donné.

Cela donne : <source lang="ocaml"> let rec somme_carre b = if (b=0) then 0 else (b*b) + somme_carre (b-1);; </source>

Ensuite on nous demande de calculer la somme des cubes des entiers de 1 jusqu'à un nombre donné. On pourrait faire le même programme en remplaçant b*b par b*b*b, mais on va définir une fonction puissance (car elle n'existe pas d'origine sous Caml), qui nous servira aussi pour la suite... :

<source lang="ocaml"> let rec puissance x a = if (a = 0) then 1 else x * puissance x (a-1);; </source>

On doit maintenant calculer la somme des $i^{i}$, i variant de 1 à un nombre donné :

<source lang="ocaml"> let rec somme_puissance b = if (b=0) then 0 else (puissance b b) + somme_puissance (b-1);; </source>

On peut définir une unique fonction qui permettrait de faire toutes ces sommes, celle-ci aura pour argument une fonction quelconque :

<source lang="ocaml"> let rec somme_fonction n f = (* f étant une fonction *) if (n=0) then f 0 else f n + somme_fonction (n-1) f;; </source>

cette fonction est de type "int -> fun -> int"

Nombres pairs et impairs (TP0 Partie 2 Question 2)

Il faut écrire les fonctions récursives pairs et impairs, qui renvoient vrai si le nombre est pair (respectivement impair) et faux si le nombre est impair (respectivement pair); Ici nous devons déclarer simultanément les deux fonctions, car chacune fait appel à l'autre lors de son exécution.

Cela donne :

<source lang="ocaml"> let rec pair n =

 if (n=0) then true
 else impair (n-1)

and impair n =

 if (n=0) then false
 else  pair (n-1);;

</source>

Suite de Fibonacci

La suite de fibonacci est tel que u₀=0 u₁=1 et u_n+2=u_n+1+u_n.

<source lang="ocaml"> let rec fib n = if (n=0) then 0 else if (n=1) then 1 else fib (n-1) + fib (n-2);; </source>

La plus grande valeur que l'on peut obtenir sans que cela soit trop long est 24157817, ce qui correspond à fib 37. Nous trouvons qu'il faut déjà 88 additions pour calculer fib 10.

Rq : fib de 37 prend effectivement beaucoup de temps. Il faut 39088168 additions avant d'en arriver à bout. Il est possible de faire une version de Fibonacci qui va très vite et qui calcule fib 37 en seulement 36 additions...

Comment ?

Dragon !

 Le dragon est une créature mythique, présente dans de nombreuses cultures.
 On peut déterminer deux grands types de dragons : le dragon occidental et le dragon oriental

La fonction dragon a pour but de dessiner un dragon, pour cela on utilise une fonction récursive qui admet pour argument le nombre n d'itération de la fonction, et les coordonnées de 2 points. A chaque itération, la fonction calcule pour chaque segment, un nouveau point et le relie ensuite aux deux autres.

On obtient en tout 2ⁿ segments entremêlés, qui forment un dragon.

Let's go !

<source lang="ocaml"> let rec dragon (n:int) (a:int) (b:int) (c:int) (d:int) : unit = if (n = 0) then (moveto a b ; lineto c d)

              else begin
                     let x = (a+c+d-b)/2 in
                     let y = (b+d+a-c)/2 in
                     dragon (n-1) a b x y ;
                     dragon (n-1) c d x y
                   end ;;

</source>

Rq : votre version du dragon est bien, mais pas très précises. (Je chipote un peu...) Pour les paramètres (dragon 11 100 100 400 400), de nombreux carrés ne sont pas bien tracés.

Comment expliquez-vous cela, et comment pouvez-vous le corriger ?

Pour améliorer la précision je suggère de passer les coordonnées en type Float. --Nicolas 31 janvier 2009 à 11:42 (CET)

Le TD2

Exercice 1 : Tuples
Question 4 :

On définit la fonction curry par:

<source lang="ocaml">

Let curry (f: 'a * 'b -> 'c) : 'a -> 'b -> 'c
    = fun x y -> f(x,y);;

</source>

Ou encore en simplifiant:

<source lang="ocaml">

Let curry f x y = f(x,y);;

</source>

On définit ensuite la fonction uncurry par:

<source lang="ocaml">

Let uncurry (f: 'a -> 'b -> 'c) : 'a * 'b -> 'c
    = fun x -> f (fst x) (snd x);;

</source>

Ou encore de trois autres manières plus simplifiées:

<source lang="ocaml">

Let uncurry f = fun x -> f (fst x) (snd x);;

</source>

<source lang="ocaml">

Let uncurry f = fun x -> match x with (a,b) -> f a b;;

</source>

<source lang="ocaml">

Let uncurry f = function (a,b) -> f a b;;

</source>

Avantage de la première forme (à plusieurs arguments): Elle permet une application partielle: on peut appliquer cette fonction à une seule partie des arguments.

Inconvénients de la seconde forme (à un argument):

• il faut faire appel à fst, snd;
• Caml doit séparer les paires: c'est une perte de temps

Question 5 :

D'après la fonction récursive Fibonacci définit par
f(0)=0
f(1)=1
f(n+2)=f(n+1)+f(n),
comment compter le nombre d'appels récursifs en Caml?
<source lang="ocaml">

let rec fib n =
    if (n<2) then (n,0)
    else let t = fib (n-1) in
         let s = fib (n-2) in 
    (fst t + fst s , snd t + snd s + 1)

</source> exemple : fib 10 = (55, 88) pour exécuter la fonction Fibonacci(10), il y a 88 appels récursifs nécessaires...

Exercice 2 : Listes
Question 5 :

suite à l'étude des fonctions

• longueur

<source lang="ocaml">

let rec longueur l=
    match l with
    [] ->0
    | _ :: l -> 1+longueur l

</source>

• applique

<source lang="ocaml">

let rec app f p =
    match p with 
    [] -> []
    | a :: p -> f(a) :: app f p

</source>

• concatene

<source lang="ocaml">

let rec cat l1 l2 =
    match l1 with
    [] -> l2
    | a :: l -> a :: (cat l l2)

</source>

• renverse,

<source lang="ocaml">

let rec renverse l =
    match l with
    [] -> []
    | a :: l -> (renverse l)@[a]

</source> on remarque des similitudes. Ces fonctions ont le même schéma de base ( celui de la fonction reduit) <source lang="ocaml">

let rec reduit l o f =
    match l with
    [] -> o
    | a :: l -> f a (reduit l o f)

</source> NB : val reduit : 'a list -> 'b -> ('a -> 'b -> 'b) -> 'b = <fun>

Question 6 :
Reprogrammons les fonctions précédentes à partir de la fonction reduit !
<source lang="ocaml">

let longueur l =
    let f _ r = 1 + r in 
    reduit l o f

</source>

<source lang="ocaml">

let app g l =
    let f  
    reduit l [] f

</source>

<source lang="ocaml">

let cat l1 l2 =
    let f a r = a :: r in  
    reduit l1 l2 f

</source>

<source lang="ocaml">

let renverse l =
    let f r a = [r]@[a]  
    reduit l [] f

</source>

Le TP1 - début

Le sujet programmes récursifs, listes, au format pdf.

Partie 1 : Quelques compléments sur les programmes récursifs

Dans cette partie, on travaille sur la fonction Fibonacci

Question 1

On commence par l'utiliser sous la forme :

<source lang="ocaml"> let rec fib n = if n<2

  then n
  else fib (n-1) + fib (n-2)</source>

Pour comprendre ce qu'il se passe, on trace la fonction à l'aide de "#trace" pour fib 5

fib <-- n veut dire que l'on donne la valeur n à la fonction fib

alors que fib --> n veut dire que fib renvoie n <source lang="ocaml">

1. fib 5 ;;

fib <-- 5 fib <-- 3 fib <-- 1 fib --> 1 fib <-- 2 fib <-- 0 fib --> 0 ... fib --> 1 fib <-- 2 fib <-- 0 fib --> 0 fib <-- 1 fib --> 1 fib --> 1 fib --> 2 fib --> 3 fib --> 5 - : int = 5</source>

On peut remarquer que la fonction calcule plusieurs fois le même fib n. Une optimisation consisterait à garder certaines valeurs en mémoire.

Question 2

On écrit fib2 de type "int -> int*int" qui renvoie le valeur de fib n (fst fib2 n) et fib n-1 (snd (fib2 n)) :

<source lang="ocaml"> let rec fib2 n = if n<2

  then (n,n-1)
  else let t = fib2 (n-1) in
     (fst(t)+snd(t),fst(t));;</source>

Question 3

Pour comparer les fonctions fib et fib2, on les trace pour n=7 :

<source lang="ocaml">

1. fib 7 ;;

fib <-- 7 fib <-- 5 fib <-- 3 fib <-- 1 ... fib --> 3 fib --> 5 fib --> 8 fib --> 13 - : int = 13 </source> <source lang="ocaml">

1. fib2 7 ;;

fib2 <-- 7 fib2 <-- 6 fib2 <-- 5 fib2 <-- 4 fib2 <-- 3 fib2 <-- 2 fib2 <-- 1 fib2 --> (1, 0) fib2 --> (1, 1) fib2 --> (2, 1) fib2 --> (3, 2) fib2 --> (5, 3) fib2 --> (8, 5) fib2 --> (13, 8) - : int * int = (13, 8) </source> On remarque que fib2 fait 14 calculs alors que fib en 81 pour n=7. Afin de retourner uniquement la valeur de fib n on définit une nouvelle fonction, beaucoup plus rapide que fib, en prenant le premier élément de la paire constituant fib2 n.

Question 4 ( Bonus )

On veut créer fib3 de type int->int->int->int tel que :

- son premier argument est l'entier n pour fibonacci de n

- les 2 autres arguments sont des accumulateurs qui permettent de conserver des valeurs successives ( pour i-1 et i )

--- à venir ---

Partie 2 : Manipulation des listes

Question 1

Voici quelque fonctions d'abord en définition directe, puis en utiliser la fonction List.fold right

<source lang="ocaml"> let rec longueur l = match l with []->0 |a::l'->1 + (longueur l')

let rec applique f l = match l with []->[] |a::l -> ( f a )::( applique f l ) </source>

<source lang="ocaml"> let rec applique f l = match l with []->[] |a::l -> ( f a )::( applique f l ) </source>

<source lang="ocaml"> let rec concatene l l' = match l with []->l' |a::l->a::(concatene l l') </source> <source lang="ocaml"> let longueur_bis l = let f a r = 1 + r in List.fold_right l o f </source> <source lang="ocaml"> let applique_bis f l = let f' a r = ( f a )::r in List.fold_right l [] f' </source> <source lang="ocaml"> let concatene_bis l1 l2 = let f a r = a::r in List.fold_right l1 l2 f </source>

Question 2

Voici la fonction reverse telle qu'on l'a écrite dans le TD

<source lang="ocaml"> let rec reverse l =

 match l with
 []->[]
 |a::l -> (reverse l)@[a] ;; 

</source>

Pour la comparer avec List.rev, on va regarder le temps d'exécution sur une très grande liste.

Pour cela, on créé une fonction qui fabrique une liste de n valeurs :

<source lang="ocaml"> let rec liste_ordonnée l n =

 if n=0 then l
 else g l (n-1) @ [n] ;;

</source>

Ou encore

<source lang="ocaml"> let rec longueliste n = if n=0 then [] else n::longueliste (n-1);; </source>

On peut tester les fonctions avec une liste de 10000 éléments.

La fonction reverse met environ 15s alors que List.rev s'exécute immédiatement.

Cela montre donc que List.rev est bien plus efficace que Reverse.

Partie 3 : Deux algorithmes de tri pour les listes

Question 1

On programme une fonction insertion qui permet d'insérer un élément à sa place dans une liste triée.

<source lang="ocaml"> let rec insertion l n =

 match l with
 []->[n]
 |a::l' -> if n<=a
   then n::l
   else a::(insertion l' n) ;;

</source>

Question 2

On programme ensuite le tri par insertion.

Le tri par insertion fonctionne de la manière suivante :

- la liste vide est triée,

- pour trier la liste "a::l", on commence par trier (récursivement) la liste l, puis on insère l'élément a dans le résultat.

<source lang="ocaml"> let rec tri_insertion l =

match l with
 []->[]
 |a::l' -> insertion (tri_insertion l' ) a ;;

</source>

Question 3

Maintenant, on programme une fonction fusionne qui permet de fusionner deux listes triées en une seule liste triée.

<source lang="ocaml"> let rec fusionne l1 l2 =

match l1 with 
[]->l2
|a::l' -> begin
          match l2 with
           []-> l1
           |b::l -> if a<=b then ( a::fusionne l' l2 ) 
                              else ( b::fusionne l1 l) 

          end;;

</source>

Pour éviter d'imbriquer des "match", on peut aussi filtrer directement la paire (l1,l2) :

<source lang="ocaml"> let rec fusionnebis l1 l2 = match (l1,l2) with

 ([],_)->l2
 |(_,[])->l1
 |(a::l', b::l2')-> 
    if a < b
    then a::(fusionnebis l' l2)
    else b::(fusionnebis l1 l2');;

</source>

Question 4

Puis une fonction sépare qui permet de séparer une liste quelconque en deux listes de taille équivalente

<source lang="ocaml"> let rec separe l =

match l with
[]->([],[])
|[a]->([a],[])
|a::b::l' -> let t=separe l' in (a::(fst t),b::(snd t)) ;;

</source>

Question 5

On doit maintenant programmer un deuxième type de tri : le tri par fusion.

Le tri fusion fonctionne de la manière suivante :

- la liste vide est triée,

- pour trier une liste non-vide, on sépare la liste en deux parties de longueur égale (à un élément prêt), on trie (récursivement) ces deux listes, puis on fusionne les deux résultats.

<source lang="ocaml"> let rec tri_fusion l =

match l with
[]->[]
|[a]->[a]
|_->let t=separe l in
     fusionne (tri_fusion (fst t)) (tri_fusion (snd t)) ;;

</source>

Question 6

Pour comparer l'efficacité des deux fonctions de tri, on utilise la même méthode que précédemment :

On créé a l'aide d'un fonction une liste aléatoire de 10000 éléments, les éléments étant non triés.

<source lang="ocaml"> let rec créé_list n =

if n=0 then []
else (Random.int n)::créé_list(n-1) ;;

</source>

Ensuite on trie cette liste avec les deux fonctions.

Le tri_fusion renvoie instantanément une liste de 10000 éléments aléatoires triés.

Le tri_insertion, quant à lui, prend plus d'une dizaine de secondes.

Cela semble logique dans le sens où le tri_fusion fait plusieurs calculs simultanés :

il sépare chaque liste en 2 listes distinctes, qu'il re-sépare en 2 listes distinctes, etc...

Il effectue des calculs simultanés sur des plus petites listes.

Question 7

On souhaite trier une liste selon la hauteur des points c'est-à-dire selon le deuxième élément de la paire de flottants. Pour cela, il faudrait faire un tri_fusion sur le 2eme élément de la paire représentant les points tout en sauvegardant le 1er élément...

On peut créer une fonction de tri par insertion générale, qui prend comme paramètre une autre fonction (qui sert à vérifier la comparaison de 2 éléments et rend true ou false) afin de choisir le tri que l'on veut ( décroissant, croissant ... ) :

<source lang="ocaml"> let rec insere comp n l = match l with | [] -> n::[] | a::l' ->

  if comp n a then n :: l
  else a :: insere comp n l' ;;

let rec tri_insertion_bis f = function | [] -> [] | a::l -> insere f a (tri_insertion f l) ;; </source>

Il suffit alors a l'utilisateur de définir la fonction f pour ensuite faire appel a tri_insertion_bis.

Par exemple, pour trier dans un ordre décroissant :

<source lang="ocaml"> let dec a n = if a>=n then true else false ; </source>

Pour trier une liste de paires, il faut créer une fonction qui compare les seconds membres ;

<source lang="ocaml"> let paire a n = if (snd a)<=(snd n) then true else false ;; </source>

Ici, les paires seront triées selon le second membre dans l'ordre croissant.

Question 8 ( Bonus )

Un algorithme de tri est dit stable quand il ne modifie pas l'ordre relatifs des éléments "égaux".

Par exemple, on tri par ordre croissant du premier membre une liste de paires de float : [ ( 5 , 3 ) ; ( -2 , 8 ) ; ( -2 , 2 ) ; ( 5 , 8 ) ; ( 5 , -8 ) ]

non stable : [(-2, 2); (-2, 8); (5, -8); (5, 8); (5, 3)]

stable :[(-2, 8); (-2, 2); (5, 3); (5, 8); (5, -8)]

Pour qu'un tri soit stable, la comparaison de deux éléments doit comprendre aussi le "=", comme c'est le cas pour les fonctions paire et dec