Wiki du LAMA (UMR 5127) - Contributions [fr]

INFO401 corr TD TP

2009-05-27T16:22:50Z

Laurent corantin : /* Le TP2 */

==Préliminaires==

Pour afficher correctement dans le wiki, allez voir un peu comment on fait. Vous pouvez regarder par exemple sur le [[INFO401 | wiki du cours]] ou directement sur des articles de [http://fr.wikipedia.org/wiki/Accueil Wikipedia]. La documentation de mediawiki se trouve [http://meta.wikimedia.org/wiki/Aide:Éditeur ici].

Un truc important : pour rentrer du code Caml, il faut mettre les balises <tt><nowiki><source lang="ocaml">...</source></nowiki>"</tt> autour de votre code. Allez par exemple voir le début de la section sur [[#Le TD1 et le TP0 | 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 <math>!n = 1\times2\times \cdots \times n</math> 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 <tt>rec</tt> 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 "<tt>function</tt>" plutôt que <tt>fun</tt>,
* le symbole "<tt>|</tt>",
* le mot clé "<tt>when</tt>".

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 <math>i^i</math>, 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 "<tt>int -> fun -> int</tt>"

 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 u0=0 u1=1 et un+2=un+1+un.

<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 <tt>fib 37</tt> 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 2n 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 (<tt>dragon 11 100 100 400 400</tt>), 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. --[[Utilisateur:Nicolas|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">
(* la fonction renvoie une valeur de type int*int :
- la première composante est la valeur de Fibonacci pour n,
- la seconde composante est le nonbre d'appels recursifs effectués *)
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. On peut résumer le principe commun dans la fonction suivante :
<source lang="ocaml">
let rec reduit l o f =
match l with
[] -> o
| a :: l -> let appel_rec = reduit l o f in
f a appel_rec
</source>
''NB :'' le type de <tt>reduit</tt> donné par Caml est : <tt>val reduit : 'a list -> 'b -> ('a -> 'b -> 'b) -> 'b = <fun></tt>

'''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 0 f
</source>

<source lang="ocaml">
let app g l =
let f a r = (g a)::r in
reduit l [] f
</source>

<source lang="ocaml">
let cat l1 l2 =
let f a r = a :: r in
reduit l1 l2 f
</source>

On peut également introduire la fonction directement avec un <tt>fun</tt> de la maniere suivante :
<source lang="ocaml">
let renverse l = reduit l [] (fun a r -> r @ [a])
</source>
 
'''Question 7 :''' 

Le type de la fonction reduit est: ( 'a -> 'b -> 'b ) -> 'a list 
Celui de la fonction List.fold_right est: ( 'a -> 'b -> 'b ) -> 'a list -> 'b -> 'b ;
 
 
l'ordre des arguments de fold_right est le même que l'ordre des arguments de reduit. La fonction fold_right compte juste deux arguments supplémentaires.

 
'''Question 8 :''' 

Voici la fonction fold_left:
<source lang="ocaml">
let rec fold_left f b l=
match l with
[]->b
|a::l -> fold_left f (f b a) l;;
</source>
 
Cette fonction est ''récursive terminale'', de type ( 'a -> 'b -> 'a ) -> 'a -> 'b list -> 'a .

==Le TP1 - début==

Le sujet [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info401/tp1.pdf 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">
# 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">
# fib 7 ;;
fib <-- 7
fib <-- 5
fib <-- 3
fib <-- 1
...
fib --> 3
fib --> 5
fib --> 8
fib --> 13
- : int = 13
</source>
<source lang="ocaml">
# 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 :

<source lang="ocaml">
let fib n = fst ( fib2 n ) ;;
</source>

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éfinies en utilisant <tt>List.fold_right</tt> :

<source lang="ocaml">
let longueur l = let f a r = 1 + r in List.fold_right f l 0
</source>
<source lang="ocaml">
let app f l = let f' a r = ( f a )::r in List.fold_right f' l []
</source>
<source lang="ocaml">
let concat 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 la fonction <tt>List.rev</tt> de Caml, 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 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 <tt>reverse</tt> met environ 15s alors que <tt>List.rev</tt> s'exécute immédiatement.

Cela montre donc que <tt>List.rev</tt> est bien plus efficace que <tt>reverse</tt>.

::En fait, reverse fait ( n + n-1 + n-2 + ... + 1 ) opérations à chaque fois (il met le premier élément au bout de la liste et ainsi de suite) , soit au total <math>n*(n+1)/2 \sim n^2</math> opérations.

<tt>List.rev</tt> utilise la fonction suivante :

<source lang="ocaml">
let rec rev_append l1 l2 =
match l1 with
[] -> l2
| a::l -> rev_append l (a::l2);;

let rec rev l = rev_append l [];;
</source>

Elle fait donc environ <math>n</math> opérations.

'''Partie 3 : Deux algorithmes de tri pour les listes'''

Question 1

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

<source lang="ocaml">
let rec insertion n l =
match l with
[] -> [n]
| a::l' -> if n<=a
then n::l
else a::(insertion n l') ;;
</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 "<tt>a::l</tt>", on commence par trier (récursivement) la liste <tt>l</tt>, puis on insère
l'élément <tt>a</tt> dans le résultat.

<source lang="ocaml">
let rec tri_insertion l =
match l with
[] -> []
| a::l' -> insertion a (tri_insertion l') ;;
</source>

ou plus simplement :

<source lang="ocaml">
let tri l = List.fold.right insertion l [] ;;
</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 <tt>(l1,l2)</tt> et regrouper les cas d'un des listes vides ensemble :

<source lang="ocaml">
let rec fusionnebis l1 l2 =
match l1,l2 with
[],l | l,[] -> l
| (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 liste_aleatoire n =
let rec aux n max =
if n=0
then []
else (Random.int max)::aux (n-1) max
in
aux n n ;;
</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.

:''Remarque :'' cela vient du fait que le tri fusion divise la taille de la liste par deux à chaque étape, alors que le tri par insertion soustrait un élément à chaque étape.
: On peut montrer que le temps de calcul pour le tri fusion est proportionnel à <math>n \log(n)</math>, ce qui est très petit par rapport à <math>n^2</math> (temps d'execution moyen du tri par insertion) quand <math>n</math> est grand.

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 fusion 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 fusionne comp l1 l2 =
match (l1,l2) with
([],_) -> l2
| (_,[]) -> l1
| (a::l', b::l2') ->
if (comp a b)
then a::(fusionne l' l2)
else b::(fusionne l1 l2');;

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

Il suffit alors a l'utilisateur de définir la fonction de comparaison pour ensuite faire appel à <tt>tri_fusion</tt>.

Par exemple, pour trier dans un ordre décroissant :
<source lang="ocaml">
let dec a n = if a>=n then true
else false ;
</source>
ou même plus simplement
<source lang="ocaml">
let dec = (>=) ;;
</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 = (snd a) <= (snd n) ;;
</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 : <tt>[(-2, 2); (-2, 8); (5, -8); (5, 8); (5, 3)]</tt>

stable : <tt>[(-2, 8); (-2, 2); (5, 3); (5, 8); (5, -8)]</tt>

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.

==Le TD3==

 Exercice 1 : les arbres binaires 

 Question 1 

<source lang="ocaml">
type 'a arbre = Vide | Noeud of 'a*'a arbre*'a arbre ;;
</source>

 
 Question 2 

<source lang="ocaml">
let rec taille a =
match a with
Vide -> 0
|Noeud(e,g,d) -> 1 + (taille g) + (taille d) ;;
</source>

La fonction taille compte le nombre de noeuds que contient un arbre.

 
 Question 3 

<source lang="ocaml">
let rec applique f a =
match a with
Vide -> Vide
|Noeud(e,g,d) -> Noeud(f e,applique f g,applique f d) ;;
</source>

La fonction applique est équivalente à la fonction List.map

 
 Question 4 

<source lang="ocaml">
let rec poids (f : 'a -> int) a =
match a with
Vide -> 0
|Noeud(e,g,d) -> (f e) + (poids f g) + (poids f d) ;;
</source>

 
 Question 5 
<source lang="ocaml">
let rec reduit a o f =
match a with
Vide -> 0
|Noeud(e,g,d) -> let x = reduit g o f in
let y = reduit d o f in
f e x y ;;
</source>

La fonction reduit est equivalente à la fonction List.fold_right pour le type des arbres.

Réécriture de taille et poids :

<source lang="ocaml">
let rec taille a = reduit a 0 (fun e x y -> 1 + x + y) ;;
let rec poids f a = reduit a 0 (fun e x y -> (f e) + (f x) + (f y)) ;; (*?????*)
</source>

 
 Question 6 
<source lang="ocaml">
let rec collecte a =
match a with
Vide -> []
|Noeud(e,g,d) -> e::(collecte g)@(collecte d) ;;
</source>

La fonction collecte récupère tous les éléments de l'arbre et les renvoie sous forme d'une liste.

Avec la fonction reduit :

<source lang="ocaml">
let rec collecte a = reduit a [] (fun e x y -> e::x@y) ;;
</source>

 
 Question 7 
<source lang="ocaml">
let rec feuilles a =
match a with
Vide -> []
|Noeud(e,g,d) -> if (g=Vide && d=Vide) then [e]
else (feuilles g)@(feuilles d) ;;
</source>

Avec reduit :

<source lang="ocaml">
let rec feuilles a = reduit a [] (fun e x y -> if (x=[] && y=[]) then [e]
else x@y) ;;
</source>

 

 Exercice 2 : la tortue 

 Question 1 

<source lang="ocaml">
type action = Forward of int | Left of int | SetPos of int*int | SetHeading of int | PenUp | Pendown ;;
</source>

 
 Question 2 

<source lang="ocaml">
let rec ecrit (l:action list) (pen:bool) : bool =
match l with
[] -> false
|(Forward d)::l -> if (d=0 || pen=false) then ecrit l pen
else true
|PenUp::l -> ecrit l false
|PenDown::l -> ecrit l true
| _ -> ecrit l pen ;;
</source>

La fonction ecrit renvoie true si la tortue écrit qqch ou false sinon.

 
 Question 3 

<source lang="ocaml">
let rec pos (x:int) (y:int) (a:int) (l:action list) : ((int*int)int) =
match l with
[] -> ((x,y),a)
|PenUp::l |Pendown::l -> pos x y a l
|(Left b)::l -> pos x y (a+b) l
|(SetPos(x',y'))::l -> pos x' y' a l
|(SetHeading b)::l -> pos x y b l
|(Forward d)::l -> pos (x+(sin a)*d) (y+(cos a)*d) a l ;;
</source>

 
 Question 5 
<source lang="ocaml">
type action = Forward of int | SetPos of int*int | SetHeading of int | Left of int | PenUp | Pendown | Repeat of int*action list ;;
</source>

==Le TD4==

 Exercice 1 : Petits exercices combinatoires 
Question 3 
 
On commence par créer une fonction intermédiaire.
<source lang="ocaml">
let rec supp' x l =
match l with
[]->[]
|b::f'-> if (x=b) then supp' x l'
else b::supp' x f';;
</source>

<source lang="ocaml">
let rec supp l =
match l with
[]->[]
|a::l'-> a::supp supp' a l';;
</source>
 

 Exercice 2 : Dictionnaires 
Un dictionnaire est une liste de paires 
Question 2 
 
<source lang="ocaml">
let rec insere c v d
match d with
[]->[(c,v)]
|(c',v')::d -> if (c=c') then (c',v')::(insere c v d)
else (c,v)::d ;;
</source>

<source lang="ocaml">
let rec supprime c d
match d with
[]->[]
|(c',v')::d -> if (c=c') then d
else (c',v')::(supprime c d) ;;
</source>

<source lang="ocaml">
let rec existe_cle c d
match d with
[]-> false
|(c',_)::d -> (c=c') || existe_cle c d;;
</source>

<source lang="ocaml">
let rec existe_val v d
match d with
[]-> false
|(_,v')::d -> if (v=v') then true
else existe_val v d;;
</source>

<source lang="ocaml">
let rec recherche_cle c d
match d with
[]-> None
|(c',_)::d -> if (c=c') then Some c'
else recherche_cle c d;;
</source>

<source lang="ocaml">
(* liste des valeurs de c par on peut avoir plusieurs cases, et donc plusieurs clés, avec une même valeur *)
let rec recherche_val v d
match d with
[]->[]
|(c',v')::d -> if (v=v') then c'::(recherche_val v d)
else recherche_val v d;;
</source>

Question 3 
 
<source lang="ocaml">
(* Liste des clés *)
let rec liste_cle c d
match d with
[]-> []
|(c',_)::d -> c'::(liste_cle c d);;

(* Liste des valeurs *)
let rec liste_val v d
match d with
[]->[]
|(_,v')::d -> v'::(liste_val v d);;
</source>

On peut également utiliser des fonctions existantes :
<source lang="ocaml">
(* Liste des clés *)
let liste_cle d = List.map fst;;

(* Liste des valeurs, attention aux doublons! *)
let liste_val d = suppr_doublons(List.map snd);;
</source>

Question 4 
 
<source lang="ocaml">
let rec zip l1 l2
match l1 l2 with
[].[]->[]
|c::lc, v::lv -> (c,v)::(zip lc lv)
|_,_ -> [];;
</source>

Question 5 
 
On aurait pu utiliser une liste triée : si par exemple on cherche 12 et qu'on en est à 14 dans la liste, on sait que 12 n'y est pas. PB : ceci n'empêche pas d'aller à la fin de la liste si la valeur ou la clé recherchée est grande ... 
Une recherche dichotomique est inefficace sur les listes ... 
=> dans la bibliothèque hash table de Caml, il existe un List.zip

 Exercice 3 : Arbres binaires 
Question 1 
 
La profondeur d'un arbre binaire correspond au nombre d'étage : on regarde à partir de la première racine et des sous arbres, on calcule la profondeur à gauche et la profondeur à droite, on prend la plus grande et on y ajoute 1.
<source lang="ocaml">
let rec profondeur a
match a with
Vide -> 0
|Noeud(_,g,d) -> 1 + max(profondeurg) (profondeurd);;
</source>

Question 2 
 
<source lang="ocaml">
let rec equilibre a
match a with
Vide -> true
|Noeud(_,g,d) -> if (profondeur g)=(profondeur d) || (profondeur g)=(profondeur d +1) || (profondeur g +1)=(profondeur d)
then (equilibre d)&&(equilibre g)
else false;;
</source>

Question 3 
 
<source lang="ocaml">
let rec present e a
match a with
Vide -> false
|Noeud(e',g,d) -> e'=e || present e g || present e d;;
</source>

Question 4 
 
<source lang="ocaml">
let rec present e a
match a with
Vide -> false
|Noeud(e',g,d) -> if (e'=e) then true
else if (e<e') then present e g
else present e d;;
</source>

Question 5 
 
<source lang="ocaml">
let rec insere e a
match a with
Vide -> e
|Noeud(e',g,d) -> if (e<e') then insere e g
else insere e d;;
</source>

==Le TP2==
Partie 1 
QUESTION 1 : 
la fonction suivante permet de calculer les ensemble de nombre. Elle est réalisé à l'aide d'une concaténation de la liste précédente avec la liste modifier ainsi que List.map.
 

<source lang="ocaml">
open List

let rec sous_ensemble n=
if n=0
then
[[]]
else
let liste = sous_ensemble (n-1) in (List.map (fun l->n::l) liste) @ liste

</source>
 

QUESTION 2 : 
la fonction supprime doublon est réalisé tout d'abord en triant la liste puis en regardant si deux éléments concécutif sont les mêmes, si oui on en supprime un.
 

<source lang="ocaml">
let rec lstTrier liste=
match liste with
[]->[]
| [a]->liste
| a::b::liste->if a=b then lstTrier (a::liste)
else a::lstTrier (b::liste)

let supprime_doublon lst=
lstTrier (List.sort (-) lst)

</source>
 

Partie 2 
QUESTION 1 : 
la fonction taille calcul la taille d'un arbre, on incrémente un compteur dès que l'on rencontre un noeud. 

<source lang="ocaml">

let rec taille (arbre:'a arbre)=
match arbre with
Vide -> 0
| Noeud(_,a,b) -> 1 + taille a+taille b

</source>
 

la fonction applique permet d'appliquer une fonction a tous les éléments d'un arbre. 

<source lang="ocaml">
let rec applique (fc:'a->'b) arbre=
match arbre with
Vide->Vide
| Noeud(a,b,c)->Noeud (fc a,applique fc b,applique fc c )

</source>
 

la fonction fold renvoie le contenu des feuilles composant l'arbre. 

<source lang="ocaml">

let rec fold (f:'a->'b->'b->'b) arbre n=
match arbre with
Vide->n
| Noeud (a,b,c)->f a(fold f b n) (fold f c n)

</source>
 

QUESTION 2 : 
la fonction feuille crée une liste à partir des éléments retourné par la fonction fold. 

<source lang="ocaml">

let rec feuilles (f:'a arbre->'a list) arbre=
fold (fun a b c-> if(b=[])&&(c=[])
then [a]
else (b@c)) arbre[]

</source>
 

QUESTION 3 : 
cette fonction permet de créer un arbre à partir d'une liste, elle regarde la taille des branches afin de pouvoir inserer les éléments de façon à avoir le moins de noeuds possible. 

<source lang="ocaml">

let rec insert arbre aInsert=
match arbre with
Vide->Noeud (aInsert,Vide,Vide)
| Noeud (a,b,c)->if (taille b < taille c) then Noeud(a,(insert b aInsert),c) else Noeud(a,b,(insert c aInsert))

let rec construit_arbre_int liste arbre=
match liste with
[a]->insert arbre a
| a::liste->construit_arbre_int liste (insert arbre a)

let construit_arbre liste=
construit_arbre_int liste Vide

</source>
 

QUESTION 4 : 
la fonction se divise en deux partie : l'une permet d'obtenir la taille minimal d'une branche et l'autre la taille maximal, la fonction affiche ensuite les résultats. 

<source lang="ocaml">

let rec calcMax arbre compt=
match arbre with
Vide->compt
| Noeud (a,b,c)->if (taille b > taille c) then calcMax b compt+1 else calcMax c compt+1

let rec calcMin arbre compt=
match arbre with
Vide->compt
| Noeud (a,b,c)->if (taille b < taille c) then calcMax b compt+1 else calcMax c compt+1

let profondeurs arbre=
(calcMax arbre 0 , calcMin arbre 0)

</source>
 

QUESTION 5 : 
la fonction tailleR est la fonction tille pour les arbres binaires. 
nous pouvons remarquer que la fonction applique pourrait rendre un arbre binaire faux. 

<source lang="ocaml">

type 'a abr = Vide | Noeud of 'a abr * 'a* 'a abr

let rec tailleR abr=
match abr with
Vide -> 0
| Noeud(a,_,b) -> 1 + tailleR a+tailleR b

</source>
 

QUESTION 6 : 
la fonction ajoute permet d'ajouter une donnée en conservant un arbre binaire.
<source lang="ocaml">

let rec ajoute arbre aInsert=
match arbre with
Vide->Noeud (Vide,aInsert,Vide)
| Noeud (a,b,c)->if aInsert
 
QUESTION 7: 
la fonction supp utilise aissi la fonction ajoute afin de conserver un arbre binaire.

<source lang="ocaml">

let rec supp arbre aSupp=
match arbre with
Vide->Vide
| Noeud (a,b,c)->
if (aSupp=b)
then
if (a=Vide&&c=Vide)
then Vide
else
if (a=Vide&&c!=Vide)
then supp c aSupp
else
if (a!=Vide&&c=Vide)
then supp a aSupp
else
ajouteArbre c a
else Noeud((supp a aSupp),b,(supp c aSupp))

</source>
 

QUESTION 8: 
afin de verifier si un arbre est binaire on effectue deux match simultané a tous les noeuds rencontrés en parcourant l'arbre.
<source lang="ocaml">

let rec verifabr arbre=
match arbre with
Vide->true
| Noeud (a,b,c)->
match a with
Vide->true
| Noeud (a2,b2,c2)->if b2true
| Noeud (a3,b3,c3)->if b3>b then verifabr c else false

</source>
 
QUESTION 9: 
la fonction trouveVal permet de renvoyer si oui ou non une valeur est présente dans l'arbre binaire.
<source lang="ocaml">

let rec trouveVal arbre valAtrouve=
match arbre with
Vide->false
| Noeud (a,b,c)->
if (b=valAtrouve)
then true
else
if (valAtrouve<b)
then trouveVal a valAtrouve
else trouveVal c valAtrouve

</source>
 

QUESTION 10: 
la fonction supprime_doublon sur un arbre binaire est plus complexe que celle sur les liste, en effet il faut vérifier aussi les doublons pouvant exister sur des branche séparé.
<source lang="ocaml">

let rec suppDoublon arbre=
match arbre with
Vide->Vide
| Noeud (a,b,c)->
if (trouveVal a b)
then
if (trouveVal c b)
then Noeud((suppDoublon(supp a b)),b,(suppDoublon(supp c b)))
else Noeud((suppDoublon(supp a b)),b,(suppDoublon c))
else
if (trouveVal c b)
then Noeud((suppDoublon a),b,(suppDoublon(supp c b)))
else Noeud((suppDoublon a),b,(suppDoublon c))

</source>
 

==Contrôle continu 1==
'''Partie 2'''

'''Queston 1'''

cette fonction s'applique a tout les elements d'une liste

'''let rec pam0 a l '''=
match l with []->[]
|f::l->(f a)::(pam0 a l);;

la meme fonction mais cette fois on utilise Fold_right

''' let pam a l''' = List.fold_right(fun f t ->(f a)::t)l [];;

ou encore la version avec List.map,elle a le meme type que pam
'''let pam1 a''' = List.map(fun f->f a);;

'''Question 2'''

'''let rec seq i n''' = if nint->int list,cette fonction créee une liste
d'entier consecutifs et concatène un element en fin de liste par exemple::
seq 5 14;;
'''-:int list''' = [5;6;7;8;9;10;11;12;13;14]
mais a partir de 5 chriffres l'execution met plus d'une demi seconde

essayons la version simple
'''let rec seq1 i n''' = if n<i then [] else i::(seq(i+1)n);;

la version recursive terminale avec un accumulateur nous permettons d'avoir
une execution rapide de la fonction

'''let seq2 i n''' =
''' let rec aux i n acc '''=
if n<i then acc
else aux i(n-1) (n::acc)
in
aux i n [];;

'''Partie 3'''
suite de robinson
ecrivons d'abord une iteration qui nous permet de repéter
l'action sur la fonction
'''let rec iter f n x''' = if n=0 then x else iter f(n-1)(f x);;
ensuite la fonction suivant pour passer d'un terme a l'autre
''' let suivant u '''=
(*nous avons aussi la fonction aux permettant de compter le nombre de fois
ou d apparait dans n*)
''' let rec aux u n d '''= match u with []->n::d::[]
|a::u when a=d -> aux u (n+1) d
|a::u->n::d::(aux u 1 a)
in
'''let u '''= List.sort(fun x y->y-x)u (*et la fonction u qui nous permet de trier par ordre
decroissant en utilisant List.sort*)
in
match u with []->[]
|a::u-> aux u 1 a;;

==Le TP3==
'''Partie 1'''

'''Queston 1'''
Déclaration du type pour les tas ( 'a tas )
<source lang="ocaml">type 'a tas = Vide | Noeud of 'a * 'a tas * 'a tas ;;</source>
La fonction pour tester si un élement de type 'a tas est effectivement un tas :
<source lang="ocaml">let rec test tas vPrec = match tas with
Noeud(v,t1,t2) -> if v >= vPrec
then ((test t1 v)&(test t2 v))
else false
|Vide -> true

let testTas tas = match tas with
Noeud(v,_,_) -> test tas v
|Vide -> true </source>

'''Queston 2'''
Pour cette question nous allons écrire 3 fonctions.
La première a pour but de supprimer le premier élément du tas (donc le plus petit), la seconde a pour but de retourner la valeur du premier élément du tas.

<source lang="ocaml">(*Enleve le premier element du tas

Explication du nom de variables
tgv -> tas gauche valeur ( valeur du tas de gauche)
tgg -> tas gauche gauche ( le tas gauche du tas gauche)
tgd -> tas gauche droit ( le tas droit du tas gauche)
*)
let rec enlever tas = match tas with
Vide -> Vide (* Si le tas est vide on retourne le tas Vide *)
| Noeud (v,Vide,td) -> td (* Si le tas gauche est Vide on retourne le tas droit *)
| Noeud (v,tg,Vide) -> tg (* Si le tas droit est Vide on retourne le tas gauche *)
| Noeud (v, (Noeud (tgv,tgg,tgd) as tg),
(Noeud (tdv,tdg,tdd) as td)) (* Si aucun des deux tas est vide *)
-> if tgv < tdv
then Noeud (tgv, enlever tg, td)
else Noeud (tdv, tg, enlever td);;
</source>

<source lang="ocaml">
(* Renvoie la valeur du premier element du tas *)
let premier tas = match tas with
Vide -> raise Tas_Vide
| Noeud(v,_,_) -> v ;;
</source>

On combine ces deux fonctions pour crée la fonction demandée.
<source lang="ocaml">
let min_tas tas = ((premier tas),(enlever tas));;
</source>

'''Queston 3'''
Nous allons crée un fonction qui va calculer la taille de la plus petite branche du tas et de la plus grande branche du tas.
<source lang="ocaml">
(* compare les taille max et les taille min des tas calculé par la fonction tailleTas *)
let compare a b = match (a,b) with
((amin,amax),(bmin,bmax)) -> ((min amin bmin),(max amax bmax));;

(* ajoute 1 a la taille du tas *)
let add a = match a with
(min,max)-> ((min+1),(max+1));;

(* retourne la taille max et la taille min d'un tas *)
let rec tailleTas tas = match tas with
Vide -> (0,0)
| Noeud(_,tg,td) -> add (compare (tailleTas tg) (tailleTas td));;
</source>

Ensuite il suffit d'utiliser cette fonction sur le tas et de comparer l'écart entre la branche la plus courte et la branche la plus longue.
<source lang="ocaml">
let equilibre tas = match (tailleTas tas) with
(min,max) -> (max - min)<2 ;; (* on calcule la difference entre max et min et on test si elle est inférieur à 2 *)
</source>

'''Queston 4'''
<source lang="ocaml">
(* ajoute un element a un tas *)
let rec ajouter v tas = match tas with
Vide -> Noeud (v,Vide,Vide)
| Noeud (tv,tg,td) -> Noeud( min tv v, td, ajouter (max tv v) tg);;
</source>
on insère systématiquement dans le tas de droite, mais on permute le tas de gauche et le tas de droite a chaque fois pour "mélanger" le tas et avoir un tas équilibré

'''Queston 5'''
<source lang="ocaml">
(* ajoute une liste d’elements a un tas *)
let rec ajList liste tas = match liste with
[] -> tas
| v::l' -> ajouter v (ajList l' tas);;
</source>
Il s'agit d'une simple fonction récursive qui parcours la liste et fais appel a la fonction ajouter pour chaque élément de la liste.

''à finir''

'''Queston 6'''
Pour implémenter le tri par tas, nous allons commencer par créer une fonction qui vide un tas et renvoie le contenu de celui-ci dans une liste triée.
<source lang="ocaml">
(* vide un tas et renvoie le contenu du tas dans une liste triée *)
let rec viderTas tas = match tas with
Vide -> []
| Noeud (x,_,_) -> (premier tas)::(viderTas (enlever tas)) ;;
</source>

Il nous suffit maintenant de crée un tas avec la liste en utilisant la fonction ajList, et de passer la liste ainsi crée en paramètre a la fonction viderTas.
<source lang="ocaml">
(* tri la liste passée en paramètre avec la méthode du tri par tas *)
let triTas lst = viderTas (ajList lst Vide);;
</source>

''à finir''

==Le TD5==

==Le TP4==

==TD6==

INFO401 corr TD TP

2009-05-22T11:55:33Z

Laurent corantin : /* Le TP2 */

==Préliminaires==

Pour afficher correctement dans le wiki, allez voir un peu comment on fait. Vous pouvez regarder par exemple sur le [[INFO401 | wiki du cours]] ou directement sur des articles de [http://fr.wikipedia.org/wiki/Accueil Wikipedia]. La documentation de mediawiki se trouve [http://meta.wikimedia.org/wiki/Aide:Éditeur ici].

Un truc important : pour rentrer du code Caml, il faut mettre les balises <tt><nowiki><source lang="ocaml">...</source></nowiki>"</tt> autour de votre code. Allez par exemple voir le début de la section sur [[#Le TD1 et le TP0 | 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 <math>!n = 1\times2\times \cdots \times n</math> 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 <tt>rec</tt> 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 "<tt>function</tt>" plutôt que <tt>fun</tt>,
* le symbole "<tt>|</tt>",
* le mot clé "<tt>when</tt>".

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 <math>i^i</math>, 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 "<tt>int -> fun -> int</tt>"

 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 u0=0 u1=1 et un+2=un+1+un.

<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 <tt>fib 37</tt> 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 2n 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 (<tt>dragon 11 100 100 400 400</tt>), 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. --[[Utilisateur:Nicolas|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">
(* la fonction renvoie une valeur de type int*int :
- la première composante est la valeur de Fibonacci pour n,
- la seconde composante est le nonbre d'appels recursifs effectués *)
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. On peut résumer le principe commun dans la fonction suivante :
<source lang="ocaml">
let rec reduit l o f =
match l with
[] -> o
| a :: l -> let appel_rec = reduit l o f in
f a appel_rec
</source>
''NB :'' le type de <tt>reduit</tt> donné par Caml est : <tt>val reduit : 'a list -> 'b -> ('a -> 'b -> 'b) -> 'b = <fun></tt>

'''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 0 f
</source>

<source lang="ocaml">
let app g l =
let f a r = (g a)::r in
reduit l [] f
</source>

<source lang="ocaml">
let cat l1 l2 =
let f a r = a :: r in
reduit l1 l2 f
</source>

On peut également introduire la fonction directement avec un <tt>fun</tt> de la maniere suivante :
<source lang="ocaml">
let renverse l = reduit l [] (fun a r -> r @ [a])
</source>
 
'''Question 7 :''' 

Le type de la fonction reduit est: ( 'a -> 'b -> 'b ) -> 'a list 
Celui de la fonction List.fold_right est: ( 'a -> 'b -> 'b ) -> 'a list -> 'b -> 'b ;
 
 
l'ordre des arguments de fold_right est le même que l'ordre des arguments de reduit. La fonction fold_right compte juste deux arguments supplémentaires.

 
'''Question 8 :''' 

Voici la fonction fold_left:
<source lang="ocaml">
let rec fold_left f b l=
match l with
[]->b
|a::l -> fold_left f (f b a) l;;
</source>
 
Cette fonction est ''récursive terminale'', de type ( 'a -> 'b -> 'a ) -> 'a -> 'b list -> 'a .

==Le TP1 - début==

Le sujet [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info401/tp1.pdf 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">
# 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">
# fib 7 ;;
fib <-- 7
fib <-- 5
fib <-- 3
fib <-- 1
...
fib --> 3
fib --> 5
fib --> 8
fib --> 13
- : int = 13
</source>
<source lang="ocaml">
# 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 :

<source lang="ocaml">
let fib n = fst ( fib2 n ) ;;
</source>

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éfinies en utilisant <tt>List.fold_right</tt> :

<source lang="ocaml">
let longueur l = let f a r = 1 + r in List.fold_right f l 0
</source>
<source lang="ocaml">
let app f l = let f' a r = ( f a )::r in List.fold_right f' l []
</source>
<source lang="ocaml">
let concat 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 la fonction <tt>List.rev</tt> de Caml, 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 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 <tt>reverse</tt> met environ 15s alors que <tt>List.rev</tt> s'exécute immédiatement.

Cela montre donc que <tt>List.rev</tt> est bien plus efficace que <tt>reverse</tt>.

::En fait, reverse fait ( n + n-1 + n-2 + ... + 1 ) opérations à chaque fois (il met le premier élément au bout de la liste et ainsi de suite) , soit au total <math>n*(n+1)/2 \sim n^2</math> opérations.

<tt>List.rev</tt> utilise la fonction suivante :

<source lang="ocaml">
let rec rev_append l1 l2 =
match l1 with
[] -> l2
| a::l -> rev_append l (a::l2);;

let rec rev l = rev_append l [];;
</source>

Elle fait donc environ <math>n</math> opérations.

'''Partie 3 : Deux algorithmes de tri pour les listes'''

Question 1

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

<source lang="ocaml">
let rec insertion n l =
match l with
[] -> [n]
| a::l' -> if n<=a
then n::l
else a::(insertion n l') ;;
</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 "<tt>a::l</tt>", on commence par trier (récursivement) la liste <tt>l</tt>, puis on insère
l'élément <tt>a</tt> dans le résultat.

<source lang="ocaml">
let rec tri_insertion l =
match l with
[] -> []
| a::l' -> insertion a (tri_insertion l') ;;
</source>

ou plus simplement :

<source lang="ocaml">
let tri l = List.fold.right insertion l [] ;;
</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 <tt>(l1,l2)</tt> et regrouper les cas d'un des listes vides ensemble :

<source lang="ocaml">
let rec fusionnebis l1 l2 =
match l1,l2 with
[],l | l,[] -> l
| (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 liste_aleatoire n =
let rec aux n max =
if n=0
then []
else (Random.int max)::aux (n-1) max
in
aux n n ;;
</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.

:''Remarque :'' cela vient du fait que le tri fusion divise la taille de la liste par deux à chaque étape, alors que le tri par insertion soustrait un élément à chaque étape.
: On peut montrer que le temps de calcul pour le tri fusion est proportionnel à <math>n \log(n)</math>, ce qui est très petit par rapport à <math>n^2</math> (temps d'execution moyen du tri par insertion) quand <math>n</math> est grand.

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 fusion 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 fusionne comp l1 l2 =
match (l1,l2) with
([],_) -> l2
| (_,[]) -> l1
| (a::l', b::l2') ->
if (comp a b)
then a::(fusionne l' l2)
else b::(fusionne l1 l2');;

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

Il suffit alors a l'utilisateur de définir la fonction de comparaison pour ensuite faire appel à <tt>tri_fusion</tt>.

Par exemple, pour trier dans un ordre décroissant :
<source lang="ocaml">
let dec a n = if a>=n then true
else false ;
</source>
ou même plus simplement
<source lang="ocaml">
let dec = (>=) ;;
</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 = (snd a) <= (snd n) ;;
</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 : <tt>[(-2, 2); (-2, 8); (5, -8); (5, 8); (5, 3)]</tt>

stable : <tt>[(-2, 8); (-2, 2); (5, 3); (5, 8); (5, -8)]</tt>

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.

==Le TD3==

 Exercice 1 : les arbres binaires 

 Question 1 

<source lang="ocaml">
type 'a arbre = Vide | Noeud of 'a*'a arbre*'a arbre ;;
</source>

 
 Question 2 

<source lang="ocaml">
let rec taille a =
match a with
Vide -> 0
|Noeud(e,g,d) -> 1 + (taille g) + (taille d) ;;
</source>

La fonction taille compte le nombre de noeuds que contient un arbre.

 
 Question 3 

<source lang="ocaml">
let rec applique f a =
match a with
Vide -> Vide
|Noeud(e,g,d) -> Noeud(f e,applique f g,applique f d) ;;
</source>

La fonction applique est équivalente à la fonction List.map

 
 Question 4 

<source lang="ocaml">
let rec poids (f : 'a -> int) a =
match a with
Vide -> 0
|Noeud(e,g,d) -> (f e) + (poids f g) + (poids f d) ;;
</source>

 
 Question 5 
<source lang="ocaml">
let rec reduit a o f =
match a with
Vide -> 0
|Noeud(e,g,d) -> let x = reduit g o f in
let y = reduit d o f in
f e x y ;;
</source>

La fonction reduit est equivalente à la fonction List.fold_right pour le type des arbres.

Réécriture de taille et poids :

<source lang="ocaml">
let rec taille a = reduit a 0 (fun e x y -> 1 + x + y) ;;
let rec poids f a = reduit a 0 (fun e x y -> (f e) + (f x) + (f y)) ;; (*?????*)
</source>

 
 Question 6 
<source lang="ocaml">
let rec collecte a =
match a with
Vide -> []
|Noeud(e,g,d) -> e::(collecte g)@(collecte d) ;;
</source>

La fonction collecte récupère tous les éléments de l'arbre et les renvoie sous forme d'une liste.

Avec la fonction reduit :

<source lang="ocaml">
let rec collecte a = reduit a [] (fun e x y -> e::x@y) ;;
</source>

 
 Question 7 
<source lang="ocaml">
let rec feuilles a =
match a with
Vide -> []
|Noeud(e,g,d) -> if (g=Vide && d=Vide) then [e]
else (feuilles g)@(feuilles d) ;;
</source>

Avec reduit :

<source lang="ocaml">
let rec feuilles a = reduit a [] (fun e x y -> if (x=[] && y=[]) then [e]
else x@y) ;;
</source>

 

 Exercice 2 : la tortue 

 Question 1 

<source lang="ocaml">
type action = Forward of int | Left of int | SetPos of int*int | SetHeading of int | PenUp | Pendown ;;
</source>

 
 Question 2 

<source lang="ocaml">
let rec ecrit (l:action list) (pen:bool) : bool =
match l with
[] -> false
|(Forward d)::l -> if (d=0 || pen=false) then ecrit l pen
else true
|PenUp::l -> ecrit l false
|PenDown::l -> ecrit l true
| _ -> ecrit l pen ;;
</source>

La fonction ecrit renvoie true si la tortue écrit qqch ou false sinon.

 
 Question 3 

<source lang="ocaml">
let rec pos (x:int) (y:int) (a:int) (l:action list) : ((int*int)int) =
match l with
[] -> ((x,y),a)
|PenUp::l |Pendown::l -> pos x y a l
|(Left b)::l -> pos x y (a+b) l
|(SetPos(x',y'))::l -> pos x' y' a l
|(SetHeading b)::l -> pos x y b l
|(Forward d)::l -> pos (x+(sin a)*d) (y+(cos a)*d) a l ;;
</source>

 
 Question 5 
<source lang="ocaml">
type action = Forward of int | SetPos of int*int | SetHeading of int | Left of int | PenUp | Pendown | Repeat of int*action list ;;
</source>

==Le TD4==

 Exercice 1 : Petits exercices combinatoires 
Question 3 
 
On commence par créer une fonction intermédiaire.
<source lang="ocaml">
let rec supp' x l =
match l with
[]->[]
|b::f'-> if (x=b) then supp' x l'
else b::supp' x f';;
</source>

<source lang="ocaml">
let rec supp l =
match l with
[]->[]
|a::l'-> a::supp supp' a l';;
</source>
 

 Exercice 2 : Dictionnaires 
Un dictionnaire est une liste de paires 
Question 2 
 
<source lang="ocaml">
let rec insere c v d
match d with
[]->[(c,v)]
|(c',v')::d -> if (c=c') then (c',v')::(insere c v d)
else (c,v)::d ;;
</source>

<source lang="ocaml">
let rec supprime c d
match d with
[]->[]
|(c',v')::d -> if (c=c') then d
else (c',v')::(supprime c d) ;;
</source>

<source lang="ocaml">
let rec existe_cle c d
match d with
[]-> false
|(c',_)::d -> (c=c') || existe_cle c d;;
</source>

<source lang="ocaml">
let rec existe_val v d
match d with
[]-> false
|(_,v')::d -> if (v=v') then true
else existe_val v d;;
</source>

<source lang="ocaml">
let rec recherche_cle c d
match d with
[]-> None
|(c',_)::d -> if (c=c') then Some c'
else recherche_cle c d;;
</source>

<source lang="ocaml">
(* liste des valeurs de c par on peut avoir plusieurs cases, et donc plusieurs clés, avec une même valeur *)
let rec recherche_val v d
match d with
[]->[]
|(c',v')::d -> if (v=v') then c'::(recherche_val v d)
else recherche_val v d;;
</source>

Question 3 
 
<source lang="ocaml">
(* Liste des clés *)
let rec liste_cle c d
match d with
[]-> []
|(c',_)::d -> c'::(liste_cle c d);;

(* Liste des valeurs *)
let rec liste_val v d
match d with
[]->[]
|(_,v')::d -> v'::(liste_val v d);;
</source>

On peut également utiliser des fonctions existantes :
<source lang="ocaml">
(* Liste des clés *)
let liste_cle d = List.map fst;;

(* Liste des valeurs, attention aux doublons! *)
let liste_val d = suppr_doublons(List.map snd);;
</source>

Question 4 
 
<source lang="ocaml">
let rec zip l1 l2
match l1 l2 with
[].[]->[]
|c::lc, v::lv -> (c,v)::(zip lc lv)
|_,_ -> [];;
</source>

Question 5 
 
On aurait pu utiliser une liste triée : si par exemple on cherche 12 et qu'on en est à 14 dans la liste, on sait que 12 n'y est pas. PB : ceci n'empêche pas d'aller à la fin de la liste si la valeur ou la clé recherchée est grande ... 
Une recherche dichotomique est inefficace sur les listes ... 
=> dans la bibliothèque hash table de Caml, il existe un List.zip

 Exercice 3 : Arbres binaires 
Question 1 
 
La profondeur d'un arbre binaire correspond au nombre d'étage : on regarde à partir de la première racine et des sous arbres, on calcule la profondeur à gauche et la profondeur à droite, on prend la plus grande et on y ajoute 1.
<source lang="ocaml">
let rec profondeur a
match a with
Vide -> 0
|Noeud(_,g,d) -> 1 + max(profondeurg) (profondeurd);;
</source>

Question 2 
 
<source lang="ocaml">
let rec equilibre a
match a with
Vide -> true
|Noeud(_,g,d) -> if (profondeur g)=(profondeur d) || (profondeur g)=(profondeur d +1) || (profondeur g +1)=(profondeur d)
then (equilibre d)&&(equilibre g)
else false;;
</source>

Question 3 
 
<source lang="ocaml">
let rec present e a
match a with
Vide -> false
|Noeud(e',g,d) -> e'=e || present e g || present e d;;
</source>

Question 4 
 
<source lang="ocaml">
let rec present e a
match a with
Vide -> false
|Noeud(e',g,d) -> if (e'=e) then true
else if (e<e') then present e g
else present e d;;
</source>

Question 5 
 
<source lang="ocaml">
let rec insere e a
match a with
Vide -> e
|Noeud(e',g,d) -> if (e<e') then insere e g
else insere e d;;
</source>

==Le TP2==
Partie 1 
QUESTION 1 : 
la fonction suivante permet de calculer les ensemble de nombre. Elle est réalisé à l'aide d'une concaténation de la liste précédente avec la liste modifier ainsi que List.map.
 

<source lang="ocaml">
open List

let rec sous_ensemble n=
if n=0
then
[[]]
else
let liste = sous_ensemble (n-1) in (List.map (fun l->n::l) liste) @ liste

</source>
 

QUESTION 2 : 
la fonction supprime doublon est réalisé tout d'abord en triant la liste puis en regardant si deux éléments concécutif sont les mêmes, si oui on en supprime un.
 

<source lang="ocaml">
let rec lstTrier liste=
match liste with
[]->[]
| [a]->liste
| a::b::liste->if a=b then lstTrier (a::liste)
else a::lstTrier (b::liste)

let supprime_doublon lst=
lstTrier (List.sort (-) lst)

</source>
 

Partie 2 
QUESTION 1 : 
la fonction taille calcul la taille d'un arbre, on incrémente un compteur dès que l'on rencontre un noeud. 

<source lang="ocaml">

let rec taille (arbre:'a arbre)=
match arbre with
Vide -> 0
| Noeud(_,a,b) -> 1 + taille a+taille b

</source>
 

la fonction applique permet d'appliquer une fonction a tous les éléments d'un arbre. 

<source lang="ocaml">
let rec applique (fc:'a->'b) arbre=
match arbre with
Vide->Vide
| Noeud(a,b,c)->Noeud (fc a,applique fc b,applique fc c )

</source>
 

la fonction fold renvoie le contenu des feuilles composant l'arbre. 

<source lang="ocaml">

let rec fold (f:'a->'b->'b->'b) arbre n=
match arbre with
Vide->n
| Noeud (a,b,c)->f a(fold f b n) (fold f c n)

</source>
 

QUESTION 2 : 
la fonction feuille crée une liste à partir des éléments retourné par la fonction fold. 

<source lang="ocaml">

let rec feuilles (f:'a arbre->'a list) arbre=
fold (fun a b c-> if(b=[])&&(c=[])
then [a]
else (b@c)) arbre[]

</source>
 

QUESTION 3 : 
cette fonction permet de créer un arbre à partir d'une liste, elle regarde la taille des branches afin de pouvoir inserer les éléments de façon à avoir le moins de noeuds possible. 

<source lang="ocaml">

let rec insert arbre aInsert=
match arbre with
Vide->Noeud (aInsert,Vide,Vide)
| Noeud (a,b,c)->if (taille b < taille c) then Noeud(a,(insert b aInsert),c) else Noeud(a,b,(insert c aInsert))

let rec construit_arbre_int liste arbre=
match liste with
[a]->insert arbre a
| a::liste->construit_arbre_int liste (insert arbre a)

let construit_arbre liste=
construit_arbre_int liste Vide

</source>
 

QUESTION 4 : 
la fonction se divise en deux partie : l'une permet d'obtenir la taille minimal d'une branche et l'autre la taille maximal, la fonction affiche ensuite les résultats. 

<source lang="ocaml">

let rec calcMax arbre compt=
match arbre with
Vide->compt
| Noeud (a,b,c)->if (taille b > taille c) then calcMax b compt+1 else calcMax c compt+1

let rec calcMin arbre compt=
match arbre with
Vide->compt
| Noeud (a,b,c)->if (taille b < taille c) then calcMax b compt+1 else calcMax c compt+1

let profondeurs arbre=
(calcMax arbre 0 , calcMin arbre 0)

</source>
 

QUESTION 5 : 
la fonction tailleR est la fonction tille pour les arbres binaires. 
nous pouvons remarquer que la fonction applique pourrait rendre un arbre binaire faux. 

<source lang="ocaml">

type 'a abr = Vide | Noeud of 'a abr * 'a* 'a abr

let rec tailleR abr=
match abr with
Vide -> 0
| Noeud(a,_,b) -> 1 + tailleR a+tailleR b

</source>
 

QUESTION 6 : 
la fonction ajoute permet d'ajouter une donnée en conservant un arbre binaire.
<source lang="ocaml">

let rec ajoute arbre aInsert=
match arbre with
Vide->Noeud (Vide,aInsert,Vide)
| Noeud (a,b,c)->if aInsert
 
QUESTION 7: 
la fonction supp utilise aissi la fonction ajoute afin de conserver un arbre binaire.

<source lang="ocaml">

let rec supp arbre aSupp=
match arbre with
Vide->Vide
| Noeud (a,b,c)->
if (aSupp=b)
then
if (a=Vide&&c=Vide)
then Vide
else
if (a=Vide&&c!=Vide)
then supp c aSupp
else
if (a!=Vide&&c=Vide)
then supp a aSupp
else
ajouteArbre c a
else Noeud((supp a aSupp),b,(supp c aSupp))

</source>
 

QUESTION 8: 
afin de verifier si un arbre est binaire on effectue deux match simultané a tous les noeuds rencontrés en parcourant l'arbre.
<source lang="ocaml">

let rec verifabr arbre=
match arbre with
Vide->true
| Noeud (a,b,c)->
match a with
Vide->true
| Noeud (a2,b2,c2)->if b2true
| Noeud (a3,b3,c3)->if b3>b then verifabr c else false

</source>

==Contrôle continu 1==
'''Partie 2'''

'''Queston 1'''

cette fonction s'applique a tout les elements d'une liste

'''let rec pam0 a l '''=
match l with []->[]
|f::l->(f a)::(pam0 a l);;

la meme fonction mais cette fois on utilise Fold_right

''' let pam a l''' = List.fold_right(fun f t ->(f a)::t)l [];;

ou encore la version avec List.map,elle a le meme type que pam
'''let pam1 a''' = List.map(fun f->f a);;

'''Question 2'''

'''let rec seq i n''' = if nint->int list,cette fonction créee une liste
d'entier consecutifs et concatène un element en fin de liste par exemple::
seq 5 14;;
'''-:int list''' = [5;6;7;8;9;10;11;12;13;14]
mais a partir de 5 chriffres l'execution met plus d'une demi seconde

essayons la version simple
'''let rec seq1 i n''' = if n<i then [] else i::(seq(i+1)n);;

la version recursive terminale avec un accumulateur nous permettons d'avoir
une execution rapide de la fonction

'''let seq2 i n''' =
''' let rec aux i n acc '''=
if n<i then acc
else aux i(n-1) (n::acc)
in
aux i n [];;

'''Partie 3'''
suite de robinson
ecrivons d'abord une iteration qui nous permet de repéter
l'action sur la fonction
'''let rec iter f n x''' = if n=0 then x else iter f(n-1)(f x);;
ensuite la fonction suivant pour passer d'un terme a l'autre
''' let suivant u '''=
(*nous avons aussi la fonction aux permettant de compter le nombre de fois
ou d apparait dans n*)
''' let rec aux u n d '''= match u with []->n::d::[]
|a::u when a=d -> aux u (n+1) d
|a::u->n::d::(aux u 1 a)
in
'''let u '''= List.sort(fun x y->y-x)u (*et la fonction u qui nous permet de trier par ordre
decroissant en utilisant List.sort*)
in
match u with []->[]
|a::u-> aux u 1 a;;

==Le TP3==
'''Partie 1'''

'''Queston 1'''
Déclaration du type pour les tas ( 'a tas )
<source lang="ocaml">type 'a tas = Vide | Noeud of 'a * 'a tas * 'a tas ;;</source>
La fonction pour tester si un élement de type 'a tas est effectivement un tas :
<source lang="ocaml">let rec test tas vPrec = match tas with
Noeud(v,t1,t2) -> if v >= vPrec
then ((test t1 v)&(test t2 v))
else false
|Vide -> true

let testTas tas = match tas with
Noeud(v,_,_) -> test tas v
|Vide -> true </source>

'''Queston 2'''
Pour cette question nous allons écrire 3 fonctions.
La première a pour but de supprimer le premier élément du tas (donc le plus petit), la seconde a pour but de retourner la valeur du premier élément du tas.

<source lang="ocaml">(*Enleve le premier element du tas

Explication du nom de variables
tgv -> tas gauche valeur ( valeur du tas de gauche)
tgg -> tas gauche gauche ( le tas gauche du tas gauche)
tgd -> tas gauche droit ( le tas droit du tas gauche)
*)
let rec enlever tas = match tas with
Vide -> Vide (* Si le tas est vide on retourne le tas Vide *)
| Noeud (v,Vide,td) -> td (* Si le tas gauche est Vide on retourne le tas droit *)
| Noeud (v,tg,Vide) -> tg (* Si le tas droit est Vide on retourne le tas gauche *)
| Noeud (v, (Noeud (tgv,tgg,tgd) as tg),
(Noeud (tdv,tdg,tdd) as td)) (* Si aucun des deux tas est vide *)
-> if tgv < tdv
then Noeud (tgv, enlever tg, td)
else Noeud (tdv, tg, enlever td);;
</source>

<source lang="ocaml">
(* Renvoie la valeur du premier element du tas *)
let premier tas = match tas with
Vide -> raise Tas_Vide
| Noeud(v,_,_) -> v ;;
</source>

On combine ces deux fonctions pour crée la fonction demandée.
<source lang="ocaml">
let min_tas tas = ((premier tas),(enlever tas));;
</source>

'''Queston 3'''
Nous allons crée un fonction qui va calculer la taille de la plus petite branche du tas et de la plus grande branche du tas.
<source lang="ocaml">
(* compare les taille max et les taille min des tas calculé par la fonction tailleTas *)
let compare a b = match (a,b) with
((amin,amax),(bmin,bmax)) -> ((min amin bmin),(max amax bmax));;

(* ajoute 1 a la taille du tas *)
let add a = match a with
(min,max)-> ((min+1),(max+1));;

(* retourne la taille max et la taille min d'un tas *)
let rec tailleTas tas = match tas with
Vide -> (0,0)
| Noeud(_,tg,td) -> add (compare (tailleTas tg) (tailleTas td));;
</source>

Ensuite il suffit d'utiliser cette fonction sur le tas et de comparer l'écart entre la branche la plus courte et la branche la plus longue.
<source lang="ocaml">
let equilibre tas = match (tailleTas tas) with
(min,max) -> (max - min)<2 ;; (* on calcule la difference entre max et min et on test si elle est inférieur à 2 *)
</source>

'''Queston 4'''
<source lang="ocaml">
(* ajoute un element a un tas *)
let rec ajouter v tas = match tas with
Vide -> Noeud (v,Vide,Vide)
| Noeud (tv,tg,td) -> Noeud( min tv v, td, ajouter (max tv v) tg);;
</source>
on insère systématiquement dans le tas de droite, mais on permute le tas de gauche et le tas de droite a chaque fois pour "mélanger" le tas et avoir un tas équilibré

'''Queston 5'''
<source lang="ocaml">
(* ajoute une liste d’elements a un tas *)
let rec ajList liste tas = match liste with
[] -> tas
| v::l' -> ajouter v (ajList l' tas);;
</source>
Il s'agit d'une simple fonction récursive qui parcours la liste et fais appel a la fonction ajouter pour chaque élément de la liste.

''à finir''

'''Queston 6'''
Pour implémenter le tri par tas, nous allons commencer par créer une fonction qui vide un tas et renvoie le contenu de celui-ci dans une liste triée.
<source lang="ocaml">
(* vide un tas et renvoie le contenu du tas dans une liste triée *)
let rec viderTas tas = match tas with
Vide -> []
| Noeud (x,_,_) -> (premier tas)::(viderTas (enlever tas)) ;;
</source>

Il nous suffit maintenant de crée un tas avec la liste en utilisant la fonction ajList, et de passer la liste ainsi crée en paramètre a la fonction viderTas.
<source lang="ocaml">
(* tri la liste passée en paramètre avec la méthode du tri par tas *)
let triTas lst = viderTas (ajList lst Vide);;
</source>

''à finir''

==Le TD5==

==Le TP4==

==TD6==

INFO401 corr TD TP

2009-05-22T11:54:33Z

Laurent corantin : /* Le TP2 */

==Préliminaires==

Pour afficher correctement dans le wiki, allez voir un peu comment on fait. Vous pouvez regarder par exemple sur le [[INFO401 | wiki du cours]] ou directement sur des articles de [http://fr.wikipedia.org/wiki/Accueil Wikipedia]. La documentation de mediawiki se trouve [http://meta.wikimedia.org/wiki/Aide:Éditeur ici].

Un truc important : pour rentrer du code Caml, il faut mettre les balises <tt><nowiki><source lang="ocaml">...</source></nowiki>"</tt> autour de votre code. Allez par exemple voir le début de la section sur [[#Le TD1 et le TP0 | 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 <math>!n = 1\times2\times \cdots \times n</math> 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 <tt>rec</tt> 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 "<tt>function</tt>" plutôt que <tt>fun</tt>,
* le symbole "<tt>|</tt>",
* le mot clé "<tt>when</tt>".

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 <math>i^i</math>, 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 "<tt>int -> fun -> int</tt>"

 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 u0=0 u1=1 et un+2=un+1+un.

<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 <tt>fib 37</tt> 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 2n 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 (<tt>dragon 11 100 100 400 400</tt>), 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. --[[Utilisateur:Nicolas|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">
(* la fonction renvoie une valeur de type int*int :
- la première composante est la valeur de Fibonacci pour n,
- la seconde composante est le nonbre d'appels recursifs effectués *)
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. On peut résumer le principe commun dans la fonction suivante :
<source lang="ocaml">
let rec reduit l o f =
match l with
[] -> o
| a :: l -> let appel_rec = reduit l o f in
f a appel_rec
</source>
''NB :'' le type de <tt>reduit</tt> donné par Caml est : <tt>val reduit : 'a list -> 'b -> ('a -> 'b -> 'b) -> 'b = <fun></tt>

'''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 0 f
</source>

<source lang="ocaml">
let app g l =
let f a r = (g a)::r in
reduit l [] f
</source>

<source lang="ocaml">
let cat l1 l2 =
let f a r = a :: r in
reduit l1 l2 f
</source>

On peut également introduire la fonction directement avec un <tt>fun</tt> de la maniere suivante :
<source lang="ocaml">
let renverse l = reduit l [] (fun a r -> r @ [a])
</source>
 
'''Question 7 :''' 

Le type de la fonction reduit est: ( 'a -> 'b -> 'b ) -> 'a list 
Celui de la fonction List.fold_right est: ( 'a -> 'b -> 'b ) -> 'a list -> 'b -> 'b ;
 
 
l'ordre des arguments de fold_right est le même que l'ordre des arguments de reduit. La fonction fold_right compte juste deux arguments supplémentaires.

 
'''Question 8 :''' 

Voici la fonction fold_left:
<source lang="ocaml">
let rec fold_left f b l=
match l with
[]->b
|a::l -> fold_left f (f b a) l;;
</source>
 
Cette fonction est ''récursive terminale'', de type ( 'a -> 'b -> 'a ) -> 'a -> 'b list -> 'a .

==Le TP1 - début==

Le sujet [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info401/tp1.pdf 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">
# 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">
# fib 7 ;;
fib <-- 7
fib <-- 5
fib <-- 3
fib <-- 1
...
fib --> 3
fib --> 5
fib --> 8
fib --> 13
- : int = 13
</source>
<source lang="ocaml">
# 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 :

<source lang="ocaml">
let fib n = fst ( fib2 n ) ;;
</source>

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éfinies en utilisant <tt>List.fold_right</tt> :

<source lang="ocaml">
let longueur l = let f a r = 1 + r in List.fold_right f l 0
</source>
<source lang="ocaml">
let app f l = let f' a r = ( f a )::r in List.fold_right f' l []
</source>
<source lang="ocaml">
let concat 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 la fonction <tt>List.rev</tt> de Caml, 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 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 <tt>reverse</tt> met environ 15s alors que <tt>List.rev</tt> s'exécute immédiatement.

Cela montre donc que <tt>List.rev</tt> est bien plus efficace que <tt>reverse</tt>.

::En fait, reverse fait ( n + n-1 + n-2 + ... + 1 ) opérations à chaque fois (il met le premier élément au bout de la liste et ainsi de suite) , soit au total <math>n*(n+1)/2 \sim n^2</math> opérations.

<tt>List.rev</tt> utilise la fonction suivante :

<source lang="ocaml">
let rec rev_append l1 l2 =
match l1 with
[] -> l2
| a::l -> rev_append l (a::l2);;

let rec rev l = rev_append l [];;
</source>

Elle fait donc environ <math>n</math> opérations.

'''Partie 3 : Deux algorithmes de tri pour les listes'''

Question 1

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

<source lang="ocaml">
let rec insertion n l =
match l with
[] -> [n]
| a::l' -> if n<=a
then n::l
else a::(insertion n l') ;;
</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 "<tt>a::l</tt>", on commence par trier (récursivement) la liste <tt>l</tt>, puis on insère
l'élément <tt>a</tt> dans le résultat.

<source lang="ocaml">
let rec tri_insertion l =
match l with
[] -> []
| a::l' -> insertion a (tri_insertion l') ;;
</source>

ou plus simplement :

<source lang="ocaml">
let tri l = List.fold.right insertion l [] ;;
</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 <tt>(l1,l2)</tt> et regrouper les cas d'un des listes vides ensemble :

<source lang="ocaml">
let rec fusionnebis l1 l2 =
match l1,l2 with
[],l | l,[] -> l
| (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 liste_aleatoire n =
let rec aux n max =
if n=0
then []
else (Random.int max)::aux (n-1) max
in
aux n n ;;
</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.

:''Remarque :'' cela vient du fait que le tri fusion divise la taille de la liste par deux à chaque étape, alors que le tri par insertion soustrait un élément à chaque étape.
: On peut montrer que le temps de calcul pour le tri fusion est proportionnel à <math>n \log(n)</math>, ce qui est très petit par rapport à <math>n^2</math> (temps d'execution moyen du tri par insertion) quand <math>n</math> est grand.

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 fusion 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 fusionne comp l1 l2 =
match (l1,l2) with
([],_) -> l2
| (_,[]) -> l1
| (a::l', b::l2') ->
if (comp a b)
then a::(fusionne l' l2)
else b::(fusionne l1 l2');;

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

Il suffit alors a l'utilisateur de définir la fonction de comparaison pour ensuite faire appel à <tt>tri_fusion</tt>.

Par exemple, pour trier dans un ordre décroissant :
<source lang="ocaml">
let dec a n = if a>=n then true
else false ;
</source>
ou même plus simplement
<source lang="ocaml">
let dec = (>=) ;;
</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 = (snd a) <= (snd n) ;;
</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 : <tt>[(-2, 2); (-2, 8); (5, -8); (5, 8); (5, 3)]</tt>

stable : <tt>[(-2, 8); (-2, 2); (5, 3); (5, 8); (5, -8)]</tt>

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.

==Le TD3==

 Exercice 1 : les arbres binaires 

 Question 1 

<source lang="ocaml">
type 'a arbre = Vide | Noeud of 'a*'a arbre*'a arbre ;;
</source>

 
 Question 2 

<source lang="ocaml">
let rec taille a =
match a with
Vide -> 0
|Noeud(e,g,d) -> 1 + (taille g) + (taille d) ;;
</source>

La fonction taille compte le nombre de noeuds que contient un arbre.

 
 Question 3 

<source lang="ocaml">
let rec applique f a =
match a with
Vide -> Vide
|Noeud(e,g,d) -> Noeud(f e,applique f g,applique f d) ;;
</source>

La fonction applique est équivalente à la fonction List.map

 
 Question 4 

<source lang="ocaml">
let rec poids (f : 'a -> int) a =
match a with
Vide -> 0
|Noeud(e,g,d) -> (f e) + (poids f g) + (poids f d) ;;
</source>

 
 Question 5 
<source lang="ocaml">
let rec reduit a o f =
match a with
Vide -> 0
|Noeud(e,g,d) -> let x = reduit g o f in
let y = reduit d o f in
f e x y ;;
</source>

La fonction reduit est equivalente à la fonction List.fold_right pour le type des arbres.

Réécriture de taille et poids :

<source lang="ocaml">
let rec taille a = reduit a 0 (fun e x y -> 1 + x + y) ;;
let rec poids f a = reduit a 0 (fun e x y -> (f e) + (f x) + (f y)) ;; (*?????*)
</source>

 
 Question 6 
<source lang="ocaml">
let rec collecte a =
match a with
Vide -> []
|Noeud(e,g,d) -> e::(collecte g)@(collecte d) ;;
</source>

La fonction collecte récupère tous les éléments de l'arbre et les renvoie sous forme d'une liste.

Avec la fonction reduit :

<source lang="ocaml">
let rec collecte a = reduit a [] (fun e x y -> e::x@y) ;;
</source>

 
 Question 7 
<source lang="ocaml">
let rec feuilles a =
match a with
Vide -> []
|Noeud(e,g,d) -> if (g=Vide && d=Vide) then [e]
else (feuilles g)@(feuilles d) ;;
</source>

Avec reduit :

<source lang="ocaml">
let rec feuilles a = reduit a [] (fun e x y -> if (x=[] && y=[]) then [e]
else x@y) ;;
</source>

 

 Exercice 2 : la tortue 

 Question 1 

<source lang="ocaml">
type action = Forward of int | Left of int | SetPos of int*int | SetHeading of int | PenUp | Pendown ;;
</source>

 
 Question 2 

<source lang="ocaml">
let rec ecrit (l:action list) (pen:bool) : bool =
match l with
[] -> false
|(Forward d)::l -> if (d=0 || pen=false) then ecrit l pen
else true
|PenUp::l -> ecrit l false
|PenDown::l -> ecrit l true
| _ -> ecrit l pen ;;
</source>

La fonction ecrit renvoie true si la tortue écrit qqch ou false sinon.

 
 Question 3 

<source lang="ocaml">
let rec pos (x:int) (y:int) (a:int) (l:action list) : ((int*int)int) =
match l with
[] -> ((x,y),a)
|PenUp::l |Pendown::l -> pos x y a l
|(Left b)::l -> pos x y (a+b) l
|(SetPos(x',y'))::l -> pos x' y' a l
|(SetHeading b)::l -> pos x y b l
|(Forward d)::l -> pos (x+(sin a)*d) (y+(cos a)*d) a l ;;
</source>

 
 Question 5 
<source lang="ocaml">
type action = Forward of int | SetPos of int*int | SetHeading of int | Left of int | PenUp | Pendown | Repeat of int*action list ;;
</source>

==Le TD4==

 Exercice 1 : Petits exercices combinatoires 
Question 3 
 
On commence par créer une fonction intermédiaire.
<source lang="ocaml">
let rec supp' x l =
match l with
[]->[]
|b::f'-> if (x=b) then supp' x l'
else b::supp' x f';;
</source>

<source lang="ocaml">
let rec supp l =
match l with
[]->[]
|a::l'-> a::supp supp' a l';;
</source>
 

 Exercice 2 : Dictionnaires 
Un dictionnaire est une liste de paires 
Question 2 
 
<source lang="ocaml">
let rec insere c v d
match d with
[]->[(c,v)]
|(c',v')::d -> if (c=c') then (c',v')::(insere c v d)
else (c,v)::d ;;
</source>

<source lang="ocaml">
let rec supprime c d
match d with
[]->[]
|(c',v')::d -> if (c=c') then d
else (c',v')::(supprime c d) ;;
</source>

<source lang="ocaml">
let rec existe_cle c d
match d with
[]-> false
|(c',_)::d -> (c=c') || existe_cle c d;;
</source>

<source lang="ocaml">
let rec existe_val v d
match d with
[]-> false
|(_,v')::d -> if (v=v') then true
else existe_val v d;;
</source>

<source lang="ocaml">
let rec recherche_cle c d
match d with
[]-> None
|(c',_)::d -> if (c=c') then Some c'
else recherche_cle c d;;
</source>

<source lang="ocaml">
(* liste des valeurs de c par on peut avoir plusieurs cases, et donc plusieurs clés, avec une même valeur *)
let rec recherche_val v d
match d with
[]->[]
|(c',v')::d -> if (v=v') then c'::(recherche_val v d)
else recherche_val v d;;
</source>

Question 3 
 
<source lang="ocaml">
(* Liste des clés *)
let rec liste_cle c d
match d with
[]-> []
|(c',_)::d -> c'::(liste_cle c d);;

(* Liste des valeurs *)
let rec liste_val v d
match d with
[]->[]
|(_,v')::d -> v'::(liste_val v d);;
</source>

On peut également utiliser des fonctions existantes :
<source lang="ocaml">
(* Liste des clés *)
let liste_cle d = List.map fst;;

(* Liste des valeurs, attention aux doublons! *)
let liste_val d = suppr_doublons(List.map snd);;
</source>

Question 4 
 
<source lang="ocaml">
let rec zip l1 l2
match l1 l2 with
[].[]->[]
|c::lc, v::lv -> (c,v)::(zip lc lv)
|_,_ -> [];;
</source>

Question 5 
 
On aurait pu utiliser une liste triée : si par exemple on cherche 12 et qu'on en est à 14 dans la liste, on sait que 12 n'y est pas. PB : ceci n'empêche pas d'aller à la fin de la liste si la valeur ou la clé recherchée est grande ... 
Une recherche dichotomique est inefficace sur les listes ... 
=> dans la bibliothèque hash table de Caml, il existe un List.zip

 Exercice 3 : Arbres binaires 
Question 1 
 
La profondeur d'un arbre binaire correspond au nombre d'étage : on regarde à partir de la première racine et des sous arbres, on calcule la profondeur à gauche et la profondeur à droite, on prend la plus grande et on y ajoute 1.
<source lang="ocaml">
let rec profondeur a
match a with
Vide -> 0
|Noeud(_,g,d) -> 1 + max(profondeurg) (profondeurd);;
</source>

Question 2 
 
<source lang="ocaml">
let rec equilibre a
match a with
Vide -> true
|Noeud(_,g,d) -> if (profondeur g)=(profondeur d) || (profondeur g)=(profondeur d +1) || (profondeur g +1)=(profondeur d)
then (equilibre d)&&(equilibre g)
else false;;
</source>

Question 3 
 
<source lang="ocaml">
let rec present e a
match a with
Vide -> false
|Noeud(e',g,d) -> e'=e || present e g || present e d;;
</source>

Question 4 
 
<source lang="ocaml">
let rec present e a
match a with
Vide -> false
|Noeud(e',g,d) -> if (e'=e) then true
else if (e<e') then present e g
else present e d;;
</source>

Question 5 
 
<source lang="ocaml">
let rec insere e a
match a with
Vide -> e
|Noeud(e',g,d) -> if (e<e') then insere e g
else insere e d;;
</source>

==Le TP2==
Partie 1 
QUESTION 1 : 
la fonction suivante permet de calculer les ensemble de nombre. Elle est réalisé à l'aide d'une concaténation de la liste précédente avec la liste modifier ainsi que List.map.
 

<source lang="ocaml">
open List

let rec sous_ensemble n=
if n=0
then
[[]]
else
let liste = sous_ensemble (n-1) in (List.map (fun l->n::l) liste) @ liste

</source>
 

QUESTION 2 : 
la fonction supprime doublon est réalisé tout d'abord en triant la liste puis en regardant si deux éléments concécutif sont les mêmes, si oui on en supprime un.
 

<source lang="ocaml">
let rec lstTrier liste=
match liste with
[]->[]
| [a]->liste
| a::b::liste->if a=b then lstTrier (a::liste)
else a::lstTrier (b::liste)

let supprime_doublon lst=
lstTrier (List.sort (-) lst)

</source>
 

Partie 2 
QUESTION 1 : 
la fonction taille calcul la taille d'un arbre, on incrémente un compteur dès que l'on rencontre un noeud. 

<source lang="ocaml">

let rec taille (arbre:'a arbre)=
match arbre with
Vide -> 0
| Noeud(_,a,b) -> 1 + taille a+taille b

</source>
 

la fonction applique permet d'appliquer une fonction a tous les éléments d'un arbre. 

<source lang="ocaml">
let rec applique (fc:'a->'b) arbre=
match arbre with
Vide->Vide
| Noeud(a,b,c)->Noeud (fc a,applique fc b,applique fc c )

</source>
 

la fonction fold renvoie le contenu des feuilles composant l'arbre. 

<source lang="ocaml">

let rec fold (f:'a->'b->'b->'b) arbre n=
match arbre with
Vide->n
| Noeud (a,b,c)->f a(fold f b n) (fold f c n)

</source>
 

QUESTION 2 : 
la fonction feuille crée une liste à partir des éléments retourné par la fonction fold. 

<source lang="ocaml">

let rec feuilles (f:'a arbre->'a list) arbre=
fold (fun a b c-> if(b=[])&&(c=[])
then [a]
else (b@c)) arbre[]

</source>
 

QUESTION 3 : 
cette fonction permet de créer un arbre à partir d'une liste, elle regarde la taille des branches afin de pouvoir inserer les éléments de façon à avoir le moins de noeuds possible. 

<source lang="ocaml">

let rec insert arbre aInsert=
match arbre with
Vide->Noeud (aInsert,Vide,Vide)
| Noeud (a,b,c)->if (taille b < taille c) then Noeud(a,(insert b aInsert),c) else Noeud(a,b,(insert c aInsert))

let rec construit_arbre_int liste arbre=
match liste with
[a]->insert arbre a
| a::liste->construit_arbre_int liste (insert arbre a)

let construit_arbre liste=
construit_arbre_int liste Vide

</source>
 

QUESTION 4 : 
la fonction se divise en deux partie : l'une permet d'obtenir la taille minimal d'une branche et l'autre la taille maximal, la fonction affiche ensuite les résultats. 

<source lang="ocaml">

let rec calcMax arbre compt=
match arbre with
Vide->compt
| Noeud (a,b,c)->if (taille b > taille c) then calcMax b compt+1 else calcMax c compt+1

let rec calcMin arbre compt=
match arbre with
Vide->compt
| Noeud (a,b,c)->if (taille b < taille c) then calcMax b compt+1 else calcMax c compt+1

let profondeurs arbre=
(calcMax arbre 0 , calcMin arbre 0)

</source>
 

QUESTION 5 : 
la fonction tailleR est la fonction tille pour les arbres binaires. 
nous pouvons remarquer que la fonction applique pourrait rendre un arbre binaire faux. 

<source lang="ocaml">

type 'a abr = Vide | Noeud of 'a abr * 'a* 'a abr

let rec tailleR abr=
match abr with
Vide -> 0
| Noeud(a,_,b) -> 1 + tailleR a+tailleR b

</source>
 

QUESTION 6 : 
la fonction ajoute permet d'ajouter une donnée en conservant un arbre binaire.
<source>

let rec ajoute arbre aInsert=
match arbre with
Vide->Noeud (Vide,aInsert,Vide)
| Noeud (a,b,c)->if aInsert
 
QUESTION 7: 
la fonction supp utilise aissi la fonction ajoute afin de conserver un arbre binaire.

<source>

let rec supp arbre aSupp=
match arbre with
Vide->Vide
| Noeud (a,b,c)->
if (aSupp=b)
then
if (a=Vide&&c=Vide)
then Vide
else
if (a=Vide&&c!=Vide)
then supp c aSupp
else
if (a!=Vide&&c=Vide)
then supp a aSupp
else
ajouteArbre c a
else Noeud((supp a aSupp),b,(supp c aSupp))

</source>
 

QUESTION 8: 
afin de verifier si un arbre est binaire on effectue deux match simultané a tous les noeuds rencontrés en parcourant l'arbre.
<source>

let rec verifabr arbre=
match arbre with
Vide->true
| Noeud (a,b,c)->
match a with
Vide->true
| Noeud (a2,b2,c2)->if b2true
| Noeud (a3,b3,c3)->if b3>b then verifabr c else false

</source>

==Contrôle continu 1==
'''Partie 2'''

'''Queston 1'''

cette fonction s'applique a tout les elements d'une liste

'''let rec pam0 a l '''=
match l with []->[]
|f::l->(f a)::(pam0 a l);;

la meme fonction mais cette fois on utilise Fold_right

''' let pam a l''' = List.fold_right(fun f t ->(f a)::t)l [];;

ou encore la version avec List.map,elle a le meme type que pam
'''let pam1 a''' = List.map(fun f->f a);;

'''Question 2'''

'''let rec seq i n''' = if nint->int list,cette fonction créee une liste
d'entier consecutifs et concatène un element en fin de liste par exemple::
seq 5 14;;
'''-:int list''' = [5;6;7;8;9;10;11;12;13;14]
mais a partir de 5 chriffres l'execution met plus d'une demi seconde

essayons la version simple
'''let rec seq1 i n''' = if n<i then [] else i::(seq(i+1)n);;

la version recursive terminale avec un accumulateur nous permettons d'avoir
une execution rapide de la fonction

'''let seq2 i n''' =
''' let rec aux i n acc '''=
if n<i then acc
else aux i(n-1) (n::acc)
in
aux i n [];;

'''Partie 3'''
suite de robinson
ecrivons d'abord une iteration qui nous permet de repéter
l'action sur la fonction
'''let rec iter f n x''' = if n=0 then x else iter f(n-1)(f x);;
ensuite la fonction suivant pour passer d'un terme a l'autre
''' let suivant u '''=
(*nous avons aussi la fonction aux permettant de compter le nombre de fois
ou d apparait dans n*)
''' let rec aux u n d '''= match u with []->n::d::[]
|a::u when a=d -> aux u (n+1) d
|a::u->n::d::(aux u 1 a)
in
'''let u '''= List.sort(fun x y->y-x)u (*et la fonction u qui nous permet de trier par ordre
decroissant en utilisant List.sort*)
in
match u with []->[]
|a::u-> aux u 1 a;;

==Le TP3==
'''Partie 1'''

'''Queston 1'''
Déclaration du type pour les tas ( 'a tas )
<source lang="ocaml">type 'a tas = Vide | Noeud of 'a * 'a tas * 'a tas ;;</source>
La fonction pour tester si un élement de type 'a tas est effectivement un tas :
<source lang="ocaml">let rec test tas vPrec = match tas with
Noeud(v,t1,t2) -> if v >= vPrec
then ((test t1 v)&(test t2 v))
else false
|Vide -> true

let testTas tas = match tas with
Noeud(v,_,_) -> test tas v
|Vide -> true </source>

'''Queston 2'''
Pour cette question nous allons écrire 3 fonctions.
La première a pour but de supprimer le premier élément du tas (donc le plus petit), la seconde a pour but de retourner la valeur du premier élément du tas.

<source lang="ocaml">(*Enleve le premier element du tas

Explication du nom de variables
tgv -> tas gauche valeur ( valeur du tas de gauche)
tgg -> tas gauche gauche ( le tas gauche du tas gauche)
tgd -> tas gauche droit ( le tas droit du tas gauche)
*)
let rec enlever tas = match tas with
Vide -> Vide (* Si le tas est vide on retourne le tas Vide *)
| Noeud (v,Vide,td) -> td (* Si le tas gauche est Vide on retourne le tas droit *)
| Noeud (v,tg,Vide) -> tg (* Si le tas droit est Vide on retourne le tas gauche *)
| Noeud (v, (Noeud (tgv,tgg,tgd) as tg),
(Noeud (tdv,tdg,tdd) as td)) (* Si aucun des deux tas est vide *)
-> if tgv < tdv
then Noeud (tgv, enlever tg, td)
else Noeud (tdv, tg, enlever td);;
</source>

<source lang="ocaml">
(* Renvoie la valeur du premier element du tas *)
let premier tas = match tas with
Vide -> raise Tas_Vide
| Noeud(v,_,_) -> v ;;
</source>

On combine ces deux fonctions pour crée la fonction demandée.
<source lang="ocaml">
let min_tas tas = ((premier tas),(enlever tas));;
</source>

'''Queston 3'''
Nous allons crée un fonction qui va calculer la taille de la plus petite branche du tas et de la plus grande branche du tas.
<source lang="ocaml">
(* compare les taille max et les taille min des tas calculé par la fonction tailleTas *)
let compare a b = match (a,b) with
((amin,amax),(bmin,bmax)) -> ((min amin bmin),(max amax bmax));;

(* ajoute 1 a la taille du tas *)
let add a = match a with
(min,max)-> ((min+1),(max+1));;

(* retourne la taille max et la taille min d'un tas *)
let rec tailleTas tas = match tas with
Vide -> (0,0)
| Noeud(_,tg,td) -> add (compare (tailleTas tg) (tailleTas td));;
</source>

Ensuite il suffit d'utiliser cette fonction sur le tas et de comparer l'écart entre la branche la plus courte et la branche la plus longue.
<source lang="ocaml">
let equilibre tas = match (tailleTas tas) with
(min,max) -> (max - min)<2 ;; (* on calcule la difference entre max et min et on test si elle est inférieur à 2 *)
</source>

'''Queston 4'''
<source lang="ocaml">
(* ajoute un element a un tas *)
let rec ajouter v tas = match tas with
Vide -> Noeud (v,Vide,Vide)
| Noeud (tv,tg,td) -> Noeud( min tv v, td, ajouter (max tv v) tg);;
</source>
on insère systématiquement dans le tas de droite, mais on permute le tas de gauche et le tas de droite a chaque fois pour "mélanger" le tas et avoir un tas équilibré

'''Queston 5'''
<source lang="ocaml">
(* ajoute une liste d’elements a un tas *)
let rec ajList liste tas = match liste with
[] -> tas
| v::l' -> ajouter v (ajList l' tas);;
</source>
Il s'agit d'une simple fonction récursive qui parcours la liste et fais appel a la fonction ajouter pour chaque élément de la liste.

''à finir''

'''Queston 6'''
Pour implémenter le tri par tas, nous allons commencer par créer une fonction qui vide un tas et renvoie le contenu de celui-ci dans une liste triée.
<source lang="ocaml">
(* vide un tas et renvoie le contenu du tas dans une liste triée *)
let rec viderTas tas = match tas with
Vide -> []
| Noeud (x,_,_) -> (premier tas)::(viderTas (enlever tas)) ;;
</source>

Il nous suffit maintenant de crée un tas avec la liste en utilisant la fonction ajList, et de passer la liste ainsi crée en paramètre a la fonction viderTas.
<source lang="ocaml">
(* tri la liste passée en paramètre avec la méthode du tri par tas *)
let triTas lst = viderTas (ajList lst Vide);;
</source>

''à finir''

==Le TD5==

==Le TP4==

==TD6==

INFO401 corr TD TP

2009-05-03T11:38:00Z

Laurent corantin :

==Préliminaires==

Pour afficher correctement dans le wiki, allez voir un peu comment on fait. Vous pouvez regarder par exemple sur le [[INFO401 | wiki du cours]] ou directement sur des articles de [http://fr.wikipedia.org/wiki/Accueil Wikipedia]. La documentation de mediawiki se trouve [http://meta.wikimedia.org/wiki/Aide:Éditeur ici].

Un truc important : pour rentrer du code Caml, il faut mettre les balises <tt><nowiki><source lang="ocaml">...</source></nowiki>"</tt> autour de votre code. Allez par exemple voir le début de la section sur [[#Le TD1 et le TP0 | 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 <math>!n = 1\times2\times \cdots \times n</math> 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 <tt>rec</tt> 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 "<tt>function</tt>" plutôt que <tt>fun</tt>,
* le symbole "<tt>|</tt>",
* le mot clé "<tt>when</tt>".

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 <math>i^i</math>, 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 "<tt>int -> fun -> int</tt>"

 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 u0=0 u1=1 et un+2=un+1+un.

<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 <tt>fib 37</tt> 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 2n 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 (<tt>dragon 11 100 100 400 400</tt>), 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. --[[Utilisateur:Nicolas|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">
(* la fonction renvoie une valeur de type int*int :
- la première composante est la valeur de Fibonacci pour n,
- la seconde composante est le nonbre d'appels recursifs effectués *)
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. On peut résumer le principe commun dans la fonction suivante :
<source lang="ocaml">
let rec reduit l o f =
match l with
[] -> o
| a :: l -> let appel_rec = reduit l o f in
f a appel_rec
</source>
''NB :'' le type de <tt>reduit</tt> donné par Caml est : <tt>val reduit : 'a list -> 'b -> ('a -> 'b -> 'b) -> 'b = <fun></tt>

'''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 0 f
</source>

<source lang="ocaml">
let app g l =
let f a r = (g a)::r in
reduit l [] f
</source>

<source lang="ocaml">
let cat l1 l2 =
let f a r = a :: r in
reduit l1 l2 f
</source>

On peut également introduire la fonction directement avec un <tt>fun</tt> de la maniere suivante :
<source lang="ocaml">
let renverse l = reduit l [] (fun a r -> r @ [a])
</source>
 
'''Question 7 :''' 

Le type de la fonction reduit est: ( 'a -> 'b -> 'b ) -> 'a list 
Celui de la fonction List.fold_right est: ( 'a -> 'b -> 'b ) -> 'a list -> 'b -> 'b ;
 
 
l'ordre des arguments de fold_right est le même que l'ordre des arguments de reduit. La fonction fold_right compte juste deux arguments supplémentaires.

 
'''Question 8 :''' 

Voici la fonction fold_left:
<source lang="ocaml">
let rec fold_left f b l=
match l with
[]->b
|a::l -> fold_left f (f b a) l;;
</source>
 
Cette fonction est ''récursive terminale'', de type ( 'a -> 'b -> 'a ) -> 'a -> 'b list -> 'a .

==Le TP1 - début==

Le sujet [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info401/tp1.pdf 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">
# 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">
# fib 7 ;;
fib <-- 7
fib <-- 5
fib <-- 3
fib <-- 1
...
fib --> 3
fib --> 5
fib --> 8
fib --> 13
- : int = 13
</source>
<source lang="ocaml">
# 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 :

<source lang="ocaml">
let fib n = fst ( fib2 n ) ;;
</source>

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éfinies en utilisant <tt>List.fold_right</tt> :

<source lang="ocaml">
let longueur l = let f a r = 1 + r in List.fold_right f l 0
</source>
<source lang="ocaml">
let app f l = let f' a r = ( f a )::r in List.fold_right f' l []
</source>
<source lang="ocaml">
let concat 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 la fonction <tt>List.rev</tt> de Caml, 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 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 <tt>reverse</tt> met environ 15s alors que <tt>List.rev</tt> s'exécute immédiatement.

Cela montre donc que <tt>List.rev</tt> est bien plus efficace que <tt>reverse</tt>.

::En fait, reverse fait ( n + n-1 + n-2 + ... + 1 ) opérations à chaque fois (il met le premier élément au bout de la liste et ainsi de suite) , soit au total <math>n*(n+1)/2 \sim n^2</math> opérations.

<tt>List.rev</tt> utilise la fonction suivante :

<source lang="ocaml">
let rec rev_append l1 l2 =
match l1 with
[] -> l2
| a::l -> rev_append l (a::l2);;

let rec rev l = rev_append l [];;
</source>

Elle fait donc environ <math>n</math> opérations.

'''Partie 3 : Deux algorithmes de tri pour les listes'''

Question 1

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

<source lang="ocaml">
let rec insertion n l =
match l with
[] -> [n]
| a::l' -> if n<=a
then n::l
else a::(insertion n l') ;;
</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 "<tt>a::l</tt>", on commence par trier (récursivement) la liste <tt>l</tt>, puis on insère
l'élément <tt>a</tt> dans le résultat.

<source lang="ocaml">
let rec tri_insertion l =
match l with
[] -> []
| a::l' -> insertion a (tri_insertion l') ;;
</source>

ou plus simplement :

<source lang="ocaml">
let tri l = List.fold.right insertion l [] ;;
</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 <tt>(l1,l2)</tt> et regrouper les cas d'un des listes vides ensemble :

<source lang="ocaml">
let rec fusionnebis l1 l2 =
match l1,l2 with
[],l | l,[] -> l
| (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 liste_aleatoire n =
let rec aux n max =
if n=0
then []
else (Random.int max)::aux (n-1) max
in
aux n n ;;
</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.

:''Remarque :'' cela vient du fait que le tri fusion divise la taille de la liste par deux à chaque étape, alors que le tri par insertion soustrait un élément à chaque étape.
: On peut montrer que le temps de calcul pour le tri fusion est proportionnel à <math>n \log(n)</math>, ce qui est très petit par rapport à <math>n^2</math> (temps d'execution moyen du tri par insertion) quand <math>n</math> est grand.

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 fusion 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 fusionne comp l1 l2 =
match (l1,l2) with
([],_) -> l2
| (_,[]) -> l1
| (a::l', b::l2') ->
if (comp a b)
then a::(fusionne l' l2)
else b::(fusionne l1 l2');;

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

Il suffit alors a l'utilisateur de définir la fonction de comparaison pour ensuite faire appel à <tt>tri_fusion</tt>.

Par exemple, pour trier dans un ordre décroissant :
<source lang="ocaml">
let dec a n = if a>=n then true
else false ;
</source>
ou même plus simplement
<source lang="ocaml">
let dec = (>=) ;;
</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 = (snd a) <= (snd n) ;;
</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 : <tt>[(-2, 2); (-2, 8); (5, -8); (5, 8); (5, 3)]</tt>

stable : <tt>[(-2, 8); (-2, 2); (5, 3); (5, 8); (5, -8)]</tt>

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.

==Le TD3==

 Exercice 1 : les arbres binaires 

 Question 1 

<source lang="ocaml">
type 'a arbre = Vide | Noeud of 'a*'a arbre*'a arbre ;;
</source>

 
 Question 2 

<source lang="ocaml">
let rec taille a =
match a with
Vide -> 0
|Noeud(e,g,d) -> 1 + (taille g) + (taille d) ;;
</source>

La fonction taille compte le nombre de noeuds que contient un arbre.

 
 Question 3 

<source lang="ocaml">
let rec applique f a =
match a with
Vide -> Vide
|Noeud(e,g,d) -> Noeud(f e,applique f g,applique f d) ;;
</source>

La fonction applique est équivalente à la fonction List.map

 
 Question 4 

<source lang="ocaml">
let rec poids (f : 'a -> int) a =
match a with
Vide -> 0
|Noeud(e,g,d) -> (f e) + (poids f g) + (poids f d) ;;
</source>

 
 Question 5 
<source lang="ocaml">
let rec reduit a o f =
match a with
Vide -> 0
|Noeud(e,g,d) -> let x = reduit g o f in
let y = reduit d o f in
f e x y ;;
</source>

La fonction reduit est equivalente à la fonction List.fold_right pour le type des arbres.

Réécriture de taille et poids :

<source lang="ocaml">
let rec taille a = reduit a 0 (fun e x y -> 1 + x + y) ;;
let rec poids f a = reduit a 0 (fun e x y -> (f e) + (f x) + (f y)) ;; (*?????*)
</source>

 
 Question 6 
<source lang="ocaml">
let rec collecte a =
match a with
Vide -> []
|Noeud(e,g,d) -> e::(collecte g)@(collecte d) ;;
</source>

La fonction collecte récupère tous les éléments de l'arbre et les renvoie sous forme d'une liste.

Avec la fonction reduit :

<source lang="ocaml">
let rec collecte a = reduit a [] (fun e x y -> e::x@y) ;;
</source>

 
 Question 7 
<source lang="ocaml">
let rec feuilles a =
match a with
Vide -> []
|Noeud(e,g,d) -> if (g=Vide && d=Vide) then [e]
else (feuilles g)@(feuilles d) ;;
</source>

Avec reduit :

<source lang="ocaml">
let rec feuilles a = reduit a [] (fun e x y -> if (x=[] && y=[]) then [e]
else x@y) ;;
</source>

 

 Exercice 2 : la tortue 

 Question 1 

<source lang="ocaml">
type action = Forward of int | Left of int | SetPos of int*int | SetHeading of int | PenUp | Pendown ;;
</source>

 
 Question 2 

<source lang="ocaml">
let rec ecrit (l:action list) (pen:bool) : bool =
match l with
[] -> false
|(Forward d)::l -> if (d=0 || pen=false) then ecrit l pen
else true
|PenUp::l -> ecrit l false
|PenDown::l -> ecrit l true
| _ -> ecrit l pen ;;
</source>

La fonction ecrit renvoie true si la tortue écrit qqch ou false sinon.

 
 Question 3 

<source lang="ocaml">
let rec pos (x:int) (y:int) (a:int) (l:action list) : ((int*int)int) =
match l with
[] -> ((x,y),a)
|PenUp::l |Pendown::l -> pos x y a l
|(Left b)::l -> pos x y (a+b) l
|(SetPos(x',y'))::l -> pos x' y' a l
|(SetHeading b)::l -> pos x y b l
|(Forward d)::l -> pos (x+(sin a)*d) (y+(cos a)*d) a l ;;
</source>

 
 Question 5 
<source lang="ocaml">
type action = Forward of int | SetPos of int*int | SetHeading of int | Left of int | PenUp | Pendown | Repeat of int*action list ;;
</source>

==Le TD4==

 Exercice 1 : Petits exercices combinatoires 
Question 3 
 
On commence par créer une fonction intermédiaire.
<source lang="ocaml">
let rec supp' x l =
match l with
[]->[]
|b::f'-> if (x=b) then supp' x l'
else b::supp' x f';;
</source>

<source lang="ocaml">
let rec supp l =
match l with
[]->[]
|a::l'-> a::supp supp' a l';;
</source>
 

 Exercice 2 : Dictionnaires 
Un dictionnaire est une liste de paires 
Question 2 
 
<source lang="ocaml">
let rec insere c v d
match d with
[]->[(c,v)]
|(c',v')::d -> if (c=c') then (c',v')::(insere c v d)
else (c,v)::d ;;
</source>

<source lang="ocaml">
let rec supprime c d
match d with
[]->[]
|(c',v')::d -> if (c=c') then d
else (c',v')::(supprime c d) ;;
</source>

<source lang="ocaml">
let rec existe_cle c d
match d with
[]-> false
|(c',_)::d -> (c=c') || existe_cle c d;;
</source>

<source lang="ocaml">
let rec existe_val v d
match d with
[]-> false
|(_,v')::d -> if (v=v') then true
else existe_val v d;;
</source>

<source lang="ocaml">
let rec recherche_cle c d
match d with
[]-> None
|(c',_)::d -> if (c=c') then Some c'
else recherche_cle c d;;
</source>

<source lang="ocaml">
(* liste des valeurs de c par on peut avoir plusieurs cases, et donc plusieurs clés, avec une même valeur *)
let rec recherche_val v d
match d with
[]->[]
|(c',v')::d -> if (v=v') then c'::(recherche_val v d)
else recherche_val v d;;
</source>

Question 3 
 
<source lang="ocaml">
(* Liste des clés *)
let rec liste_cle c d
match d with
[]-> []
|(c',_)::d -> c'::(liste_cle c d);;

(* Liste des valeurs *)
let rec liste_val v d
match d with
[]->[]
|(_,v')::d -> v'::(liste_val v d);;
</source>

On peut également utiliser des fonctions existantes :
<source lang="ocaml">
(* Liste des clés *)
let liste_cle d = List.map fst;;

(* Liste des valeurs, attention aux doublons! *)
let liste_val d = suppr_doublons(List.map snd);;
</source>

Question 4 
 
<source lang="ocaml">
let rec zip l1 l2
match l1 l2 with
[].[]->[]
|c::lc, v::lv -> (c,v)::(zip lc lv)
|_,_ -> [];;
</source>

Question 5 
 
On aurait pu utiliser une liste triée : si par exemple on cherche 12 et qu'on en est à 14 dans la liste, on sait que 12 n'y est pas. PB : ceci n'empêche pas d'aller à la fin de la liste si la valeur ou la clé recherchée est grande ... 
Une recherche dichotomique est inefficace sur les listes ... 
=> dans la bibliothèque hash table de Caml, il existe un List.zip

 Exercice 3 : Arbres binaires 
Question 1 
 
La profondeur d'un arbre binaire correspond au nombre d'étage : on regarde à partir de la première racine et des sous arbres, on calcule la profondeur à gauche et la profondeur à droite, on prend la plus grande et on y ajoute 1.
<source lang="ocaml">
let rec profondeur a
match a with
Vide -> 0
|Noeud(_,g,d) -> 1 + max(profondeurg) (profondeurd);;
</source>

Question 2 
 
<source lang="ocaml">
let rec equilibre a
match a with
Vide -> true
|Noeud(_,g,d) -> if (profondeur g)=(profondeur d) || (profondeur g)=(profondeur d +1) || (profondeur g +1)=(profondeur d)
then (equilibre d)&&(equilibre g)
else false;;
</source>

Question 3 
 
<source lang="ocaml">
let rec present e a
match a with
Vide -> false
|Noeud(e',g,d) -> e'=e || present e g || present e d;;
</source>

Question 4 
 
<source lang="ocaml">
let rec present e a
match a with
Vide -> false
|Noeud(e',g,d) -> if (e'=e) then true
else if (e<e') then present e g
else present e d;;
</source>

Question 5 
 
<source lang="ocaml">
let rec insere e a
match a with
Vide -> e
|Noeud(e',g,d) -> if (e<e') then insere e g
else insere e d;;
</source>

==Le TP2==
Partie 1 
QUESTION 1 : 
la fonction suivante permet de calculer les ensemble de nombre. Elle est réalisé à l'aide d'une concaténation de la liste précédente avec la liste modifier ainsi que List.map.
 

<source lang="ocaml">
open List

let rec sous_ensemble n=
if n=0
then
[[]]
else
let liste = sous_ensemble (n-1) in (List.map (fun l->n::l) liste) @ liste

</source>
 

QUESTION 2 : 
la fonction supprime doublon est réalisé tout d'abord en triant la liste puis en regardant si deux éléments concécutif sont les mêmes, si oui on en supprime un.
 

<source lang="ocaml">
let rec lstTrier liste=
match liste with
[]->[]
| [a]->liste
| a::b::liste->if a=b then lstTrier (a::liste)
else a::lstTrier (b::liste)

let supprime_doublon lst=
lstTrier (List.sort (-) lst)

</source>
 

Partie 2 
QUESTION 1 : 
la fonction taille calcul la taille d'un arbre, on incrémente un compteur dès que l'on rencontre un noeud. 

<source lang="ocaml">

let rec taille (arbre:'a arbre)=
match arbre with
Vide -> 0
| Noeud(_,a,b) -> 1 + taille a+taille b

</source>
 

la fonction applique permet d'appliquer une fonction a tous les éléments d'un arbre. 

<source lang="ocaml">
let rec applique (fc:'a->'b) arbre=
match arbre with
Vide->Vide
| Noeud(a,b,c)->Noeud (fc a,applique fc b,applique fc c )

</source>
 

la fonction fold renvoie le contenu des feuilles composant l'arbre. 

<source lang="ocaml">

let rec fold (f:'a->'b->'b->'b) arbre n=
match arbre with
Vide->n
| Noeud (a,b,c)->f a(fold f b n) (fold f c n)

</source>
 

QUESTION 2 : 
la fonction feuille crée une liste à partir des éléments retourné par la fonction fold. 

<source lang="ocaml">

let rec feuilles (f:'a arbre->'a list) arbre=
fold (fun a b c-> if(b=[])&&(c=[])
then [a]
else (b@c)) arbre[]

</source>
 

QUESTION 3 : 
cette fonction permet de créer un arbre à partir d'une liste, elle regarde la taille des branches afin de pouvoir inserer les éléments de façon à avoir le moins de noeuds possible. 

<source lang="ocaml">

let rec insert arbre aInsert=
match arbre with
Vide->Noeud (aInsert,Vide,Vide)
| Noeud (a,b,c)->if (taille b < taille c) then Noeud(a,(insert b aInsert),c) else Noeud(a,b,(insert c aInsert))

let rec construit_arbre_int liste arbre=
match liste with
[a]->insert arbre a
| a::liste->construit_arbre_int liste (insert arbre a)

let construit_arbre liste=
construit_arbre_int liste Vide

</source>
 

QUESTION 4 : 
la fonction se divise en deux partie : l'une permet d'obtenir la taille minimal d'une branche et l'autre la taille maximal, la fonction affiche ensuite les résultats. 

<source lang="ocaml">

let rec calcMax arbre compt=
match arbre with
Vide->compt
| Noeud (a,b,c)->if (taille b > taille c) then calcMax b compt+1 else calcMax c compt+1

let rec calcMin arbre compt=
match arbre with
Vide->compt
| Noeud (a,b,c)->if (taille b < taille c) then calcMax b compt+1 else calcMax c compt+1

let profondeurs arbre=
(calcMax arbre 0 , calcMin arbre 0)

</source>
 

QUESTION 5 : 
la fonction tailleR est la fonction tille pour les arbres binaires. 
nous pouvons remarquer que la fonction applique pourrait rendre un arbre binaire faux. 

<source lang="ocaml">

type 'a abr = Vide | Noeud of 'a abr * 'a* 'a abr

let rec tailleR abr=
match abr with
Vide -> 0
| Noeud(a,_,b) -> 1 + tailleR a+tailleR b

</source>
 
==Contrôle continu 1==

==Le TP3==

==Le TD5==

==Le TP4==

==TD6==

INFO401 corr TD TP

2009-04-30T12:34:20Z

Laurent corantin :

==Préliminaires==

Pour afficher correctement dans le wiki, allez voir un peu comment on fait. Vous pouvez regarder par exemple sur le [[INFO401 | wiki du cours]] ou directement sur des articles de [http://fr.wikipedia.org/wiki/Accueil Wikipedia]. La documentation de mediawiki se trouve [http://meta.wikimedia.org/wiki/Aide:Éditeur ici].

Un truc important : pour rentrer du code Caml, il faut mettre les balises <tt><nowiki><source lang="ocaml">...</source></nowiki>"</tt> autour de votre code. Allez par exemple voir le début de la section sur [[#Le TD1 et le TP0 | 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 <math>!n = 1\times2\times \cdots \times n</math> 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 <tt>rec</tt> 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 "<tt>function</tt>" plutôt que <tt>fun</tt>,
* le symbole "<tt>|</tt>",
* le mot clé "<tt>when</tt>".

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 <math>i^i</math>, 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 "<tt>int -> fun -> int</tt>"

 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 u0=0 u1=1 et un+2=un+1+un.

<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 <tt>fib 37</tt> 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 2n 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 (<tt>dragon 11 100 100 400 400</tt>), 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. --[[Utilisateur:Nicolas|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">
(* la fonction renvoie une valeur de type int*int :
- la première composante est la valeur de Fibonacci pour n,
- la seconde composante est le nonbre d'appels recursifs effectués *)
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. On peut résumer le principe commun dans la fonction suivante :
<source lang="ocaml">
let rec reduit l o f =
match l with
[] -> o
| a :: l -> let appel_rec = reduit l o f in
f a appel_rec
</source>
''NB :'' le type de <tt>reduit</tt> donné par Caml est : <tt>val reduit : 'a list -> 'b -> ('a -> 'b -> 'b) -> 'b = <fun></tt>

'''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 0 f
</source>

<source lang="ocaml">
let app g l =
let f a r = (g a)::r in
reduit l [] f
</source>

<source lang="ocaml">
let cat l1 l2 =
let f a r = a :: r in
reduit l1 l2 f
</source>

On peut également introduire la fonction directement avec un <tt>fun</tt> de la maniere suivante :
<source lang="ocaml">
let renverse l = reduit l [] (fun a r -> r @ [a])
</source>
 
'''Question 7 :''' 

Le type de la fonction reduit est: ( 'a -> 'b -> 'b ) -> 'a list 
Celui de la fonction List.fold_right est: ( 'a -> 'b -> 'b ) -> 'a list -> 'b -> 'b ;
 
 
l'ordre des arguments de fold_right est le même que l'ordre des arguments de reduit. La fonction fold_right compte juste deux arguments supplémentaires.

 
'''Question 8 :''' 

Voici la fonction fold_left:
<source lang="ocaml">
let rec fold_left f b l=
match l with
[]->b
|a::l -> fold_left f (f b a) l;;
</source>
 
Cette fonction est ''récursive terminale'', de type ( 'a -> 'b -> 'a ) -> 'a -> 'b list -> 'a .

==Le TP1 - début==

Le sujet [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info401/tp1.pdf 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">
# 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">
# fib 7 ;;
fib <-- 7
fib <-- 5
fib <-- 3
fib <-- 1
...
fib --> 3
fib --> 5
fib --> 8
fib --> 13
- : int = 13
</source>
<source lang="ocaml">
# 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 :

<source lang="ocaml">
let fib n = fst ( fib2 n ) ;;
</source>

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éfinies en utilisant <tt>List.fold_right</tt> :

<source lang="ocaml">
let longueur l = let f a r = 1 + r in List.fold_right f l 0
</source>
<source lang="ocaml">
let app f l = let f' a r = ( f a )::r in List.fold_right f' l []
</source>
<source lang="ocaml">
let concat 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 la fonction <tt>List.rev</tt> de Caml, 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 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 <tt>reverse</tt> met environ 15s alors que <tt>List.rev</tt> s'exécute immédiatement.

Cela montre donc que <tt>List.rev</tt> est bien plus efficace que <tt>reverse</tt>.

::En fait, reverse fait ( n + n-1 + n-2 + ... + 1 ) opérations à chaque fois (il met le premier élément au bout de la liste et ainsi de suite) , soit au total <math>n*(n+1)/2 \sim n^2</math> opérations.

<tt>List.rev</tt> utilise la fonction suivante :

<source lang="ocaml">
let rec rev_append l1 l2 =
match l1 with
[] -> l2
| a::l -> rev_append l (a::l2);;

let rec rev l = rev_append l [];;
</source>

Elle fait donc environ <math>n</math> opérations.

'''Partie 3 : Deux algorithmes de tri pour les listes'''

Question 1

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

<source lang="ocaml">
let rec insertion n l =
match l with
[] -> [n]
| a::l' -> if n<=a
then n::l
else a::(insertion n l') ;;
</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 "<tt>a::l</tt>", on commence par trier (récursivement) la liste <tt>l</tt>, puis on insère
l'élément <tt>a</tt> dans le résultat.

<source lang="ocaml">
let rec tri_insertion l =
match l with
[] -> []
| a::l' -> insertion a (tri_insertion l') ;;
</source>

ou plus simplement :

<source lang="ocaml">
let tri l = List.fold.right insertion l [] ;;
</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 <tt>(l1,l2)</tt> et regrouper les cas d'un des listes vides ensemble :

<source lang="ocaml">
let rec fusionnebis l1 l2 =
match l1,l2 with
[],l | l,[] -> l
| (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 liste_aleatoire n =
let rec aux n max =
if n=0
then []
else (Random.int max)::aux (n-1) max
in
aux n n ;;
</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.

:''Remarque :'' cela vient du fait que le tri fusion divise la taille de la liste par deux à chaque étape, alors que le tri par insertion soustrait un élément à chaque étape.
: On peut montrer que le temps de calcul pour le tri fusion est proportionnel à <math>n \log(n)</math>, ce qui est très petit par rapport à <math>n^2</math> (temps d'execution moyen du tri par insertion) quand <math>n</math> est grand.

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 fusion 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 fusionne comp l1 l2 =
match (l1,l2) with
([],_) -> l2
| (_,[]) -> l1
| (a::l', b::l2') ->
if (comp a b)
then a::(fusionne l' l2)
else b::(fusionne l1 l2');;

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

Il suffit alors a l'utilisateur de définir la fonction de comparaison pour ensuite faire appel à <tt>tri_fusion</tt>.

Par exemple, pour trier dans un ordre décroissant :
<source lang="ocaml">
let dec a n = if a>=n then true
else false ;
</source>
ou même plus simplement
<source lang="ocaml">
let dec = (>=) ;;
</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 = (snd a) <= (snd n) ;;
</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 : <tt>[(-2, 2); (-2, 8); (5, -8); (5, 8); (5, 3)]</tt>

stable : <tt>[(-2, 8); (-2, 2); (5, 3); (5, 8); (5, -8)]</tt>

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.

==Le TD3==

 Exercice 1 : les arbres binaires 

 Question 1 

<source lang="ocaml">
type 'a arbre = Vide | Noeud of 'a*'a arbre*'a arbre ;;
</source>

 
 Question 2 

<source lang="ocaml">
let rec taille a =
match a with
Vide -> 0
|Noeud(e,g,d) -> 1 + (taille g) + (taille d) ;;
</source>

La fonction taille compte le nombre de noeuds que contient un arbre.

 
 Question 3 

<source lang="ocaml">
let rec applique f a =
match a with
Vide -> Vide
|Noeud(e,g,d) -> Noeud(f e,applique f g,applique f d) ;;
</source>

La fonction applique est équivalente à la fonction List.map

 
 Question 4 

<source lang="ocaml">
let rec poids (f : 'a -> int) a =
match a with
Vide -> 0
|Noeud(e,g,d) -> (f e) + (poids f g) + (poids f d) ;;
</source>

 
 Question 5 
<source lang="ocaml">
let rec reduit a o f =
match a with
Vide -> 0
|Noeud(e,g,d) -> let x = reduit g o f in
let y = reduit d o f in
f e x y ;;
</source>

La fonction reduit est equivalente à la fonction List.fold_right pour le type des arbres.

Réécriture de taille et poids :

<source lang="ocaml">
let rec taille a = reduit a 0 (fun e x y -> 1 + x + y) ;;
let rec poids f a = reduit a 0 (fun e x y -> (f e) + (f x) + (f y)) ;; (*?????*)
</source>

 
 Question 6 
<source lang="ocaml">
let rec collecte a =
match a with
Vide -> []
|Noeud(e,g,d) -> e::(collecte g)@(collecte d) ;;
</source>

La fonction collecte récupère tous les éléments de l'arbre et les renvoie sous forme d'une liste.

Avec la fonction reduit :

<source lang="ocaml">
let rec collecte a = reduit a [] (fun e x y -> e::x@y) ;;
</source>

 
 Question 7 
<source lang="ocaml">
let rec feuilles a =
match a with
Vide -> []
|Noeud(e,g,d) -> if (g=Vide && d=Vide) then [e]
else (feuilles g)@(feuilles d) ;;
</source>

Avec reduit :

<source lang="ocaml">
let rec feuilles a = reduit a [] (fun e x y -> if (x=[] && y=[]) then [e]
else x@y) ;;
</source>

 

 Exercice 2 : la tortue 

 Question 1 

<source lang="ocaml">
type action = Forward of int | Left of int | SetPos of int*int | SetHeading of int | PenUp | Pendown ;;
</source>

 
 Question 2 

<source lang="ocaml">
let rec ecrit (l:action list) (pen:bool) : bool =
match l with
[] -> false
|(Forward d)::l -> if (d=0 || pen=false) then ecrit l pen
else true
|PenUp::l -> ecrit l false
|PenDown::l -> ecrit l true
| _ -> ecrit l pen ;;
</source>

La fonction ecrit renvoie true si la tortue écrit qqch ou false sinon.

 
 Question 3 

<source lang="ocaml">
let rec pos (x:int) (y:int) (a:int) (l:action list) : ((int*int)int) =
match l with
[] -> ((x,y),a)
|PenUp::l |Pendown::l -> pos x y a l
|(Left b)::l -> pos x y (a+b) l
|(SetPos(x',y'))::l -> pos x' y' a l
|(SetHeading b)::l -> pos x y b l
|(Forward d)::l -> pos (x+(sin a)*d) (y+(cos a)*d) a l ;;
</source>

 
 Question 5 
<source lang="ocaml">
type action = Forward of int | SetPos of int*int | SetHeading of int | Left of int | PenUp | Pendown | Repeat of int*action list ;;
</source>

==Le TD4==

 Exercice 1 : Petits exercices combinatoires 
Question 3 
 
On commence par créer une fonction intermédiaire.
<source lang="ocaml">
let rec supp' x l =
match l with
[]->[]
|b::f'-> if (x=b) then supp' x l'
else b::supp' x f';;
</source>

<source lang="ocaml">
let rec supp l =
match l with
[]->[]
|a::l'-> a::supp supp' a l';;
</source>
 

 Exercice 2 : Dictionnaires 
Un dictionnaire est une liste de paires 
Question 2 
 
<source lang="ocaml">
let rec insere c v d
match d with
[]->[(c,v)]
|(c',v')::d -> if (c=c') then (c',v')::(insere c v d)
else (c,v)::d ;;
</source>

<source lang="ocaml">
let rec supprime c d
match d with
[]->[]
|(c',v')::d -> if (c=c') then d
else (c',v')::(supprime c d) ;;
</source>

<source lang="ocaml">
let rec existe_cle c d
match d with
[]-> false
|(c',_)::d -> (c=c') || existe_cle c d;;
</source>

<source lang="ocaml">
let rec existe_val v d
match d with
[]-> false
|(_,v')::d -> if (v=v') then true
else existe_val v d;;
</source>

<source lang="ocaml">
let rec recherche_cle c d
match d with
[]-> None
|(c',_)::d -> if (c=c') then Some c'
else recherche_cle c d;;
</source>

<source lang="ocaml">
(* liste des valeurs de c par on peut avoir plusieurs cases, et donc plusieurs clés, avec une même valeur *)
let rec recherche_val v d
match d with
[]->[]
|(c',v')::d -> if (v=v') then c'::(recherche_val v d)
else recherche_val v d;;
</source>

Question 3 
 
<source lang="ocaml">
(* Liste des clés *)
let rec liste_cle c d
match d with
[]-> []
|(c',_)::d -> c'::(liste_cle c d);;

(* Liste des valeurs *)
let rec liste_val v d
match d with
[]->[]
|(_,v')::d -> v'::(liste_val v d);;
</source>

On peut également utiliser des fonctions existantes :
<source lang="ocaml">
(* Liste des clés *)
let liste_cle d = List.map fst;;

(* Liste des valeurs, attention aux doublons! *)
let liste_val d = suppr_doublons(List.map snd);;
</source>

Question 4 
 
<source lang="ocaml">
let rec zip l1 l2
match l1 l2 with
[].[]->[]
|c::lc, v::lv -> (c,v)::(zip lc lv)
|_,_ -> [];;
</source>

Question 5 
 
On aurait pu utiliser une liste triée : si par exemple on cherche 12 et qu'on en est à 14 dans la liste, on sait que 12 n'y est pas. PB : ceci n'empêche pas d'aller à la fin de la liste si la valeur ou la clé recherchée est grande ... 
Une recherche dichotomique est inefficace sur les listes ... 
=> dans la bibliothèque hash table de Caml, il existe un List.zip

 Exercice 3 : Arbres binaires 
Question 1 
 
La profondeur d'un arbre binaire correspond au nombre d'étage : on regarde à partir de la première racine et des sous arbres, on calcule la profondeur à gauche et la profondeur à droite, on prend la plus grande et on y ajoute 1.
<source lang="ocaml">
let rec profondeur a
match a with
Vide -> 0
|Noeud(_,g,d) -> 1 + max(profondeurg) (profondeurd);;
</source>

Question 2 
 
<source lang="ocaml">
let rec equilibre a
match a with
Vide -> true
|Noeud(_,g,d) -> if (profondeur g)=(profondeur d) || (profondeur g)=(profondeur d +1) || (profondeur g +1)=(profondeur d)
then (equilibre d)&&(equilibre g)
else false;;
</source>

Question 3 
 
<source lang="ocaml">
let rec present e a
match a with
Vide -> false
|Noeud(e',g,d) -> e'=e || present e g || present e d;;
</source>

Question 4 
 
<source lang="ocaml">
let rec present e a
match a with
Vide -> false
|Noeud(e',g,d) -> if (e'=e) then true
else if (e<e') then present e g
else present e d;;
</source>

Question 5 
 
<source lang="ocaml">
let rec insere e a
match a with
Vide -> e
|Noeud(e',g,d) -> if (e<e') then insere e g
else insere e d;;
</source>

==Le TP2==
Partie 1 
QUESTION 1 : 
la fonction suivante permet de calculer les ensemble de nombre. Elle est réalisé à l'aide d'une concaténation de la liste précédente avec la liste modifier ainsi que List.map.
 
<source lang="ocaml">
open List

let rec sous_ensemble n=
if n=0
then
[[]]
else
let liste = sous_ensemble (n-1) in (List.map (fun l->n::l) liste) @ liste

</source>
 
QUESTION 2 : 
la fonction supprime doublon est réalisé tout d'abord en triant la liste puis en regardant si deux éléments concécutif sont les mêmes, si oui on en supprime un.
 
<source lang="ocaml">
let rec lstTrier liste=
match liste with
[]->[]
| [a]->liste
| a::b::liste->if a=b then lstTrier (a::liste)
else a::lstTrier (b::liste)

let supprime_doublon lst=
lstTrier (List.sort (-) lst)
</source>
 
Partie 2 
QUESTION

==Contrôle continu 1==

==Le TP3==

==Le TD5==

==Le TP4==

==TD6==

INFO401 corr TD TP

2009-04-28T13:00:12Z

Laurent corantin :

INFO401 corr TD TP

2009-04-28T12:59:36Z

Laurent corantin :

Discussion:INFO421 : Programmation fonctionnelle

2009-01-21T12:40:15Z

Laurent corantin :

== Comment commencer une discussion ==

Pour commencer une discussion, il suffit de cliquer sur le '''<tt>+</tt>''' en haut de la page. Vous pouvez alors rentrer un sujet de discussion et éditer le texte comme pour le wiki.

C'est mieux de signer vos intervention en utilisant l'avant dernier bouton d'édition, ou avec <tt><nowiki>--~~~~</nowiki></tt>.

:Pour répondre, il faut « modifier » la section correspondante...
:Par soucis de visibilité, il est parfois préférable de rajouter une marge à gauche (comme ici). Pour faire ça, il faut commencer votre ligne par un «<tt>:</tt>». (Ou un «<tt>::</tt>»...)

--[[Utilisateur:Hyvernat|Hyvernat]] 12 janvier 2009 à 13:47 (CET)

== Inscription sur le Wiki ==

Voila, c'est juste pour dire que je me suis inscrit...

--[[Utilisateur:Hyvernat|Hyvernat]] 21 janvier 2009 à 11:01 (CET)

coucou c'est moi

Inscription sur le Wiki
--[[Utilisateur:LAYER|LAYER]] 21 janvier 2009 à 13:39 (CET)

inscription terminée --[[Utilisateur:Laurent corantin|Laurent corantin]] 21 janvier 2009 à 13:40 (CET)