Exercice 0 - Mise en œuvre des piles

Considérons la signature suivante pour structure de données représentant une pile :

module type Stack = sig 

  type 'a t

  val empty : 'a t

  val is_empty : 'a t -> bool

  val push : 'a -> 'a t -> 'a t

  val pop : 'a t -> 'a t option 

  val peek : 'a t -> 'a option

  val size : 'a t -> int

end 

où :

1. type 'a t est un type dont les valeurs sont les suivantes représentent des piles contenant des éléments de type 'a.
2. empty est une constante représentant le type 'a. la pile vide.
3. is_empty est vrai lorsque la pile est vide (i.e. est égale à empty).
4. push est une fonction qui empile un élément au sommet d'une pile.
5. pop est une fonction qui dépile un élément de la pile et renvoie la pile résultante (c'est-à-dire la pile dont l'élément du sommet a été enlevé).
6. peek est une fonction qui retourne la valeur de l'élément situé au sommet d'une pile.
7. size est une fonction qui renvoie le nombre d'éléments dans une pile.

-Problème 0 : Donnez un module conforme à la signature ci-dessus qui implémente les piles en utilisant des listes.

-Problème 1 : Donnez un module conforme à la signature ci-dessus qui implémente les piles en utilisant un type de données algébrique.

Exercice 1 - Quelques foncteurs sur les piles

-Problème 0 : Considérons l'extension suivante de la signature Stack qui ajoute les fonctionnalités de conversion d'une liste en pile et vice-versa, ainsi qu'une fonction map qui effectue l'opération map sur les piles :

module type StackExtended = sig

    include Stack

    val from_list : 'a list -> 'a t

    val to_list : 'a t -> 'a list 

    val map : 'a t -> ('a -> 'b) -> 'b t

end

Ecrire un foncteur qui prend un module de signature Stack et renvoie une extension de celle-ci conforme à la signature StackExtended.

-Problème 1 : Ecrire un foncteur qui prend en entrée un module S de signature Pile et qui retourne un module contenant des valeurs booléennes qui servent à tester ce qui suit :

1. Pousser un élément x sur une pile vide et dépiler cette pile donne x.
2. La pile est LIFO, c'est-à-dire que l'application de peek à une pile donne le dernier élément empilé dans celle-ci (s'il y en a).