Presentons d'abord la fonction reducteur que nous utiliserons plusieurs fois dans ce GD, qui permet d'appliquer une fonction de deux arguments a une liste, en prenant une constante de depart :
1. Somme de tous les elements d'une liste de listes
Ainsi appliquee a la liste [E1,E2,...,En] et a la constante v0, on obtient
f(En,f(E(n-1),f(...f(E2,f(E1,v0))...))).
Appliquee a + et 0, cette fonction a l'interessante propriete de donner
la somme des elements de la liste.
1. On demande simplement de creer une fonction somme qui etend cette
fonction a des exemples du type [[1,2,3],[4,5],[6,7,8,9]].
On designe la fonction addition : x,y -> x+y par "op +".
2. Meme question mais sans creer de fonction (il s'agit d'utiliser
la fonction map qui possede les memes qualites qu'en Scheme et de l'appliquer
directement a la liste ci-dessus).
On desire utiliser la commande print pour afficher une liste d'entiers. Pour afficher un retour a la ligne, on utilise print("\n"). Pour effectuer une suite quelconques d'instructions A,B,C... (pas forcement print), on utilise (A;B;C...).2. Print
1. Programmer une fonction qui permet d'inserer un element dans un arbre
ternaire.
2. Programmer maintenant les fonctions permettant d'inserer une liste
d'element et d'obtenir la liste ordonnee des elements de l'arbre.
On pourra effectuer des tests sur les elements suivants:
val t1 = node(6,node(1,nul,nul,nul),nul,node(8,nul,nul,nul));
val t2= node(6,node(3,node(1,nul,nul,nul),node(3,nul,node(3,nul,nul,nul),node(4,nul,nul,nul)))
,node(6,nul,nul,nul)
,node(8,node(7,nul,nul,nul),nul,nul));
On reprend le format d'arbre ternaire vu precedemment. Il s'agit maintenant d'imprimer tous les elements. Il faut evidemment que le resultat obtenu a l'ecran ressemble a un arbre !2. Print
On demande de calculer la racine carree d'un nombre positif par la methode de Newton: il s'agit d'une methode d'essais/erreurs. L'algorithme en Pascal est le suivant:1. Methode de Newton
Apres avoir compris l'algorithme, realiser l'implementation en ML. On prendra tolerance = 0.000001.
On veut realiser trois nouvelles fonctions relatives aux arbres, mais cette fois on considerera seulement les arbres binaires.2. Encore plus sur les arbres
datatype tree = nul|
node of int * tree * tree;
val t1 = node(6,node(1,nul,nul),node(8,nul,nul));
val t2= node(6,node(3,node(1,nul,nul),node(4,nul,nul)))
,node(8,node(7,nul,nul),nul));
val t3= node(4,node(0,nul,node(3,node(2,node(1,nul,nul),nul),nul))
,node(10,node(6,nul,nul),node(12,nul,nul)));
1. Realiser la somme de tous les entiers d'un arbre.
2. Calculer la hauteur de l'arbre.
3. Verifier si l'arbre est equilibre ie si a tous les niveaux de recursion
les hauteurs des branches gauche et droite sont egales ou different d'une
unite (attention aux operateurs booleens en ML: and s'ecrit andalso et
or s'ecrit orelse).