Département d'Informatique
Licence Informatique 2001-2002
Programmation Fonctionnelle
29 octobre



Les types, éléments fondamentaux
de la construction de programmes
 (ou comment définir de nouveaux types à l'aide de constructeurs et
utiliser ces constructeurs comme un procédé de programmation, le filtrage)



I   L'exemple des n-uplets

  1. Le type couple et les fonctions fst (premier) et snd (second) d'accés aux éléments d'un couple sont prédéfinies en CAML. Comment pourrait-on définir ces fonctions si ce n'était pas fait ?
    Quel est leur type ?

  2. Définir les fonctions d'accés aux éléments d'un triplet. Quel est leur type ?

II   Le cas des listes

  1. Le type liste est prédéfini en CAML. Comment définir les fonctions hd (head) et tl (tail) d'accés aux éléments d'une liste ? Donner leur type.

  2. Définir en CAML les quelques fonctions classiques suivantes. Préciser leur type.

    1. Longueur d'une liste (length),
    2. Concaténation de deux listes ((@)),
    3. Inversion d'une liste (rev),
    4. Elément à une position (un entier à partir de 0) donnée (nth), ...

  3. Application d'une fonction à tous les éléments d'une liste.
    Définir les fonctions map et fold_left vérifiant:
    1. map f [a1;a2;...;an] = [f a1;f a2;...;f an]

    2. fold_left f a [b1;b2;...;bn] = f (... (f (f a b1) b2) ...) bn

    Donner le type de ces fonctions.

III   Le cas des arbres binaires

  1. Définir le type arbre binaire avec des valeurs aux feuilles.

  2. Donner un exemple d'un tel arbre binaire. Comment l'écrire en CAML? Quel est son type ?

  3. Ecrire une fonction qui, étant donné un arbre binaire à valeurs entières, retourne la somme des valeurs aux feuilles.

  4. Ecrire une fonction qui retourne la liste des valeurs aux feuilles d'un arbre binaire en respectant l'ordre de parcours de l'arbre en profondeur d'abord.
This document was translated from LATEX by HEVEA.