Programmation Avancée

TP5: promenades

Exercice 1: le problème des reines

Ce problème classique consiste à poser n reines sur un échiquier de taille n de façon à ce qu'aucune reine ne soit menacée par une autre: on doit donc avoir exactement une reine par ligne, une reine par colonne et une reine par diagonale.

Il n'existe essentiellement pas de formule magique pour énumérer ou même compter les solutions, la seule solution est d'énumérer bêtement toutes les combinaisons possibles. Pas trop bêtement quand même: il est hors de question d'énumérer tous les échiquiers à n reines pour enlever ensuite ceux qui sont invalides. Plus généralement, on veut éviter de construire en mémoire la liste de toutes les solutions (partielles), ce qui permet par exemple de gagner du temps si on veut seulement afficher la première solution.

Question 1

Implémenter une solution sous la forme d'une fonction qui prend en argument la taille du problème et une fonction à itérer sur chaque solution trouvée. On évite ainsi de construire la liste de toutes les solutions, tout en restant abstrait par rapport à ce qu'on veut faire avec les solutions.

Utiliser votre algorithme pour afficher la première solution et arrêter le calcul ensuite. Séparemment, l'utiliser pour compter le nombre de solutions.

Question 2

Ajoutez une continuation pour rendre votre code récursif terminal.

Exercice 2: double continuation

A priori, vous avez inventé à la fin de l'exercice précédent ce qu'on appelle les "double-barrelled continuations", ou plus simplement "success/failure continuations".

L'idée générale permet de coder de façon modulaire et efficace des calculs non-déterministes, c'est à dire qu'ils ne renvoient pas une unique valeur mais ont un nombre arbitraire de valeurs de retour possibles. On code ces calculs par des fonctions prenant en argument deux continuations appelées respectivement continuation de succès et d'échec. La continuation de succès va être appelée sur chaque valeur de retour possible. Elle prend elle-même une continuation en argument, qui va permettre de reprendre l'énumération des valeurs de retour. A la fin, la continuation d'échec est appelée pour signifier qu'il n'y a plus (ou pas) de retours possibles. Par exemple, le calcul qui renvoie 1 ou 2 peut être représenté par fun success failure -> success 1 (fun () -> success 2 failure).

Plus formellement, on définit le type 'a t des calculs non déterministes renvoyant des valeurs de type 'a:

type cont = unit -> unit
type 'a success = 'a -> cont -> unit
type failure = cont
type 'a t = 'a success -> failure -> unit

Une fonction non-déterministe qui prend des arguments de type t1 ... tn et qui renvoie des valeurs de type 'a sera encodée par une fonction Caml de type t1 -> ... -> tn -> 'a t.

Dans ce style, on peut implémenter un certain nombre de combinateurs, qui permettent ensuite d'écrire du code comme:

let rec f max target =
  if target = 0 then return [] else
    if max = 1 then fail else
      (* On met [max] dans la liste, ou pas. *)
      orelse
        (andthen
           (* Ajouter [max] à une solution pour [target-max]. *)
           (f (min max (target-max)) (target-max))
           (fun l -> return (max::l)))
        (f (max-1) target)

Question

Votre mission est d'implémenter les combinateurs nécessaires pour faire passer le code précédent. Le combinateur fail : 'a t code le calcul qui ne renvoie aucune valeur, il doit donc seulement appeler la continuation d'échec. Le combinateur return : 'a -> 'a t code le calcul qui renvoie une seule valeur, donnée en argument. Le combinateur orelse : 'a t -> 'a t -> 'a t prend deux calculs et renvoie toutes les valeurs renvoyées par ces calculs, tandis que andthen : 'a t -> ('a -> 'b t) -> 'b t prend deux calculs m et n et renvoie les succès de n x quand x est un succès de m.

Tester:

let print_list l =
  Printf.printf "[%s]\n" (String.concat "," (List.map string_of_int l))

let () =
  let fk () = () in
  let sk l k = print_list l ; k () in
    f 5 5 ~sk ~fk

Exercice 3: en long et en large

Les différentes stratégies de parcours d'arbre peuvent être codées de façon uniforme en utilisant la structure de file de priorité, avec différents ordres. Dans cet exercice on s'intéresse seulement à deux cas particuliers: les parcours en profondeur et en largeur (de gauche à droite dans les deux cas) correspondant aux structures de file et de pile.

On considère la signature suivante:

module type Priority = sig
  type 'a t
  exception Empty
  val singleton : 'a -> 'a t
  val put : 'a * 'a t -> 'a t
  val take : 'a t -> 'a * 'a t
  val put2 : 'a * 'a * 'a t -> 'a t
  val take2 : 'a t -> 'a * 'a * 'a t
end

Le type t représente une collection ordonnée, put est l'ajout et take prend une collection non-vide et renvoie le premier élement et la collection à laquelle cet élément a été enlevé; cette fonction lève l'exception Empty si on lui passe une collection vide.

La fonction put2 (resp. take2) effectue deux put dans un ordre bien choisi, qu'on ajustera dans la suite pour obtenir les parcours voulus.

Question 1

Réaliser deux module de type Priority: Stack qui implémente les piles et Queue qui implémente les files. (Pour les files, on peut éviter un put en temps linéaire, en amortissant.)

Question 2

On considère le type d'arbres suivant:

type 'a t = Leaf of 'a | Node of 'a * 'a t * 'a t

(** 0
  * |\
  * 1 6
  * |\
  * 2 3
  *   |\
  *   4 5  *)
let t =
  Node (0, Node (1, Leaf 2, Node (3, Leaf 4, Leaf 5)), Leaf 6)

Ecrire un foncteur qui prend en argument un module de type Priority, et implémente la fonction to_list qui parcourt un arbre à l'aide de la file de priorité donnée et renvoie la liste des valeurs (de type 'a) rencontrées sur les noeuds et feuilles dans l'ordre du parcours.

On teste, où Depth est l'instance de votre foncteur sur Stack et Breadth son instance sur Queue:

# Depth.to_list t ;;
- : int list = [0; 1; 2; 3; 4; 5; 6]
# Breadth.to_list t ;;
- : int list = [0; 1; 6; 2; 3; 4; 5]

Question 3

Ajouter une fonction relabel à votre foncteur, qui prend un arbre en entrée et calcule en sortie un arbre de même structure mais dont les noeuds et feuilles ont été re-étiquetés selon leur ordre de parcours. (Cela peut aider de commencer par coder la fonction identité qui déconstruit un arbre en le parcourant, puis le reconstruit en remontant la pile des appels récursifs.)

On teste:

# Depth.relabel t ;;
- : int Traversals.t =
Node (0, Node (1, Leaf 2, Node (3, Leaf 4, Leaf 5)), Leaf 6)
# Breadth.relabel t ;;
- : int Traversals.t =
Node (0, Node (1, Leaf 3, Node (4, Leaf 5, Leaf 6)), Leaf 2)