Programmation Avancée

Quelques katas

Exercice

Etant donné un type 'a t représentant une collection ordonnée d'objets de type 'a (par exemple, une liste) on considère un certain nombre d'opérations classiques:

nil est la collection vide;
cons e t renvoie la collection commençant par e et continuant avec t;
iter f t exécute f sur chaque élément de t, dans l'ordre;
rev t renvoie la collection contenant les mêmes éléments que t mais dans l'ordre inverse;
map f t renvoie la collection des f x pour x dans t, dans le même ordre;
fold f s1 t calcule s_n+1 où s_k+1 = f s_k e_k et e_1 ... e_n est la suite ordonnée des éléments de t;
find f t renvoie Some e où e est le premier élément de t tel que f e = true, et None s'il n'y a aucun tel élément.

On spécifie de plus que toutes les opérations se font en temps et en espace linéaires. De plus, on spécifie que find visite dans t au plus un élément satisfaisant f (ce qui permet par exemple que find termine sur une collection infinie contenant un élément satisfaisant f).

Question 1

Ecrire une signature Sfold contenant un type abstrait 'a t équipé des opératiors nil, cons et fold telles que décrites ci-dessus. L'étendre ensuite en S avec toutes les opérations.

Question 2

Implémenter un foncteur Make_from_fold qui prend en entrée un module M de type Sfold et retourne un module de type S with type 'a t = 'a M.t. En d'autres termes, implémenter iter, rev, map et find à partir de fold. Bien sûr on devra respecter les types, mais aussi la spécification des opérations donnée plus haut. En particulier, on fera attention pour find à ne pas continuer de parcourir t une fois qu'on a trouvé un élément satisfaisant.

Tester sur les listes:

module Slistfold = struct
  type 'a t = 'a list
  let fold = List.fold_left
  let cons a b = a::b
  let nil = []
end

module Slist = Make_from_fold(Slistfold)

let () =
  let lists = [ [2;4;8] ; [] ; [4;5;1] ; [1;3;7] ] in
    assert
      (List.for_all
         (fun l -> List.rev l = Slist.rev l)
         lists) ;
    assert
      (List.for_all
         (fun l -> List.map ((+) 1) l = Slist.map ((+) 1) l)
         lists) ;
    assert
      (List.for_all
         (fun l -> List.fold_left max 0 l = Slist.fold max 0 l)
         lists) ;
    let find f l = try Some (List.find f l) with Not_found -> None in
    let even x = x mod 2 = 0 in
    assert
      (List.for_all
         (fun l -> find even l = Slist.find even l)
         lists) ;
    Printf.printf "OK!\n"

Question 3

De même, re-implémenter toutes les opérations à partir de iter, nil et cons uniquement.

Question 4

Au lieu de spécifier fold à partir du contenu d'une collection, on peut définir le contenu à partir du comportement d'une fonction fold: les éléments d'une collection t sont simplement les objets successivement passés en second argument de la fonction f passée à fold f t.

Cette observation permet de construire une notion de collection directement sur le type de fold. En représentant en quelque sorte une collection t par l'application partielle de fold à t. Réaliser cela en complétant la définition suivante:

module Purefold : Sfold = struct
  type 'a t =
    { fold : 'b. ('b -> 'a -> 'b) -> 'b -> 'b }
  let fold f s t = t.fold f s
  let nil = (* ??? *)
  let cons e t = (* ??? *)
end

Outre le gain (subjectif) en lisibilité, l'intérêt du type enregistrement utilisé ici est de pouvoir exprimer qu'un objet de type 'a t (représentant une collection d'élements de type 'a fixé) permet de faire des fold sur n'importe quel type 'b. La notation 'b. ... dénote ce polymorphisme en 'b dans le type du champ fold de l'enregistrement 'a t.

Une fois qu'on a Purefold on peut dériver toutes les autres opérations, et tester sur un aller-retour entre les listes et nos conteneurs:

module Pure = Make_from_fold(Purefold)
let () =
  let t = List.fold_left (fun t e -> Pure.cons e t) Pure.nil [1;2;3] in
  (* Ici t devrait correspondre à la collection 3 2 1. *)
  let l = Pure.fold (fun l e -> e::l) [] t in
    assert (l = [1;2;3])