TD 3 : Programmation Fonctionnelle

 Login :  Mot de passe :

  1. Une structures de données persistantes est une structure de donnée qui, lors d’une modification, préserve les versions précedentes. Par exemple, les structures purement fonctionnelles sont immuables: on ne peut les modifier, mais seulement les copier, et sont donc automatiquement persistantes. Les listes ou les arbres tels que vous les avez vus dans les TD précédents sont des exemples de structures purement fonctionelles. On va s'intéresser ici à deux structures de données, les files et les tableaux, pour lesquelles nous allons écrire des versions persistantes.

  2. Déposer le fichier t9.ml :

    Le nom du fichier à déposer
    Il faut se connecter avant de pouvoir déposer

    Le mode T9 (text on 9 keys) était une méthode de saisie pour les téléphone portables à clavier numérique facilitant la saisie des textes. Les touches d'un clavier téléphonique étaient généralement disposées comme sur l'image ci-dessous : à chaque touche correspondait un groupe de plusieurs lettres (3 ou 4). Pour saisir une lettre, il fallait taper plusieurs fois sur une touche pour faire défiler les lettres correspondants à la touche.

    Au lieu de cela, dans le mode T9, une seule frappe par lettre suffit et le téléphone propose de lui-même les mots, à partir d'un dictionnaire, qui correspondent à la séquence de touches qui vient d'être tapée.

    Par exemple, la suite de touches 2, 6, 6, 5, 6, 8 et 7 correspond au mot bonjour. Cependant, il est possible qu'une suite de touches corresponde à plusieurs mots. Ainsi, la suite 8, 3, 6, 3, 7, 3 correspond aux mots tendre et vendre.

    Le but de cette question est de programmer une solution pour la recherche des mots du dictionnaire qui correspondent à une séquence de touches. Pour cela, nous allons représenter le dictionnaire par un arbre de décision où chaque branche est étiquetée par le numéro d'une touche, et chaque noeud par les mots du dictionnaire correspondant à la séquence des touches menant de la racine à ce noeud. Nous donnons ci-dessous l'arbre de décision pour le dictionnaire bon, bonne, bonjour, vendre, tendre:

    On vous demande:

    1. de définir le type t9 pour l'arbre de décision tel que défini ci-dessus.

    2. d'implémenter les fonctionnalités suivantes:

      
      (* Dictionnaire T9 vide *)
      val empty : t9
      
      (* insert w d : ajoute le mot `w` au dictionnaire `d` *)
      val insert : string -> t9 -> t9
      
      (* remove w d : supprime le mot `w` du dictionnaire `d` *)
      val remove : string -> t9 -> t9
      
      (* search t d : retourne la liste de mots, à partir du
       * dictionnaire `d`, correspond à la suite de touches `t` *)
      val search : int list -> t9 -> string list
          

    Pour tester votre implémentation, vous pourrez utiliser les fonctions suivantes:

    
    let iofold (f : string -> 'b -> 'b) (fname : string) (x : 'b) =
      let stream = open_in fname in
    
      try
        let rec aux (x : 'b) =
          try  aux (f (input_line stream) x)
          with End_of_file -> x
        in let x = aux x in close_in stream; x
      with e -> close_in stream; raise e
      

    Nous fournissons également un (petit) dictionnaire pour le français (non accentué).

  3. Déposer le fichier future.ml :

    Le nom du fichier à déposer
    Il faut se connecter avant de pouvoir déposer

    L'évaluation paresseuse ou différée est une stratégie qui retarde l'évaluation d'une expression jusqu'à sa première utilisation. De plus, une fois calculée, le résultat de l'évaluation peut être préservé pour une réutilisation ultérieure. L'évaluation paresseuse peut être utilisée à des fins d'optimisation (une expression non utilisée ne sera pas évaluée et une expression sera évaluée au plus une fois), mais permet aussi de construire des types de données comme des listes infinies, que nous verrons à la question suivante.

    Certains langages, comme Haskell, ont par défaut une stratégie d'évaluation paresseuse. OCaml, lui, a une stratégie d'évaluation stricte. Par exemple, tous les arguments d'une fonction sont évalués avant de procéder à l'appel.

    On se propose dans ce TD d'écrire une implémentation de calculs différés pour OCaml. Concrètement, une évaluation différée sera représentée par une fonction de type unit -> 'a. Par exemple, définissons x comme suit:

    
    let x = fun () -> 3 + 3
        

    Le corps des fonctions n'étant pas évalué tant que tous les arguments non pas été donnés, on obtient que x représente l'évaluation suspendue de l'expression 3 + 3. Il nous suffira d'appliquer x à () pour forcer cette évaluation. Cependant, à chaque fois que nous forcerons l'évaluation de x, le calcul de 3 + 3 sera fait – le résultat de la première évaluation n'est pas mémorisé.

    Pour obtenir ce comportement, on peut se servir des références pour retenir l'évaluation de 3+3. Ainsi, nous pourrions modifier la définition de x comme suit:

    
    let x =
      let r = ref None in
      fun () ->
        match !r with 
        | None ->
            let v = 3 + 3 in r := Some v; v
        | Some v ->
            v
        

    On vous demande de définir un type 'a future, représentant les calculs différés de type 'a, ainsi que les fonctions suivantes:

    
    (* Créer un calcul différé à partir d'une fonction *)
    val offun : (unit -> 'a) -> 'a future
    
    (* Créer un calcul différé à partir d'une valeur *)
    val ofval : 'a -> 'a future
    
    (* Force l'évaluation d'un calcul différé *)
    val force : 'a future -> 'a
    
    (* Retourne si un calcul différé a déjà été évalué *)
    val isval : 'a future -> bool
         
  4. Déposer le fichier wlist.ml :

    Le nom du fichier à déposer
    Il faut se connecter avant de pouvoir déposer

    On se propose maintenant de définir une structure de donnée pour les listes (potentiellement) infinies. On rappelle ci-dessous le type des listes:

    
    type 'a list = [] | (::) of 'a * 'a list
        

    On pourrait imaginer définir la liste de tous les entiers naturels comme suit:

    
    let s = let rec aux x = x :: s (x + 1) in aux 0 ;;
        

    Cependant, OCaml étant un langage d'évaluation stricte, ce dernier essaie de construire intégralement la liste, ce qui ne peut que mal terminer dans un monde fini:

    
    Stack overflow during evaluation (looping recursion?).
        

    Une technique pour coder les listes infinies est d'utiliser l'évaluation retardée afin de suspendre l'évaluation de cette dernière, par exemple en suspendant l'évaluation de la liste à chaque fois que l'on accède/retire sa tête.

    En vous aidant de la définition de la une structure de donnée 'a wlist ci-dessous, vous implémenterez les fonctions suivantes:

    
    (* Type des listes potentiellement infinies (c'est-à-dire aussi
     * bien finies que infinies. *)
    
    type 'a wlist = Nil | Cons of 'a * (unit -> 'a wlist)
    
    (* La liste infinie vide *)
    val nil : 'a wlist
    
    (* cons x s = ajoute l'élément `x` en tête de `s` *)
    val cons : 'a -> (unit -> 'a wlist) -> 'a wlist
    
    (* cons x = la liste infinie constante `[x; x; ...]` *)
    val const : 'a -> 'a wlist
    
    (* iter f x = la liste infinie `[x; f x; f^2 x; ...]` *)
    val iter : ('a -> 'a) -> 'a -> 'a wlist
    
    (* oflist s = la liste infinie à partir de la liste `s` *)
    val oflist : 'a list -> 'a wlist
    
    (* observe s = retourne la tête et la queue de `s`.
     * Retourne `None` si la liste est vide *)
    val observe : 'a wlist -> ('a * 'a wlist) option
    
    (* filter p s = la liste infinie `[x | x \in s & p x]` *)
    val filter : ('a -> bool) -> 'a wlist -> 'a wlist
    
    (* map f s = la liste infinie `[f x | x \in s]` *)
    val map : ('a -> 'b) -> 'a wlist -> 'b wlist
    
    (* combine s1 s2 = la liste infinie `[(x, y) | x \in s1, y \in s2]` *)
    val combine : 'a wlist -> 'b wlist -> ('a * 'b) wlist
    
    (* drop i s = la liste infinie obtenue en enlevant les `i`
     * premiers éléments de `s`. *)
    val drop : int -> 'a wlist -> 'a wlist
    
    (* fold f s i x = comme `List.fold_lefti` mais s'arrête au bout
     * de `i` étapes, c'est-à-dire, si `s` = [s0; s1; ...], alors
     * fold f s i x = f i si (f ... (f 1 s1 (f 0 s0 x)) ...).
     *
     * Si `i` est strictement négatif, épuise toute la liste. *)
    val fold : (int -> 'a -> 'b -> 'b) -> 'a wlist -> int -> 'b -> 'b
        

    Que dire de filter (fun x -> x < 0) (const 0) ? Pourquoi ?

  5. Déposer le fichier ksnapsack.ml :

    Le nom du fichier à déposer
    Il faut se connecter avant de pouvoir déposer

    La programmation dynamique est une méthode algorithmique pour résoudre des problèmes d'optimisation. Elle consiste à résoudre un problème en le décomposant en sous-problèmes, puis à résoudre les sous-problèmes, des plus petits aux plus grands en stockant les résultats intermédiaires. Un cas particulier de programmation dynamique est la mémoïsation ou programmation dynamique descendante où un problème est résolu par une fonction récursive et où les résultats de cette dernière sont conserver d'un appel à l'autre – ceci permetttant d'accumuler les résultats déjà établis pour éviter de les recalculer ultérieurement.

    Nous donnons ci-dessous une implémentation de la fonction de Fibonacci avec la technique de mémoïsation:

    
    let fibonacci n =
      if n < 0 then 0 else
    
      let mem =
        Array.init (n+1) (fun i -> if i < 2 then 1 else -1)
      in
    
      let rec aux n =
        if mem.(n) >= 0 then mem.(n) else
          let v = aux (n-1) + aux (n-2) in
          mem.(n) <- v; v
      in aux n
        

    On vérifiera bien qu'un appel à fibonacci (n+2) ne calculera qu'une fois fibonacci n.

    On s'intéresse ici à résoudre le problème du sac à dos grâce à la technique de mémoïsation. On suppose que l'on possède $n$ objets et on note respectivement $v_i$ et $p_i$, pour $i \in \{ 1 .. n \}$, la valeur et le poids de l'objet $i$. On suppose qu'on possède également un sac à dos de capacité $c$. Le problème est de remplir le sac à dos tel que la somme des valeurs des objets soit maximale, c'est-à-dire de trouver $\{ x_i \in \{ 0, 1 \}\}_{1 \le i \le n}$ tels que $\sum_{i = 1}^{n} x_i p_i \le c$ et $\sum_{i = 1}^{n} x_i v_i$ soit maximal.

    On note $T(i, j)$ la valeur maximale pouvant être atteinte avec les $i$ premiers objets et une capacité $j$. Alors, on a la relation de récurrence suivante:

    $$ \left\{ \begin{aligned} T(0, j) &= 0 \\ T(i+1, j) &= \max \{ T(i, j), T(i, j-p_{i+1}) + v_{i+1}\} & \text{(si $p_{i+1} \le j$)} \\ T(i+1, j) &= T(i, j) & \text{(sinon).} \end{aligned} \right. $$

    On vous demande de:

    1. Déduire de la définition de $T$ une fonction récursive knapsack : (int * int) array -> int -> int telle que knapsack vps c calcule la valeur maximale qui peut être emporté avec un sac à dos de capacité c, où vps est la liste des couples (valeur, poids) des objets à disposition.

    2. De modifier ksnapsack afin qu'une solution pour $T(i, j)$ ne soit calculée qu'une seule fois; ceci en se servant d'une technique similaire à celle utilisée, ci-dessus, pour la fonction de Fibonacci. Vous pourrez, par exemple, utiliser une matrice (tableau de tableaux) de taille $n \times c$ ou une table de hachage.