Exercices de révision

Exercice 0 : Récursion, listes

Pour les exercices suivants, essayez de proposer au moins deux variantes de votre réponse en utilisant : récursion naïve, récursion terminale, plis (left/right), map.

Problème 0 : Écrivez une fonction sum n qui calcule la somme de tous les entiers de 0 à n.
Problème 1 : Écrivez une fonction sum l qui calcule la somme des éléments d'une liste (supposés être des entiers).
Problème 2 : Écrivez une fonction climb n qui compte le nombre de façons de monter un escalier de n marches, où les déplacements permis sont : monter d'une marche ou monter de deux marches à la fois.
Problème 3 : Écrivez une fonction paths n qui compte le nombre de chemins allant de l'origine (0,0) au coin supérieur droit (n,n) du quadrant positif de la grille carrée (i.e. formée de points à coordonnées entières). Les pas autorisés sont soit vers la droite, soit vers le haut.
Problème 4 : Écrivez une fonction chaines n qui renvoie la liste de toutes les chaînes binaires de longueur n.
Problème 5 : Écrivez une fonction sort l qui trie une liste d'entiers par ordre croissant. Utilisez l'algorithme de votre choix.
Problème 6 : Écrivez une fonction zip l k qui prend deux listes l et k et renvoie une liste de taille le minimum de length l, length k et dont le i-ème élément est (a,b), un couple formé des i-èmes éléments de l et k respectivement.
Problème 6 : Écrivez une fonction cartesian l k qui prend deux listes et génère la liste de tous les couples (a,b) où a est un élément de l et b est un élément de k.

Exercice 1 : Arbres

Problème 0 : Définissez un type algébrique représentant des arbres binaires, dont les sommets (internes ou feuilles) portent des étiquettes de type 'a.
Problème 1 : Écrivez une fonction average_path_length t qui prend en entrée t et calcule la longueur moyenne d'un chemin allant de la racine de l'arbre à l'une de ses feuilles.
Problème 2 : Un arbre binaire de recherche est un arbre binaire étiqueté par des entiers, tel que tous ses sous-arbres vérifient la propriété suivante : l'étiquette de la racine est supérieure ou égale à toutes celles du sous-arbre gauche et strictement inférieure à toutes celles du sous-arbre droit. Écrivez les fonctions suivantes :
1. search t e : cherche un élément e dans l'arbre t.
2. insert t e : insère un élément e dans l'arbre t, produisant un nouvel arbre binaire de recherche.
3. merge t1 t2 : fusionne deux arbres binaires de recherche pour en produire un nouveau.
4. delete t e : supprime un élément e d'un arbre binaire de recherche t ; l'arbre résultant doit encore être un arbre binaire de recherche.
Problème 3 : Définissez un type algébrique représentant des arbres généraux dont chaque sommet possède un nombre arbitraire d'enfants, avec des étiquettes de type 'a sur toutes les bornes (internes ou feuilles).
Problème 4 : Définissez une fonction max t qui calcule le maximum des étiquettes d'un arbre général t étiqueté par des entiers.
Problème 5 : Définissez une fonction depth t qui calcule la profondeur d'un arbre général t.
Problème 6 : Soit step le type suivant :
```
type step =
  | Left of int 
  | Right of int
  | Stay
```
Définissez une fonction path t p qui prend un chemin p : step list et le suit dans l'arbre, en renvoyant la valeur du sommet sur lequel il aboutit (le cas échéant). Vous devez utiliser un mécanisme adéquat de gestion d'erreurs : lever des exceptions ou utiliser le module Option.