Exercice 1 : Les arbres enracinés
Nous souhaitons travailler avec des arbres d'arités arbitraires, dont les feuilles sont des entiers. Les nœuds internes ne possèdent pas d'information, sinon la liste de leurs fils.
Proposez un type pour encoder les arbres enracinés.
Écrivez une fonction prenant deux arbres enracinés, qui les lie avec une nouvelle racine ayant pour fils ces deux arbres.
Écrivez une fonction prenant une liste d'entiers, et qui construit un arbre enraciné dont les feuilles sont les éléments de la liste. L'arbre ainsi construit doit avoir une hauteur de $1$.
Écrivez une fonction qui calcule la somme des feuilles d'un arbre enraciné.
Écrivez une fonction qui calcule le maximum des valeurs des feuilles d'un arbre enraciné.
Pouvez-vous généraliser les deux fonctions précédentes ?
Écrivez une fonction map, qui applique une fonction passée en argument à chaque feuille, et renvoie l'arbre enraciné de même forme avec les images de la fonction en feuilles.
Écrivez une fonction prenant en argument un entier $n$, et qui calcule un arbre binaire complet de hauteur $n$ dont les feuilles sont les entiers de $1$ à $2^n$.
Regroupez le type des arbres enracinés et ses fonctions dans un module.
Exercice 2 : Chaînes de caractères concaténables.
La concaténation de chaînes de caractères est une opération coûteuse, puisqu'il faut réserver de l'espace en mémoire (coût en mémoire) et y recopier les deux chaînes concaténées (coût en temps), qui peuvent être arbitrairement longues. Lors de séries de manipulations de chaînes de caractères, il peut être plus efficace d'adopter une représentation permettant la concaténation de chaînes en temps et mémoire constants (au détriment des temps d'autres opérations, comme l'accès à des caractères).
Une technique classique est d'utiliser des arbres, dont chaque nœud représente la concaténation des chaînes représentées par les sous-arbres, et dont les feuilles stockent des chaînes de caractères élémentaires. On utilise alors le type suivant :
type catstring =
| String of string
| Append of catstring * catstring * int
Pour des raisons d'efficacité, il est utile de garder la longueur de la chaîne correspondant à chaque nœud.
Pour l'exercice, vous aurez besoin des fonctions suivantes :
val String.get : string -> int -> char
val String.length : string -> int
val String.sub : string -> int -> int -> string
val String.concat : string list -> string
Écrire une fonction length : catstring -> int.
Proposer une fonction of_string : string -> catstring et une fonction append : catstring -> catstring -> catstring.
Écrire une fonction char_at : int -> catstring -> char option, retournant le caractère d'une position donnée.
Enrichir catstring puis char_at pour pouvoir calculer des préfixes et des suffixes d'une chaîne.
Écrire une fonction de conversion to_string : catstring ->
string. Pour cela, vous aurez besoin d'écrire une fonction plus générale, extrayant la sous-chaîne depuis une position et d'une longueur donnée, et ajoutant les facteurs extraits dans une liste, extract : start:int -> len:int -> catstring -> string list -> string list.
Exercice 3 : Listes non-vides.
Proposez un type pour les listes non-vides : une telle liste devra toujours avoir au moins un élément. Pour le reste elle doit se manipuler de la même façon qu'une liste usuelle.
Donnez des définitions pour les fonctions map, reduce, fold, filter.
