TD/TP Caml n°3 : Listes, types construits et arbres

1. Les listes en Caml - rappels et compléments

Constructions et fonctions de base

Quelques fonctions de manipulation de la bibliothèque List

Exemples de manipulation

2. Exercices sur les listes

Exercice 1

Ecrire une fonction qui renvoie la somme des éléments, supposés entiers, d'une liste.

Exercice 2

Réécrire la fonction map.

Exercice 3

Ecrire une fonction qui renvoie la liste inversée de son argument

Exercice 4

Ecrire une fonction qui fusionne 2 listes triées.

Exercice 5

Ecrire une fonction qui découpe en 2 sous-listes de longueur quasi-égales (à 1 près). Cette fonction renvoie alors le couple formé de ces 2 sous-listes.

Exercice 6

Ecrire une fonction qui trie une liste par un tri fusion (rappel : dans ce tri, on découpe la liste en 2, on trie chaque partie et on les fusionne).

3. Définition de types

Définition de base

Somme de types

Types paramétrés

4. Types récursifs, listes et arbres polymorphes

Exercice 7 : Arbres binaires polymorphes

On définit un arbre binaire polymorphe de la manière suivante :

#type 'a arbre = Vide | Noeud of 'a * ('a arbre)*('a arbre);; #Noeud (1, Noeud(2,Vide,Vide), Vide);;

a) Ecrire une fonction qui calcule le nombre d'éléments non Vide (c'est à dire de type 'a) contenus dans l'arbre. Sur l'exemple précédent, on doit en trouver 2.

b) Ecrire une fonction qui calcule le somme des éléments contenus dans un arbre d'entiers.

c) Ecrire une fonction qui renvoie une liste contenant le parcours infixe d'un arbre donné en argument.

d) Ecrire une fonction d'insertion d'un élément dans un arbre de recherche (cf. la définition d'un arbre de recherche dans le TP Lisp n°4).

e) Ecrire une fonction de création d'un arbre de recherche à partir d'une liste d'éléments.

f) Ecrire une fonction qui indique si un élément fait partie d'un arbre de recherche (en le parcourant efficacement). ... à suivre.