CSI 3525 - Groupes de discussion #5 et #6

ML

Nous allons utiliser Standard ML (Version 1991). Voila les premieres etapes :
- se connecter a Site0 ou Site1 (de preference dans un environnement Linux ou de type X-Win32).
- ouvrir un terminal X et taper sml.
- pour charger un fichier truc.ml, il faut taper la commande use("truc.ml"); une fois dans Scheme ou bien sml < truc.ml depuis le terminal (auquel cas, vous revenez sur le terminal a la fin de l'execution du programme).
- comme d'habitude, l'ideal est d'ouvrir un editeur de texte, d'enregistrer un fichier avec vos programmes et de le lancer a chaque fois que vous voulez effectuer un test.

I. Listes

1. Somme de tous les elements d'une liste de listes

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 :
fun reduce(f,nil,v0) = v0
| reduce(f,a::x,v0) = f(a,reduce(f,x,v0));

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

2. Print

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...).
Pour indiquer a SML que nous utilisons des entiers, on pourra taper print(a : int); a la premiere occurence de ce type d'instruction.

Solution

II. Arbres ternaires

1. Definitions et fonctions elementaires

Les arbres ternaires sont definis de la meme facon que les arbres binaires vus en cours sauf que chaque noeud contient trois branches (la branche du milieu etant reservee a l'egalite).
datatype ttree =
nul|node of int * ttree *ttree * ttree;

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

2. Print

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 !
On suggere de definir deux autres fonctions : une fonction tab(Sign,N) permettant d'afficher le caractere Sign N fois et une fonction prtt(arbre a imprimer,N) qui affiche l'entier du noeud correspondant et ses fils avec un decalage de N espaces (ceci permet de situer la "feuille" dans l'arbre). Voila un exemple du type de reponse attendue.
- printtree(t2);
----1
--3
----3
------3
------4
6
--6
----7
--8

Solution

3. Problemes

1. Methode de Newton

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:
Guess := 1.0;
repeat
Guess := 0.5 * (Guess + X/Guess);
until abs(X - Guess*Guess) < tolerance;

Apres avoir compris l'algorithme, realiser l'implementation en ML. On prendra tolerance = 0.000001.

Solution

2. Encore plus sur les arbres

On veut realiser trois nouvelles fonctions relatives aux arbres, mais cette fois on considerera seulement les arbres binaires.

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

Solution

rigouste@site.uottawa.ca .