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

INFO401 corr TD TP

2009-03-04T10:22:53Z

Caroline : /* Le TP1 - début */

==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">
let rec fib n =
if (n<2) then (n,0)
else let t = fib (n-1) in
let s = fib (n-2) in
(fst t + fst s , snd t + snd s + 1)
</source>
''exemple : ''fib 10 = (55, 88) pour exécuter la fonction Fibonacci(10), il y a 88 appels récursifs nécessaires... 

'''Exercice 2 : Listes''' 
'''Question 5 :''' 
suite à l'étude des fonctions
*longueur
<source lang="ocaml">
let rec longueur l=
match l with
[] ->0
| _ :: l -> 1+longueur l
</source>
*applique
<source lang="ocaml">
let rec app f p =
match p with
[] -> []
| a :: p -> f(a) :: app f p
</source>
*concatene
<source lang="ocaml">
let rec cat l1 l2 =
match l1 with
[] -> l2
| a :: l -> a :: (cat l l2)
</source>
*renverse,
<source lang="ocaml">
let rec renverse l =
match l with
[] -> []
| a :: l -> (renverse l)@[a]
</source>
on remarque des similitudes. Ces fonctions ont le même schéma de base ( celui de la fonction reduit)
<source lang="ocaml">
let rec reduit l o f =
match l with
[] -> o
| a :: l -> f a (reduit l o f)
</source>
''NB :'' val reduit : 'a list -> 'b -> ('a -> 'b -> 'b) -> 'b = <fun>

'''Question 6 :''' 
Reprogrammons les fonctions précédentes à partir de la fonction reduit ! 
<source lang="ocaml">
let longueur l =
let f _ r = 1 + r in
reduit l o f
</source>

<source lang="ocaml">
let app g l =
let f
reduit l [] f
</source>

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

<source lang="ocaml">
let renverse l =
let f r a = [r]@[a]
reduit l [] f
</source>

==Le TP1 - début==

Le sujet [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.

Question 4 ( Bonus )

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

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

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

--- à venir ---

'''Partie 2 : Manipulation des listes'''

Question 1

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

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

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

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

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

Question 2

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

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

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

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

<source lang="ocaml">
let rec liste_ordonnée l n =
if n=0 then l
else g l (n-1) @ [n] ;;
</source>

Ou encore

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

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

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

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

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

Question 1

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

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

Question 2

On programme ensuite le tri par insertion.

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

- la liste vide est triée,

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

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

Question 3

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

<source lang="ocaml">
let rec fusionne l1 l2 =
match l1 with
[]->l2
|a::l' -> begin
match l2 with
[]-> l1
|b::l'' -> if a<=b then ( a::fusionne l' l2 )
else ( b::fusionne l1 l'')

end;;
</source>

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

<source lang="ocaml">
let rec fusionnebis l1 l2 =
match (l1,l2) with
([],_)->l2
|(_,[])->l1
|(a::l', b::l2')->
if a 

Question 4

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

<source lang="ocaml">
let rec separe l =
match l with
[]->([],[])
|[a]->([a],[])
|a::b::l' -> let t=separe l' in (a::(fst t),b::(snd t)) ;;
</source>

Question 5

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

Le tri fusion fonctionne de la manière suivante :

- la liste vide est triée,

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

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

Question 6

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

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

<source lang="ocaml">
let rec créé_list n =
if n=0 then []
else (Random.int n)::créé_list(n-1) ;;
</source>

Ensuite on trie cette liste avec les deux fonctions.

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

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

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

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

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

Question 7

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

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

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

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

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

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

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

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

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

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

Question 8 ( Bonus )

--- à venir ---

INFO401 corr TD TP

2009-03-04T09:51:29Z

Caroline : /* Le TP1 - début */

==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">
let rec fib n =
if (n<2) then (n,0)
else let t = fib (n-1) in
let s = fib (n-2) in
(fst t + fst s , snd t + snd s + 1)
</source>
''exemple : ''fib 10 = (55, 88) pour exécuter la fonction Fibonacci(10), il y a 88 appels récursifs nécessaires... 

'''Exercice 2 : Listes''' 
'''Question 5 :''' 
suite à l'étude des fonctions
*longueur
<source lang="ocaml">
let rec longueur l=
match l with
[] ->0
| _ :: l -> 1+longueur l
</source>
*applique
<source lang="ocaml">
let rec app f p =
match p with
[] -> []
| a :: p -> f(a) :: app f p
</source>
*concatene
<source lang="ocaml">
let rec cat l1 l2 =
match l1 with
[] -> l2
| a :: l -> a :: (cat l l2)
</source>
*renverse,
<source lang="ocaml">
let rec renverse l =
match l with
[] -> []
| a :: l -> (renverse l)@[a]
</source>
on remarque des similitudes. Ces fonctions ont le même schéma de base ( celui de la fonction reduit)
<source lang="ocaml">
let rec reduit l o f =
match l with
[] -> o
| a :: l -> f a (reduit l o f)
</source>
''NB :'' val reduit : 'a list -> 'b -> ('a -> 'b -> 'b) -> 'b = <fun>

'''Question 6 :''' 
Reprogrammons les fonctions précédentes à partir de la fonction reduit ! 
<source lang="ocaml">
let longueur l =
let f _ r = 1 + r in
reduit l o f
</source>

<source lang="ocaml">
let app g l =
let f
reduit l [] f
</source>

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

<source lang="ocaml">
let renverse l =
let f r a = [r]@[a]
reduit l [] f
</source>

==Le TP1 - début==

Le sujet [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.

Question 4 ( Bonus )

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

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

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

--- à venir ---

'''Partie 2 : Manipulation des listes'''

Question 1

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

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

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

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

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

Question 2

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

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

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

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

<source lang="ocaml">
let rec liste_ordonnée l n =
if n=0 then l
else g l (n-1) @ [n] ;;
</source>

Ou encore

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

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

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

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

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

Question 1

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

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

Question 2

On programme ensuite le tri par insertion.

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

- la liste vide est triée,

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

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

Question 3

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

<source lang="ocaml">
let rec fusionne l1 l2 =
match l1 with
[]->l2
|a::l' -> begin
match l2 with
[]-> l1
|b::l'' -> if a<=b then ( a::fusionne l' l2 )
else ( b::fusionne l1 l'')

end;;
</source>

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

<source lang="ocaml">
let rec fusionnebis l1 l2 =
match (l1,l2) with
([],_)->l2
|(_,[])->l1
|(a::l', b::l2')->
if a 

Question 4

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

<source lang="ocaml">
let rec separe l =
match l with
[]->([],[])
|[a]->([a],[])
|a::b::l' -> let t=separe l' in (a::(fst t),b::(snd t)) ;;
</source>

Question 5

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

Le tri fusion fonctionne de la manière suivante :

- la liste vide est triée,

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

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

Question 6

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

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

<source lang="ocaml">
let rec créé_list n =
if n=0 then []
else (Random.int n)::créé_list(n-1) ;;
</source>

Ensuite on trie cette liste avec les deux fonctions.

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

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

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

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

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

Question 7

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

--- à venir ---

Question 8 ( Bonus )

--- à venir ---

INFO401 corr TD TP

2009-03-04T09:38:52Z

Caroline :

==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">
let rec fib n =
if (n<2) then (n,0)
else let t = fib (n-1) in
let s = fib (n-2) in
(fst t + fst s , snd t + snd s + 1)
</source>
''exemple : ''fib 10 = (55, 88) pour exécuter la fonction Fibonacci(10), il y a 88 appels récursifs nécessaires... 

'''Exercice 2 : Listes''' 
'''Question 5 :''' 
suite à l'étude des fonctions
*longueur
<source lang="ocaml">
let rec longueur l=
match l with
[] ->0
| _ :: l -> 1+longueur l
</source>
*applique
<source lang="ocaml">
let rec app f p =
match p with
[] -> []
| a :: p -> f(a) :: app f p
</source>
*concatene
<source lang="ocaml">
let rec cat l1 l2 =
match l1 with
[] -> l2
| a :: l -> a :: (cat l l2)
</source>
*renverse,
<source lang="ocaml">
let rec renverse l =
match l with
[] -> []
| a :: l -> (renverse l)@[a]
</source>
on remarque des similitudes. Ces fonctions ont le même schéma de base ( celui de la fonction reduit)
<source lang="ocaml">
let rec reduit l o f =
match l with
[] -> o
| a :: l -> f a (reduit l o f)
</source>
''NB :'' val reduit : 'a list -> 'b -> ('a -> 'b -> 'b) -> 'b = <fun>

'''Question 6 :''' 
Reprogrammons les fonctions précédentes à partir de la fonction reduit ! 
<source lang="ocaml">
let longueur l =
let f _ r = 1 + r in
reduit l o f
</source>

<source lang="ocaml">
let app g l =
let f
reduit l [] f
</source>

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

<source lang="ocaml">
let renverse l =
let f r a = [r]@[a]
reduit l [] f
</source>

==Le TP1 - début==

Le sujet [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.

Question 4 ( Bonus )

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

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

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

--- à venir ---

'''Partie 2 : Manipulation des listes'''

Question 1

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

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

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

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

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

Question 2

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

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

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

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

<source lang="ocaml">
let rec liste_ordonnée l n =
if n=0 then l
else g l (n-1) @ [n] ;;
</source>

Ou encore

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

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

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

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

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

Question 1

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

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

Question 2

On programme ensuite le tri par insertion.

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

- la liste vide est triée,

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

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

Question 3

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

<source lang="ocaml">
let rec fusionne l1 l2 =
match l1 with
[]->l2
|a::l' -> begin
match l2 with
[]-> l1
|b::l'' -> if a<=b then ( a::fusionne l' l2 )
else ( b::fusionne l1 l'')

end;;
</source>

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

<source lang="ocaml">
let rec fusionnebis l1 l2 =
match (l1,l2) with
([],_)->l2
|(_,[])->l1
|(a::l', b::l2')->
if a 

Question 4

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

<source lang="ocaml">
let rec separe l =
match l with
[]->([],[])
|[a]->([a],[])
|a::b::l' -> let t=separe l' in (a::(fst t),b::(snd t)) ;;
</source>

Question 5

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

Le tri fusion fonctionne de la manière suivante :

- la liste vide est triée,

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

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

Question 6

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

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

<source lang="ocaml">
let rec créé_list n =
if n=0 then []
else (Random.int n)::créé_list(n-1) ;;
</source>

Ensuite on trie cette liste avec les deux fonctions.

Le tri_fusion renvoie instantanément une liste de 10000 élèments aléatoires triés.
Le tri_insertion, quant à lui, prend plus d'une dizaine de secondes.

Cela semble logique dans le sens où le tri_fusion fait plusieurs calculs simultanés :
il sépare chaque liste en 2 listes distinctes, qu'il resépare en 2 listes distinctes, etc...
Il effectue des calculs simultanés sur des plus petites listes.

Question 7

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

--- à venir ---

Question 8 ( Bonus )

--- à venir ---

INFO421 : Programmation fonctionnelle

2009-03-04T09:07:13Z

Caroline :

Ce wiki est un complément de cours pour le cours « info-401 : programmation fonctionnelle ». La participation au wiki est fortement encouragée, et deviendra peut-être obligatoire...

Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Utilisez votre vrai nom...)

Je vous conseille d'aller voir [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

==Détails techniques==

===Nouvelles===

Les nouvelles récentes sont en haut de la liste...

* [[Utilisateur:Hyvernat|Hyvernat]] 9 février 2009 à 14:58 (CET) : '''le changement de jours pour le TP est confirmé : mercredi 11/02 à 13h30 en salle Maurienne 60.'''

* [[Utilisateur:Hyvernat|Hyvernat]] 9 février 2009 à 10:57 (CET) : oups... La manifestation nationale est prévue pour mardi, et non pas mercredi comme je le pensais. Le TP sera probablement déplacé pour mercredi après-midi. (Je vous enverrais un email, et essaierais de venir vous voir en cours pour vous prévenir...)

* [[Utilisateur:Hyvernat|Hyvernat]] 8 février 2009 à 15:59 (CET) : bien que je sois mobilisé contre les projets actuels du gouvernement, nous ferons la séance de TP prévue le mardi 10 février. (Sinon, ca sera compliqué à rattraper...) Je vous encourage à aller faire un peu de lecture [http://www.sauvonslarecherche.fr/ ici] (Sauvons la recherche) ou [http://www.lama.univ-savoie.fr/~mangolte/liens-greve.html là] (liens centralisés par F. Mangolte.

* [[Utilisateur:Hyvernat|Hyvernat]] 8 février 2009 à 15:53 (CET) : comme je vous l'avais annoncé, la séance de contrôle continu prévue dans Planète est supprimée : cette note sera remplacé par une note de participation aux corrections des TD/TP sur le wiki.

* [[Utilisateur:Hyvernat|Hyvernat]] 22 janvier 2009 à 19:05 (CET) : la DSI a modifié des trucs qui devraient supprimer certains des problèmes qu'on a eu en TP. Contactez-moi si vous rencontrez des problèmes en utilisant Emacs et Caml...

* [[Utilisateur:Hyvernat|Hyvernat]] 22 janvier 2009 à 19:05 (CET) : j'ai rajouté une page [[INFO401_corr_TD_TP | correction des TD / TP]].

* [[Utilisateur:Hyvernat|Hyvernat]] 12 janvier 2009 à 09:59 (CET) : création du wiki.

===Organisation des séances===

* séance 1 (12/01/2009). Cours : introduction, programmation fonctionnelle, le langage Caml.
* séance 2 et 3 (19/01/2009).
*# Cours : les valeurs, les types atomiques et fonctionnels (section [[#Les_fonctions | Les fonctions]]).
*# TD1
* séance 4 (21/01/2009) : TP0 : prise en main de Caml.
* séance 5 et 6 (26/01/2009).
*# Cours : les tuples, les listes, un peu de filtrage et de polymorphisme
*# TD2 : tuples et listes, un peu de filtrage, questions 1.1, 1.2 et 1.4.
* séance 7 et 8 (26/12/2009) : suite du TD2.

===Compléments de cours, TD et TP===

<big>
<center>'''[[INFO401 corr TD TP | Corrections (partielles) des TD / TP]]'''</center>
</big>

====Les travaux dirigés====

* feuille de TD1 : [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info401/td1.pdf premières expressions en Caml]

* feuille de TD2 : [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info401/td2.pdf tuples, listes, un peu de filtrage]

====Les travaux pratiques====

=====Ocaml=====

Si vous voulez installer OCaml sur votre ordinateur.

* Sous Linux : c'est la solution idéale. Il existe probablement des paquets pour votre distribution. Pour Ubuntu, pour avoir un environnement similaire à ce que vous aurez dans les salles informatiques, installez les paquets <tt>ocaml</tt>, <tt>ocaml-core</tt>, <tt>ocaml-mode</tt>, <tt>tuareg-mode</tt> et <tt>emacs</tt>.

* Sous Windows : je vous renvoie au tutoriel de Jean-Paul Roy : [http://deptinfo.unice.fr/~roy/CAML/Win/install-win.html Installation de OCaml (sur Windows XP)]. Je n'ai malheureusement (??) pas accès à une machine avec Windows (98/2000/XP/Vista/7), je ne pourrais donc pas beaucoup vous aider.

Contactez moi si vous avez des problèmes.

J'ai créé une petite [http://www.lama.univ-savoie.fr/wiki/index.php?title=INFO401_:_utilisation_Caml page dédiée pour la syntaxe de Caml et son utilisation].

=====TP0 : prise en main de Caml=====

Le TP0 [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info401/tp0.pdf prise en main de Caml], au format pdf.

* le petit fichier pour lancer l'interprète Caml : [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info401/interprete-caml.desktop interprete-caml]. (Pour le sauvegarder : clique droit sur le lien, "<tt>Enregistrer la cible du lien sous...</tt>" ; mettez le sur le bureau, et ne modifiez pas le nom du fichier...)

* [http://caml.inria.fr/pub/docs/manual-ocaml-309/libref/Graphics.html la documentation de la librairie <tt>graphics</tt>].

=====TP1 : programmes récursifs, listes=====

Le TP1 [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info401/tp1.pdf programmes récursifs, listes], au format pdf.

* le [http://www.lama.univ-savoie.fr/~hyvernat/envoi-TP.php lien vers le formulaire d'envoi du TP]

* Une partie de [http://www.lama.univ-savoie.fr/wiki/index.php/INFO401_corr_TD_TP correction] du TP1...A compléter!

====Références supplémentaires====

* Le livre d'Emmanuel Chailloux, Pascal Manoury et Bruno Pagano : [http://www.pps.jussieu.fr/Livres/ora/DA-OCAML/ Développement d'applications avec Ocaml]. (Ce livre utilise une vieille version de Ocaml, mais reste pertinent.)

* La documentation de Caml, version 3.09 (utilisé en TP) : [http://caml.inria.fr/pub/docs/manual-ocaml-309/ Documentation and user's manual].

==Introduction==

Pour paraphraser un collègue dont je ne retrouve pas le nom :

<center>''Attention :'' il ne s'agit pas d'un cours de programmation fonctionelle</center>

Il s'agit plutôt d'un cours de programmation '''fonctionnelle'''...

===Petit historique censuré===

Je ne parlerais pas des langages pré-historiques (cartes perforées, λ-calcul, machines de Turing, ...)

D'après [http://people.ku.edu/~nkinners/LangList/Extras/langlist.htm ce site], qui recense la plupart des langages de programmation, il y aurait plus de 2500 langages ! Voici donc une petite liste de langages importants :

* années 40 : langages d'assemblage (assembleurs). Aussi vieux que les ordinateurs eux-mêmes. Chaque langage d'assemblage est spécifique à une famille de processeurs, ce qui rend les programmes difficiles à ''porter''. (Càd à modifier pour les faire marcher sur d'autres ordinateurs.)
* FORTRAN (1957, toujours utilisé par les numériciens et physiciens) et COBOL (1960, toujours utilisé en gestion). Ces langages ont connus des évolutions mais restent archaïques par leur conception.
* LISP : inventé par John McCarthy en 1958. C'est le premier langage fonctionnel. Toujours utilisé (sous différentes formes), en particulier en intelligence artificielle. Ce langage est basé directement sur le λ-calcul de Church.
* ALGOL (1958, a inspiré de nombreux langages depuis : C, pascal, ...) Le but était de réparer certains défauts des langages de type FORTRAN. (Programmation structurée, blocs, ...)
* Pascal (1975).
* C (1972). Toujours très utilisé, sous différentes variantes (notamment C++).
* Prolog (1972) : programmation logique, paradigme nouveau de programmation. Toujours utilisé par une petite communauté.
* ML (fin des années 1970 ?), qui ajoute une notion de type que LISP n'avait pas.
* Smalltalk (fin des année 1983), début de la programmation objet.
* 1983 : ADA.
* 1983 : Miranda un langage fonctionnel « pur ».
* 1985 : Caml, développé à l'INRIA.
* 1990 : Haskell, inspiré de Miranda.

Je vous conseille d'aller voir le graphique suivant : [http://www.levenez.com/lang/lang.pdf Computer Languages Timeline] (ou [http://www.levenez.com/lang/redirect_lang_a4_pdf.html découpé en pages A4]).

===Fonctionnel ??===

L'adjectif ''fonctionnel'' a au moins deux sens :
# qui fonctionne, en état de marche,
# qui se rapporte aux fonctions.

Les langages fonctionnels sont bien entendus ''fonctionnels'' dans le premier sens, mais c'est surtout le second sens qui nous intéresse. Les langages tels que Pascal, Ada ou C sont qualifié, par opposition, d'''impératifs''.

Un des slogans de la programmation fonctionnelle en général est
<center>''Les fonctions sont des valeurs comme les autres''</center>
et c'est de là que vient la terminologie...

Comme nous le verront, cela a de nombreuses conséquences sur l'expressivité du langage et la manière de programmer.

===Le langage (O)Caml===

Le langage OCaml est développé par l'INRIA (Institut national de recherche en informatique et automatique). C'est un successeur de CamlLight.

Le nom Caml est formé des initiales de "Categorical Abstract Machine Language", et le langage lui même appartient à la famille de ML ("Meta Language"). C'est un langage fonctionnel ''strict'' (nous verrons ce que cela veut dire), typé (nous verrons ce que cela veut dire) qui supporte plusieurs styles de programmation :
* fonctionnel bien sûr,
* mais aussi impératif,
* objet également (c'est le « O » de OCaml).

Dans ce cours, nous utiliserons seulement le style fonctionnel.

Voici quelques aspects importants du langages que nous verrons peut-être pendant le cours :
* fonctions comme valeurs valeurs,
* polymorphisme,
* système d'exceptions,
* système de modules et de foncteurs,
* support pour des références et des données mutables (programmation « impure »),
* ...

Un aspect intéressant du langage est que c'est soit :
* un langage interprété (avec l'interpréteur OCaml),
* soit un langage compilé en bytecode (code binaire indépendant de l'architecture),
* soit un langage compilé optimisé en binaire (dépendant de l'architecture).

On peut donc choisir ce que l'on veut pour ces applications.

===Autres langages fonctionnels===

Il existe de nombreux autres langages fonctionnels. Je vous montrerais peut-être des exemples en cours. Voici quelques exemples importants :
* SML (Standard ML) : [http://en.wikipedia.org/wiki/Standard_ML Wikipedia], autre dialecte de la famille ML.
* LISP, dont les deux dialectes principaux sont :
''' Common LISP : [http://en.wikipedia.org/wiki/Common_LISP Wikipedia],
''' Scheme : [http://en.wikipedia.org/wiki/Scheme_(programming_language) Wikipedia].
* Haskell : [http://en.wikipedia.org/wiki/Haskell_(programming_language) Wikipedia] (inspiré en grande partie de [http://en.wikipedia.org/wiki/Miranda_(programming_language) Miranda]).

===Applications concrètes===

Voici quelques exemples de logiciels développés en OCaml :
* [http://ocsigen.org/ Ocsigen], un serveur web,
* [http://www.cis.upenn.edu/~bcpierce/unison/ Unison], un logiciel de synchronisation de fichiers entre ordinateurs,
* [http://mldonkey.sourceforge.net/Main_Page MLDonkey], un logiciel de Peer-to-peer multiréseaux,
* [http://pauillac.inria.fr/advi/ Active DVI] un visualisateur pour le format de fichier DVI.

La viabilité du paradigme fonctionnel se retrouve également dans le langage Erlang ([http://fr.wikipedia.org/wiki/Erlang_(langage) Wikipedia]), un langage fonctionnel développé par Ericsson pour la programmation concurrente de systèmes temps réels.

D'autre part, l'efficacité des langages fonctionnels peut être constatée sur le [http://shootout.alioth.debian.org/ The Computer Language Benchmarks Game], où différents langages de programmation sont comparés (temps d'exécution, taille du code source et utilisation de la mémoire) sur des taches différentes. Les langages fonctionnels sont toujours bien représentés...

===Objectifs du cours===

# être capable de définir des fonctions récursives, et comprendre ce qu'elles font
# comprendre le typage et le polymorphisme à la ML
# pouvoir définir des fonction d'ordre supérieur pour modulariser votre code
# être capable de décomposer un problème
# comprendre et utiliser la notion de type récursif
# commencer à réfléchir à la complexité de vos programmes

==Premiers pas en Caml==

===Les valeurs===

Un des slogans de la programmation fonctionnelle est ''tout est une valeur, ou plus précisément,
<center>''Tout programme a une valeur.''</center>

Cette idée n'est pas présente en C, et encore moins en Pascal, où l'on distingue les ''expressions'' ("<tt>3*x+f(2)</tt>" par exemple) et les ''instructions'' ("<tt>if (n>22) then a:=12 else a:=13</tt>" par exemple). En Pascal, les instructions sont en général séparées par des "<tt>;</tt>" et sont ''exécutées'' en séquence. Les expressions sont juste calculées, et ne peuvent pas être séquentialisées.

Dans un langage purement fonctionnel, le "<tt>;</tt>" n'existe pas, et il n'y a que des valeurs...

Les valeurs sont formées en utilisant :
* les fonctions du langage (addition, multiplication)
* les opérateurs logiques (qui sont juste des fonctions des booléens vers les booléens),
* les relations mathématiques (égalité, plus grand, ... qui sont juste des fonctions dont le type de retour est le type des booléens),
* les constantes,
* les variables,
* des constructions du langage (<tt>if ... then ... else ...</tt>) par exemple).

Bien entendu, comme Caml est typé, il faut respecter les types.

====Les valeurs de type atomique====

Voici quelques exemples d'expressions bien formées : on suppose que <tt>n</tt> est de type entier, <tt>x</tt> est de type flottant et <tt>s</tt> de type chaîne de caractères.
<source lang="ocaml">
17
</source>

<source lang="ocaml">
n
</source>

<source lang="ocaml">
n+(3*2)
</source>

<source lang="ocaml">
(n+3)*2
</source>

<source lang="ocaml">
n+3*2 (* --> même valeur que n+(3*2) *)
</source>

<source lang="ocaml">
length ("Bonjour") (* --> valeur 7 *)
</source>

<source lang="ocaml">
length "Bonjour" (* --> valeur 7 *)
</source>

<source lang="ocaml">
if (x>0) then n
else (n+1) (* --> suivant la valeur de x, c'est soit la valeur de n, soit la valeur de n+1 *)
</source>

<source lang="ocaml">
(if (x>0) then n
else n) + 1 (* --> (presque) la même chose que n+1 *)
</source>

Voici des exemples de valeurs mal formées :
<source lang="ocaml">
x+1 (* --> x et 1 n'ont pas le meme type *)
</source>

<source lang="ocaml">
x+1.0 (* --> le "+" ne fonctionne que sur des entiers (Pour les flottants, il faut utiliser "+." "*.", ...) *)
</source>

<source lang="ocaml">
length x (* --> length a un argument de type chaine, mais x est de type flottant *)
</source>

<source lang="ocaml">
if (x=0) then x
else n (* --> le type d'une valeur doit etre connu, mais x et n n'ont pas le meme type *)
</source>

<source lang="ocaml">
if (true) then x
else n (* --> idem (meme si dans ce cas, on peut ignorer le "else") ()
</source>

Caml donne des messages d'erreur explicites dans ces cas là. Par exemple, si on rentre l'expression
<source lang="ocaml">
let x = 1.5 in x+1
</source>
Caml répond :
# let x = 1.5 in x+1 ;;
This expression has type float but is here used with type int
(Remarquez le <tt>x</tt> souligné pour nous dire d'où vient l'erreur...)

::'''Remarque :''' en Caml, on peut déclarer une variable locale à une expression avec la syntaxe "<tt>let x= expr in expr</tt>".

====Les valeurs fonctionnelles====

Les exemples du paragraphe précédent ne devraient pas trop vous surprendre. La vraie nouveauté est que même les fonctions sont des valeurs.
<source lang="ocaml">
length (* valeur de type "fonction des chaînes vers les entiers" *)
</source>

Une valeur de type fonctionnel peut être définie de la manière suivante :
<source lang="ocaml">
fun x y -> 2*(x+y)
</source>
Ceci ressemble à une définition mathématique usuelle :
<center> La fonction qui à <math>x</math> et <math>y</math> associe <math>2\times(x+y)</math>, que l'on note habituellement <math>x,y\mapsto 2\times(x+y)</math></center>

Remarquez que cette fonction n'a pas de nom. Les langages impératifs tels que C, ou Pascal ne permettent pas de définir une fonction sans lui donner de nom.

Une telle fonction avec 2 arguments pourra être appliquée pour obtenir une nouvelle valeur. Dans l'exemple précédent, la fonction avaient deux arguments entiers et donnait un résultat de type entier. Si on donne le nom <tt>f</tt> à cette fonction :
<source lang="ocaml">
let f = fun x y -> 2*(x+y)
</source>
on pourra obtenir de nouvelles valeurs telles que :
<source lang="ocaml">
f 1 2
</source>

::'''Notez bien''' que pour appliquer une fonction à ses arguments, les parenthèses ne sont en général pas nécessaires, et qu'on n'utilise pas de "<tt>,</tt>" pour séparer les arguments.

====Notion d'environnement====

Comme tous les langages de programmation, Caml garde en mémoire une liste de définitions. Chacune de ces définitions met en relation un nom ("<tt>x</tt>", "<tt>n</tt>", "<tt>length</tt>", ...) et une valeur ("<tt>3.7</tt>", "<tt>42</tt>", "<tt>fun s -> ...</tt>").

Lorsque l'on lance Caml, l'environnement contient déjà de nombreuse fonctions prédéfinies : <tt>max</tt>, <tt>min</tt>, <tt>mod</tt>, <tt>+</tt>, <tt>float_of_int</tt>, ... Une occurrence d'un nom de variable de l'environnement qui est en position de ''variable libre'' sera remplacé par la valeur correspondante.

=====Définitions=====

L'utilisateur peut rajouter des définitions dans l'environnement grâce au mot clé <tt>let</tt>
* <tt>let ''nom'' = ''expr''</tt> permet de rajouter une définition simple dans l'environnement. Exemple : <tt>let n = 42</tt>
* <tt>let ''nom1'' = ''expr1'' and ''nom2'' = ''expr2''</tt> permet de rajouter plusieurs définitions simultanément. Exemple : <tt>let a=1 and b=2</tt>
* <tt>let rec ''nom'' = ''expr''</tt> permet de rajouter une définition récursive dans l'environnement. Exemple : <tt>let rec f n = if (n<1) then 0 else n+ f (n-1)</tt>
* <tt>let rec ''nom1'' = ''expr1'' and ''nom2'' = ''expr2''</tt> permet de rajouter des définitions mutuellement récursives.

Dans chacun des cas précédents, on peut annoter la définition de types de données. Ceci évite à Caml d'avoir à deviner le type que l'on souhaite et permet de préciser la fonction :
<source lang="ocaml">
let n:int = 42
let rec f (n:int) : string = if (n<1) then "" else "*" ^ (f (n-1))
</source>

Si une définition utilise le même nom qu'une définition précédente, la nouvelle définition écrase l'ancienne. Par exemple :
<source lang="ocaml">
# let n=42 ;;
val n : int = 42
# let n=3.1415 ;;
val n : float = 3.1415
# n ;;
- : float = 3.1415
</source>

=====Définitions locales=====

Il est possible de modifier l'environnement de manière temporaire (''locale''). On utilise alors <tt>let ''nom'' = ''expr1'' in ''expr2''</tt>. Ceci ajoute la définition <tt>''nom'' = ''expr1''</tt> dans l'environnement, mais seulement pour l'évaluation de l'expression <tt>''expr2''</tt>.
<source lang="ocaml">
# let x =
let y = 42 in
y/2 ;;
val x : int = 21
# x ;;
- : int = 21
# y ;;
Unbound value y
</source>

Les définitions locales peuvent elles aussi être multiples (<tt>let ... and ... in</tt>), récursives (<tt>let rec ... in</tt>), mutuellement récursives (<tt>let rec ... and ... in</tt>). Elles acceptent également les annotations de type...

====Transparence référentielle====

Une des idées importantes en programmation fonctionnelle est la notion de « transparence référentielle » : grosso-modo, cela veut dire que l'on a toujours le droit de remplacer une expression par sa valeur sans changer le sens du programme. Bien que ceci semble évident, ce n'est pas vrai dans un langage tels que le langage C...

Pour comprendre pourquoi ceci n'est pas vrai dans un programme Pascal, considérez la fonction suivante
<source lang="pascal">
function f (x:integer) : integer ;
begin
writeln('Salut...');
y:=0; { y est une variable globale }
f:=x+1;
end;
</source>
La valeur de <tt>f(3)</tt> est <tt>4</tt>, mais on ne peut pas remplacer <tt>f(3)</tt> par <tt>4</tt> sans changer le comportement du programme...

C'est cette propriété qui facilite grandement la formalisation des langages fonctionnels, car on peut appliquer le principe mathématique
<center> si <math>x=y</math> alors <math>f(x)=f(y)</math>.</center>

===Les types===

====Les types atomiques====

Caml (et les autres langages fonctionnels typés) possèdent plusieurs types de base tels que :
* les booléens : type <tt>bool</tt> (valeur <tt>true</tt> et <tt>false</tt>),
* les entiers : type <tt>int</tt> pour les entiers signés compris entre <math>-2^{30}</math> et <math>2^{30}-1</math>. (Les entiers Caml sont stockés sur 31 bits...)
* les flottants : type <tt>float</tt> pour les réels en virgule flottante,
* les caractères : type <tt>char</tt> (notés entre guillemets simples)
* le type unité : type <tt>unit</tt>, dont l'unique valeur est <tt>()</tt>. (Nous verrons que ce type a une utilité...)

Même s'il ne s'agit pas vraiment d'un type atomique, nous pouvons également ajouter le type des chaînes de caractères : type <tt>string</tt> (notées entre guillemets doubles).

Caml définit de nombreuse fonctions sur ces types de données :
* opérations arithmétiques
* fonctions mathématiques usuelles (logarithme, sinus, ...)
* ...

::'''Remarques :''' les opérations booléennes ("<tt>&&</tt>" pour le « et » et "<tt>||</tt>" pour le « ou ») fonctionnent de à gauche à droite, et l'argument de droite n'est évalué que si c'est nécessaires. Par exemple <tt>true || (0 = 1/0)</tt> donne la valeur <tt>true</tt>, alors que que <tt>false || (0=1/0)</tt> lève l'exception <tt>Division_by_zero</tt>.

====Les fonctions====

Caml utilise la notation mathématique pour écrire les types des fonctions. Si <tt>f</tt> est une fonction avec un seul argument de type <tt>string</tt> et d
ont la valeur de retour est de type <tt>int</tt> (la fonction <tt>length</tt> par exemple), le type de <tt>f</tt> est noté <tt>string -> int</tt>. Dans l'in
terprète Caml :
<source lang="ocaml">
# length ;;
- : string -> int = <fun>
</source>
Nous indique que la fonction <tt>length</tt> est bien de type <tt>string->int</tt>.

Une nouveauté des langages fonctionnels par rapports à Pascal est que <tt>string->int</tt> est un type comme les autre, et on peut donc créer une fonction d
e type <tt>string -> (string -> int)</tt>. Prenons par exemple la fonction suivante :
<source lang="ocaml">
let f:string->int = fun s ->
let t = "prefix-" in
length (t ^ s) (* "^" est l'opérateur de concaténation des chaînes. *)
</source>
Cette fonction va calculer la longueur de son argument, auquel on a rajouter le préfixe <tt>"prefix-"</tt>.

Si on veut pouvoir changer le préfixe que l'on rajoute devant <tt>s</tt>, on peut faire la fonction suivante :
<source lang="ocaml">
let g:string -> ( string -> int) =
fun prefix ->
fun s -> length (t^s)
</source>
La fonction <tt>f</tt> précédente aurait pu être obtenue grâce à "<tt>g "prefix-"</tt>".

::'''Remarque :''' Caml n'utilise pas les parenthèses dans ce cas là : il notera "<tt>string -> string -> int</tt>".

Nous verrons un peu plus tard que les fonctions peuvent avoir des arguments qui sont eux mêmes des fonctions.

::Exercice : essayez de trouver une fonction de type <tt>(int->int) -> int</tt>.

====Les paires====

Un autre type intéressant est celui des paires de valeur. Par exemple, le type "<tt>int * string</tt>" est compose de valeur "<tt>(3,"toto")</tt>". On peut accéder au premier élément d'une paire avec la fonction "<tt>fst</tt>" et au second élément avec la fonction "<tt>snd</tt>".
<source lang="ocaml">
let paire = ("Bonjour !" , 42*42) in (snd paire)
</source>
donnera la valeur 1764.

Ce type correspond exactement à la notion de ''produit cartésien'' utilisée en mathématiques :
<center><math> A \times B \quad=\quad \{ (a,b) \ |\ a\in A \,,\,b\in B\} </math></center>

Les fonctions <tt>fst</tt> et <tt>snd</tt> sont généralement appelées ''projections'' :
<center><math> \pi_1 : A\times B \to A \qquad (a,b) \mapsto a</math></center>
(et pareillement pour la projection sur l'élément de droite...)

Ce type de données particulièrement utile lorsque l'on veut écrire une fonction qui renvoie 2 ou 3 valeurs. On verra par la suite qu'il existe d'autre types plus appropriés si l'on veut avoir de nombreux champs, et s'il l'on veut leur donner un nom. (Dans une paire, la première composante et la seconde composante n'ont pas de nom propre...)

Notez également que les fonctions a plusieurs arguments n'utilisent en général pas de produit cartésien. Pour Caml :
* une fonction de type <tt>(A*B) -> C</tt> est une fonction à un seul argument, mais son argument est une paire,
* une fonction de type <tt>A -> B -> C</tt> est une fonction à deux arguments séparés. (Plus précisément, c'est une fonction à un argument qui renvoie une fonction à un argument.)

:Exercice : cherchez une manière de passer d'une fonction de type <tt>A*B -> C</tt> à une fonction de type <tt>A -> B -> C</tt>, et vice-versa. Ces transformations s'appellent la ''curryfication'' et la ''decurryfication''.

:Écrivez les fonctions <tt>curry :: ('a*'b -> 'c) -> ('a -> 'b -> 'c)</tt> et <tt>un curry : ('a -> 'b -> 'c) -> ('a*'b -> 'c)</tt> en Caml.

:'''Remarque :''' dans de nombreux cas, les parenthèses autour d'un tuple ne sont pas nécessaires :
<source lang="ocaml">
# let x = 42 , "Toto" and y = (42 , "Toto") in
x=y ;;
- : bool = true
</source>
:Dans le doute, mettez des parenthèses pour éviter des bugs.

====Les listes====

Le type des listes est fondamental en programmation fonctionnelle. D'une certaine manière, on peut dire qu'ils remplacent les tableaux que l'on utilise constamment en programmation impérative.

:Exercice : quels sont les différences importantes (utilisation, complexité, mémoire, ...) entre les tableaux et les listes ?

En Caml, une liste est représentée entre crochets, et les éléments sont séparés par des points-virgules :
<source lang="ocaml">
# let une_liste = [ 1 ; 2 ; 2 ; -1 ; 0 ] ;;
val une_liste : int list = [1; 2; 2; -1; 0]
# let une_autre_liste = [ "coucou" ; "je m'appelle" ; "Bob" ] ;;
val une_autre_liste : string list = ["coucou"; "je m'appelle"; "Bob"]
</source>

Comme vous pouvez le voir dans l'exemple au dessus, le type des listes d'entiers s'appelle "<tt>int list</tt>", le type des listes de flottants s'appelle "<tt>float list</tt>" et le type des listes de listes d'entiers s'appelle ... "<tt>int list list</tt>".

Contrairement au cas du produit cartésien de types, les éléments d'une liste doivent tous avoir le même type :
<source lang="ocaml">
# let une_non_liste = [ 1 ; "Toto" ; 1.3 ] ;;
This expression has type string but is here used with type int
</source>

:'''Attention : ''' quel est le type de la liste suivante ?
<source lang="ocaml">
# let une_liste_bizarre = [ 1 , 2 , 3 ] ;;
</source>

La concaténation des listes s'obtient avec l'opérateur "<tt>@</tt>" et pour rajouter un element devant une liste existante on utilise "<tt>::</tt>".
<source lang="ocaml">
# 0::[1;2;3;4] ;;
- : int list = [0; 1; 2; 3; 4]
# [-1;-2;-3;-4] @ [1;2;3;4] ;;
- : int list = [-1; -2; -3; -4; 1; 2; 3; 4]
</source>
Il existe en plus (dans la bibliothèque "<tt>List</tt>" les fonctions suivantes
* <tt>length</tt>,
* <tt>hd</tt> pour récupérer le premier élément d'une liste,
* <tt>tl</tt> pour récupérer la ''queue'' d'une liste (toute la liste, sans son premier élément).

:'''Remarque :''' Caml possède plusieurs fonctions <tt>length</tt> : notamment une pour les listes et une pour les chaînes de caractères. Pour accéder à ces fonctions (qui ne sont pas dans la bibliothèque standard), il faut utiliser :
:* <tt>List.length</tt> pour la longueur des listes,
:* <tt>String.length</tt> pour la longueur des chaînes.
:Vous pouvez aussi ''ouvrir'' toute la bibliothèque correspondante en utilisant la ligne "<tt>open List</tt>" au début de votre programme pour avoir accès à toutes les fonctions de la bibliothèque sur les listes...

La manière usuelle de définir des fonctions récursives sur les listes d'utilisez plutôt le ''filtrage'' (''"pattern matching"'') décrit plus loin, ou les fonctions prédéfinies comme <tt>List.fold_left</tt> ou <tt>List.fold_right</tt> (qui seront vues en TD et TP).

--- examples et explication de fold ?

====Filtrage, première partie====

La notion de ''filtrage'', aussi appelé ''"pattern-matching"'' est un outils clé pour la programmation en Caml. L'idée est d'essayer de faire correspondre une valeur avec un certain nombre de ''motifs''. Le "<tt>case .. of</tt>" de Pascal en est une version ultra pauvre et simplifiée.

En Caml, la syntaxe du pattern matching est la suivante :
match ''expr'' with
''pattern1'' -> ''expr1''
| ''pattern2'' -> ''expr2''
| ''pattern3'' -> ''expr3''
| ''pattern4'' -> ''expr4''
L'évaluation d'une telle expression se fait de la manière suivante : Caml évalue l'expression "''<tt>expr</tt>''", et essaie de la faire coïncider au motif "<tt>pattern1</tt>" (on dit que Caml essaie d'unifier l'expression "''<tt>expr</tt>''" avec le motif "''<tt>pattern1</tt>''"). Si il y parvient, il évalue l'expression "''<tt>expr1</tt>''" et renvoie la valeur correspondante. Caml regarde tous les motif dans l'ordre.

Par exemple,
<source lang="ocaml">
match (2+2) with
1 -> "Problème."
| 3 -> "Problème."
| 4 -> "Ouf"
| _ -> "problème."
</source>
s'évaluera en la valeur <tt>"Ouf"</tt>.

Le motif "<tt>_</tt>" est un motif ''universel'', et permet de faire ce que l'on ferait avec un "<tt>else</tt>" en Pascal. Le véritable avantage de filtrage de Caml se voit dans le filtrage sur les types ''"composés"'' comme les tuples, les listes ou les types sommes. Le filtrage permet de "déconstruire" une valeur en ces différents constituants. Par exemple, voici comment on pourrait programmer la fonction "<tt>fst</tt>"
<source lang="ocaml">
let premier p = match p with
(x,y) -> x
</source>
Pour évaluer "<tt>premier e</tt>", Caml essaie de faire coïncider la valeur de "<tt>e</tt>" avec un truc de la forme "<tt>(x,y)</tt>". S'il y arrive, alors il renvoie la valeur "<tt>x</tt>". Le typage de Caml inférera automatique que "<tt>p</tt>" doit être une paire, et il n'y a donc pas besoin de prévoir un cas par defaut.

On peut écrire des motifs plus intéressants comme
<source lang="ocaml">
let imaginaire_pur x = match x with
(0,_) -> true
| _ -> false
</source>
qui permettra de tester si la première coordonnée (partie réelle d'une nombre complexe) est nulle ou pas. On aura pu écrire de manière équivalente :
<source lang="ocaml">
let imaginaire_pur x = if (fst x = 0) then true else false
</source>

:: Question : à votre avis, que fait la fonction suivante :
<source lang="ocaml">
let une_fonction x = match x with
(1,(y,z)) -> y-z
| (0,(y,z) -> y+z
| (-1,(y,z) -> z-y
| (_,(y,_) -> y
</source>

:'''Attention :''' les variables qui apparaissent dans les motifs « écrasent » les variables de même nom qui peuvent apparaître avant dans l'expression :
<source lang="ocaml">
let f x = match x with
(x,_) -> x
</source>
:calcule la fonction "<tt>fst</tt>". De plus, les motifs ne sont pas évalués : dans
<source lang="ocaml">
let un = 1
let g x = match x with
un -> 1
| 2 -> 2
| _ -> 3
</source>
:la fonction "<tt>g</tt>" prendra toujours la valeur <tt>1</tt> car le "<tt>un</tt>" est considéré comme un nom de variable...

Pour filtrer sur une liste, on utilise "<tt>[]</tt>" et "<tt>::</tt>". Par exemple, voici une manière de tester si une liste est vide :
<source lang="ocaml">
let vide l = match l with
[] -> true
| x::xs -> false
</source>
On peut écrire des fonctions comme
<source lang="ocaml">
let un_element l = match l with
[x] -> true
| _ -> false
let deux_elements l = match l with
x::y::[] -> true
| _ -> false
let trois_element_ou_plus l = match l with
_::_::_::_ -> true
| _ -> false
</source>

--- complément sur l'unification, un peu plus de détails ?
--- un motif qui contient juste une variable est universel

:'''Compléments syntaxiques :''' Caml définit les sucres syntaxiques suivants
:* "or pattern" : on peut grouper plusieurs motifs qui définissent les mêmes variables et donnent la même expression
<source lang="ocaml">
let f x = match x with
0::l | 1::l | 1::l -> l (* on groupe 3 motifs en une seule ligne *)
| [] -> []
| x::_ -> [x]
</source>
:* "garde pour les motifs" : on peut « garder » les motifs par une condition avec le mot clé "<tt>when</tt>"
<source lang="ocaml">
let g x = match x with
x::xs when (List.lenght (f xs) = 1) -> true
| _ -> false
</source>
:* fonction par filtrage : comme on définit souvent des fonctions par filtrage, Caml autorise la syntaxe
<source lang="ocaml">
function
pattern1 -> expr1
| pattern2 -> expr2
| ...
</source>
:plutôt que
<source lang="ocaml">
fun x -> match x with
pattern1 -> expr1
| pattern2 -> expr2
| ...
</source>
:Remarquez que l'on ne peut faire ça que pour une fonction à une seule variable...
:* fonction par filtrage : s'il n'y a qu'un seul motif, on peut alors utiliser le mot clé "<tt>fun</tt>" habituel, ce qui permet la définition d'une fonction à plusieurs arguments. (Mais dans ce cas, les parenthèses autour des tuples sont obligatoires.)
<source lang="ocaml">
# let h = fun (x,y) z (u,v,w) -> x+y+z+v ;;
val h : int * int -> int -> 'a * int * 'b -> int = <fun>
</source>

====Le polymorphisme====

Nous avons vu que Caml était un langage fortement typé : toutes les expressions ont un type, et on ne peut appliquer des fonctions que lorsqu'elles ont ses arguments ont le bon type.

Quel est le type de la fonction "<tt>fst</tt>" ?
<source lang="ocaml">
let fst = function (x,_) -> x
</source>
Cette fonction est à la fois de type "<tt>int * int -> int</tt>", "<tt>int * float -> int</tt>", ... Pour Caml, cette fonction est de type "<tt>t1 * t2 -> t1</tt>" pour n'importe quels types "<tt>t1</tt>" et "<tt>t2</tt>". Caml dénote un tel type avec de guillemets simples de la manière suivante :
<source lang="ocaml">
# let fst = function (x,_) -> x ;;
val fst : 'a * 'b -> 'a = <fun>
</source>

:''Complément : '' même si cela ne vous arrivera probablement pas dans un premier temps, sachez que seuls les valeurs ''évaluées'' peuvent être polymorphes. Par exemple, dans
<source lang="ocaml">
# let i x = x
let j = i i ;;
val i : 'a -> 'a = <fun>
val j : '_a -> '_a = <fun>
</source>
:l'expression "<tt>j</tt>" n'est pas vraiment polymorphe. (C'est le sens du "<tt>_</tt>" devant le "<tt>a</tt>".) Le "<tt>'_a</tt>" veut dire : « ''la fonction "<tt>j</tt>" a pour type "<tt>t -> t</tt>", mais je ne connais pas encore ce type "<tt>t</tt>".)'' »
:Dés que l'on applique "<tt>j</tt>" à quelque chose, Caml pourra savoir quel est le type de "<tt>j</tt>" :
<source lang="ocaml">
# j 42 ;;
- : int = 42
# j ;;
- : int -> int = <fun>
</source>

:'''Remarque :''' polymorphisme « ad-hoc »...
--- à faire

==Les types avec constructeurs (types ''sommes'')==

Nous avons vu en TP qu'il était possible de définir un ''synonyme de type'' avec le mot clé <tt>type</tt> : par exemple
<code lang="ocaml">
type point = float * float
</code>
permet de définir un nouveau type appelé "<tt>point</tt>". Les valeurs de ce type sont exactement les même que celle de type "<tt>float*float</tt>". C'est bien, mais ça ne permet de définir de ''nouveaux'' types.

===Déclaration des types sommes===

La notion de ''type avec constructeur'' est centrale dans les langage fonctionnelle de la famille ML ou Miranda. Ces types vont pouvoir par exemple servir à définir des types finis :
<source lang="ocaml">
type jours = Lundi | Mardi | Mercredi | Jeudi | Vendredi | Samedi | Dimanche
</source>

Pour déclarer un type avec constructeur, on utilise "<tt>type ''nom_type'' = ''Constr_1'' | ... | ''Constr_n''</tt>" où :
* <tt>''nom_type''</tt> est le nom du type que l'on définit. Ce nom doit forcement commencer par une minuscule. (Comme les types prédéfinis : <tt>int</tt>, <tt>float</tt>, ...)
* <tt>''Constr_1''</tt> et suivants sont les ''constructeurs'' du type. Même si ce n'est pas obligatoire, les constructeurs commencent souvent par une majuscule.

Les types avec constructeurs deviennent plus intéressant lorsque l'on rajoute des ''arguments'' à certains constructeurs. Par exemple, supposons que l'on écrive un programme qui manipule des opérations géométriques dans le plan. On pourra définir le type suivant :
<source lang="ocaml">
type op = Symetrie_centrale | Rotation of float | ...
</source>
Un élément de ce type est soit :
* une symétrie centrale (pas besoin d'argument),
* une rotation autour de l'origine, avec un argument de type <tt>float</tt> : l'angle de la rotation. Voici quelques exemples de valeurs de type "<tt>op</tt>": "<tt>Symetrie_centrale</tt>", "<tt>Rotation (45.0)</tt>", "<tt>Rotation (0.0)</tt>" ou "<tt>Rotation (-360.0)</tt>".

:'''Attention :''' on pourrait penser que "<tt>Rotation</tt>" est une fonction qui prend un argument. Ça n'est pas le cas. "<tt>Rotation</tt>" est un ''constructeur'' qui doit nécessairement s'utiliser avec exactement un argument. (Les parenthèses sont facultatives, mais conseillées.

Comme on a le droit d'utiliser n'importe quel type comme argument d'un constructeur, voici ce qu'on pourrait mettre dans le type "<tt>op</tt>":
<source lang="ocaml">
type op = Symetrie_centrale | Rotation of float | Translation of float*float | Homothetie of float
</source>
De cette manière, on a également les translation selon un vecteur (donné par deux coordonnées flottantes) ou une homothétie de facteur flottant. Voici des nouvelles valeurs dans le type "<tt>op</tt>" : "<tt>Translation (0.0 , 1.0)</tt>", "<tt>Translation (1.3 , 3.5)</tt>" ou "<tt>Homothetie (2.0)</tt>".

:'''Remarque :''' les types avec constructeurs sont aussi appelés ''types sommes''. La raison est que le type des paires (<tt>''type_1'' * ''type_2''</tt>) est appelé ''type produit'' pour une raison évidente : il correspond au produit cartésien. De manière un peu similaire, les type avec constructeurs permettent de faire l'opération ''d'union disjointe'' sur les types. Par exemple, le type "<tt>C1 of ''type_1'' | C2 of ''type_2''</tt>" représente exactement la réunion disjointe des types <tt>''type_1''</tt> et <tt>''type_2''</tt>.

Bien entendu, un constructeur de type somme peut avoir des arguments dont le type est lui même un type somme...

Voici deux examples de types sommes definis par Caml : le premier est simplement le type <tt>bool</tt> :
<source lang="ocaml">
type bool = true | false
</source>
Ce type, comme le type des listes est en fait défini à un niveau plus bas.

Le second type interessant est le type <tt>'a option</tt> :
<source lang="ocaml">
type 'a option = None | Some of 'a
</source>
Par exemple, le type <tt>int option</tt> contient tous les entiers (sous la forme <tt>Some ''n''</tt>), mais également une valeur speciale <tt>None</tt>. On s'en sert en particulier pour modeliser les programmes non totaux. (Ceux qui ne donnent pas toujours une valeurs.) La valeur <tt>None</tt> joue un peu le role du pointeur <tt>NULL</tt> ou de l'entier <tt>-1</tt>.

===Filtrage===

On peut examiner une valeur d'un type somme grâce à l'égalité, mais cela ne permet pas d'accéder aux arguments d'un constructeur :
<source lang="ocaml">
let weekend (j:jours) = if (j=Samedi) || (j=Dimanche)
then true
else false
</source>

Par exemple, si on veut tester si une opération géométrique (type <tt>op</tt>) est une rotation, comment faire ?

On utilise le filtrage...

Le filtrage sur un type somme permet de faire comme un <tt>case of</tt> de Pascal, mais permet en plus de récupérer les valeur des arguments des constructeurs dans des variables.
<source lang="ocaml">
let rotation (o:op) =
match o with
Symmetrie_centrale -> false
| Rotation (a) -> true
| Translation (x,y) -> false
| Homothetie (z) -> false
</source>
Dans le filtrage précèdent, les variables <tt>a</tt>, <tt>x</tt>, <tt>y</tt> et <tt>z</tt> servent à récupérer les valeurs des arguments des constructeurs.

Comme lors du filtrage sur les listes ou les tuples, on peut décider d'ignorer certaines valeurs avec des motifs universels. Voila une seconde version de la fonction précédente :
<source lang="ocaml">
let rotation (o:op) =
match o with
Rotation (_) -> true
| _ -> false
</source>

===Types récursifs===

La véritable puissance des types sommes est dans l'utilisation des types sommes récursifs. Nous avons écrit des fonctions récursive, mais il existe également des types récursifs. Par exemple, en Pascal, le type des liste simplement chaînées s'écrit
<source lang="pascal">
type
liste = ^cellule;
cellule = record
valeur: integer ;
suivant: liste;
end;
</source>
C'est un type récursif : une liste, c'est un pointeur vers une cellule, càd vers un entier et une liste.

En Caml, le type des listes simplement chaînées s'obtient plus simplement avec :
<source lang="ocaml">
type liste = Cons int*liste
</source>
Autrement dit, une liste est donnée par un entier et une liste.

Comme le pointeur vide n'existe pas en Caml, et que de toute façon, une liste n'est pas vraiment un pointeur, il faut en fait rajouter la possibilité d'avoir la liste vide :
<source lang="ocaml">
type liste = Vide | Cons int*liste
</source>

:'''Remarque :''' alors que pour définir une fonction récursive, en doit utiliser le mot clé "<tt>rec</tt>", pour définir un type, il n'y a pas de mot clé spécial.

Finalement, comme les type ont le droit d'avoir des paramètres, on peut donner le type des listes contenant un type arbitraire avec :
<source lang="ocaml">
type 'a liste = Vide | Cons of 'a*'a liste
</source>
'''Attention :'''
# les paramètres d'un types sont précédés d'un guillemet simple,
# on doit mettre les paramètres avant le nom du type,
# il ne faut pas oublier de remettre les paramètres lors des appels récursifs au type.

La définition du type <tt>liste</tt> est équivalente à la définition du type <tt>list</tt> de Caml. Une des différences est que Caml utilise "<tt>[]</tt>" comme constructeur de liste vide, et "<tt>::</tt>" plutôt que "<tt>Cons</tt>". (Ce ne sont pas des constructeurs valides pour les types définis par l'utilisateur.)

On peut utiliser le filtrage comme pour un type somme non récursif. Voici par exemple la fonction qui convertit une liste à nous en une liste de Caml :
<source lang="ocaml">
let rec liste2list : 'a liste -> 'a list = function
Vide -> []
| Cons (a,l) -> a::(liste2list l)
</source>
(Remarquez l'utilisation du mot clé "<tt>function</tt>" à la place de "<tt>fun l -> match l with</tt>".)

De nombreux types de données sont facilement définissables par un type inductif correspondant. Les seuls types qui posent problème sont les types impératifs (tableaux par exemple) ou les types cycliques (listes doublements chaînées).

Nous verrons plus tard par quoi remplacer ces types, ou comment les utiliser...

==Les structures==

==Les exceptions==

==Les librairies==

==Les modules==

Discussion:INFO421 : Programmation fonctionnelle

2009-01-21T12:42:25Z

Caroline :

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

:: Travail terminé! --[[Utilisateur:Caroline|Caroline]] 21 janvier 2009 à 13:42 (CET)

Discussion:INFO421 : Programmation fonctionnelle

2009-01-21T12:41:28Z

Caroline :