TP 05 - Typage et fonctions d’ordre supérieur

Programmation fonctionnelle

Data types

Exercice 1 — Listes d’associations

Dans cet exercice, on utilise le type suivant :

data Dict k v = Dict [(k, v)]
    deriving (Eq, Show)

Une liste d’associations peut contenir plusieurs fois la même clé. Aucun ordre particulier n’est imposé aux clés.

Pour chaque question, définir la fonction demandée avec son type. Vous pouvez écrire toutes ces fonctions en combinant les fonctions existantes, sans récursivité explicite. Les fonctions doivent être polymorphes lorsque cela est possible. On suppose les listes finies.

Les exemples utilisent notamment cette liste de scores obtenus lors de séances d’entraînement :

scores :: (Num a) => Dict String a
scores = Dict
    [ ("Luke",20), ("Leia",10), ("Han",15), ("Luke",25), ("Yoda",30), ("Rey",28), 
      ("Leia",18), ("Chewbacca",22), ("Han",17), ("Obi-Wan",27) ]
  1. Définir une fonction keysWhere qui prend un prédicat sur les valeurs et une liste d’associations, puis renvoie les clés dont la valeur satisfait ce prédicat. Conserver l’ordre et les éventuelles répétitions des clés.
λ> keysWhere (> 20) scores
["Luke","Yoda","Rey","Chewbacca","Obi-Wan"]
λ> keysWhere (>= 20) scores
["Luke","Luke","Yoda","Rey","Chewbacca","Obi-Wan"]
λ> keysWhere (> 100) scores
[]
  1. Définir une fonction transformWhere qui prend un prédicat, une fonction de transformation et une liste d’associations. Elle conserve uniquement les associations dont la valeur satisfait le prédicat, puis transforme les valeurs conservées. Les clés restent identiques et la transformation peut changer le type des valeurs.
λ> transformWhere (> 20) (* 2) scores
Dict [("Luke",50),("Yoda",60),("Rey",56),("Chewbacca",44),("Obi-Wan",54)]
λ> transformWhere (> 20) show scores
Dict [("Luke","25"),("Yoda","30"),("Rey","28"),("Chewbacca","22"),("Obi-Wan","27")]
  1. Définir une fonction partitionByAverage qui prend une liste d’associations dont les valeurs sont de type Double, puis renvoie une paire de listes d’associations. La première contient les associations dont la valeur atteint ou dépasse la moyenne ; la seconde contient les autres. L’ordre doit être conservé dans chaque liste. Si la liste initiale est vide, renvoyer deux listes d’associations vides.
λ> partitionByAverage (Dict [("Han",8),("Luke",12),("Leia",16)])
(Dict [("Luke",12.0),("Leia",16.0)],Dict [("Han",8.0)])
λ> partitionByAverage (Dict [("R2-D2",10),("C-3PO",10)])
(Dict [("R2-D2",10.0),("C-3PO",10.0)],Dict [])
  1. Définir un type énuméré Weapon représentant trois équipements : un sabre laser (LightSaber), un communicateur (Comlink) et un pistolet laser (Blaster). Faire dériver les instances des contraintes nécessaires pour pouvoir tester l’égalité et afficher les valeurs de ce type. Vous pourrez ensuite définir la liste d’associations suivante :
weapons :: Dict String [Weapon]
weapons = Dict
   [ ("Luke",[LightSaber,Comlink]), ("Han",[]), ("Leia",[Blaster]),
     ("Rey",[LightSaber,Blaster]), ("Obi-Wan",[LightSaber,Comlink]),
     ("Luke",[Blaster,Comlink]) ]

Définir ensuite une fonction expandGroups qui transforme une liste associant chaque clé à une liste de valeurs en une liste d’associations individuelles. Une liste de valeurs vide ne produit aucune association. Conserver l’ordre des associations et des valeurs.

λ> expandGroups weapons
Dict [("Luke",LightSaber),("Luke",Comlink),("Leia",Blaster),("Rey",LightSaber),("Rey",Blaster),("Obi-Wan",LightSaber),("Obi-Wan",Comlink),("Luke",Blaster),("Luke",Comlink)]
  1. Définir une fonction groupValues qui rassemble les valeurs associées à une même clé. Chaque clé doit apparaître une seule fois dans le résultat, dans l’ordre de sa première apparition. Les valeurs associées doivent conserver leur ordre d’origine.
λ> groupValues scores
Dict [("Luke",[20,25]),("Leia",[10,18]),("Han",[15,17]),("Yoda",[30]),("Rey",[28]),("Chewbacca",[22]),("Obi-Wan",[27])]
λ> groupValues (Dict [("R2-D2","reparation"),("C-3PO","traduction"),("R2-D2","navigation")])
Dict [("R2-D2",["reparation","navigation"]),("C-3PO",["traduction"])]

Indice : il existe une fonction nub qui retire les doublons d’une liste.

  1. Définir une fonction mergeStocks qui fusionne deux inventaires. Les inventaires associent des données à des quantités de type Int. Additionner toutes les quantités associées à une même donnée, y compris lorsque celle-ci apparaît plusieurs fois dans un même inventaire. Conserver l’ordre de première apparition des données dans la concaténation des deux inventaires.
λ> mergeStocks (Dict [(LightSaber,3),(Blaster,2)]) (Dict [(LightSaber,4),(Comlink,5)])
Dict [(LightSaber,7),(Blaster,2),(Comlink,5)]
λ> mergeStocks (Dict [(Blaster,2),(Blaster,3)]) (Dict [])
Dict [(Blaster,5)]
  1. Définir une fonction innerJoin qui rapproche deux listes d’associations par leurs clés. Pour chaque clé commune, produire une association entre cette clé et une paire contenant une valeur de chaque liste. Lorsqu’une clé apparaît plusieurs fois, produire toutes les combinaisons correspondantes. Parcourir les associations de la première liste dans l’ordre, puis leurs correspondances dans la seconde.
λ> innerJoin (Dict [("Luke",20),("Leia",10)]) (Dict [("Luke","Tatooine"),("Luke","Dagobah"),("Han","Corellia")])
Dict [("Luke",(20,"Tatooine")),("Luke",(20,"Dagobah"))]
λ> innerJoin (Dict [("Luke",20),("Luke",25)]) (Dict [("Luke","Jedi")])
Dict [("Luke",(20,"Jedi")),("Luke",(25,"Jedi"))]
  1. La liste weapons associe chaque personnage à une liste d’équipements. Définir une fonction invertIndex qui transforme cet index en une liste associant chaque équipement aux personnages correspondants. Chaque équipement doit apparaître une seule fois dans le résultat et chaque personnage une seule fois par équipement, même s’il apparaît dans plusieurs associations de départ. Conserver les ordres de première apparition.
λ> invertIndex weapons
Dict [(LightSaber,["Luke","Rey","Obi-Wan"]),(Comlink,["Luke","Obi-Wan"]),(Blaster,["Leia","Rey","Luke"])]
λ> invertIndex (Dict [("Luke",[LightSaber,LightSaber]),("Han",[])])
Dict [(LightSaber,["Luke"])]
  1. Définir une fonction lookupAssoc qui recherche une clé et renvoie la valeur associée à sa première occurrence dans un Just. Si la clé est absente, renvoyer Nothing. Il existe une fonction lookup en Haskell, que vous n’avez pas le droit d’utiliser pour cette question.
λ> lookupAssoc "Luke" scores
Just 20
λ> lookupAssoc "Han" scores
Just 15
λ> lookupAssoc "Vador" scores
Nothing
  1. Définir une fonction lookupMany qui prend une liste de clés et une liste d’associations. Si toutes les clés sont présentes, renvoyer leurs valeurs dans un Just, dans l’ordre des clés demandées. Pour chaque clé, utiliser sa première occurrence. Si au moins une clé est absente, renvoyer Nothing. Une liste de clés vide doit produire Just [].
λ> lookupMany ["Yoda","Luke","Yoda"] scores
Just [30,20,30]
λ> lookupMany ["Leia","Han","Rey"] scores
Just [10,15,28]
λ> lookupMany ["Luke","Vador"] scores
Nothing
λ> lookupMany [] scores
Just []
  1. (optionnel) En Haskell, case permet de faire du pattern matching sur le résultat d’une expression pour choisir quoi renvoyer.

Prenons une fonction findWhere qui cherche le premier élément d’une liste satisfaisant un prédicat. Elle renvoie un résultat de type Maybe a : Nothing si aucun élément ne convient, ou Just x si un élément a été trouvé :

findWhere :: (a -> Bool) -> [a] -> Maybe a
findWhere predicate xs =
  case filter predicate xs of
    []  -> Nothing
    x:_ -> Just x

L’expression examinée par case est ici filter predicate xs, qui conserve les éléments satisfaisant le prédicat. Après of, chaque branche associe un motif à un résultat, avec la syntaxe motif -> résultat :

Par exemple :

λ> findWhere even [3,7,4,8]
Just 4
λ> findWhere (>10) [2,5,8]
Nothing

On pourrait écrire la même fonction avec une fonction auxiliaire :

findWhere :: (a -> Bool) -> [a] -> Maybe a
findWhere predicate xs = firstResult (filter predicate xs)
  where
    firstResult [] = Nothing
    firstResult (x:_) = Just x

case permet donc d’écrire ce pattern matching directement dans une expression, sans définir de fonction auxiliaire.

Réécrire la fonction lookupAssoc en utilisant case.

Exercice 2 — Listes d’associations ordonnées

On réutilise le type Dict k v de l’exercice précédent. Une liste d’associations est considérée comme ordonnée lorsque ses clés sont triées par ordre croissant. Les clés répétées sont autorisées.

À l’exception de sortDict, les fonctions de cet exercice reçoivent des listes d’associations déjà ordonnées. Les fonctions qui renvoient une liste d’associations doivent préserver cette propriété. Le type Dict ne garantit pas lui-même cet ordre.

Pour chaque fonction demandée, donner son type et la définir en combinant les fonctions existantes, sans récursivité explicite. Les fonctions doivent rester polymorphes lorsque cela est possible : elles ne doivent pas être limitées aux vaisseaux spatiaux.

Pour certaines questions, vous pourrez avoir besoin de fonctions qui ne sont pas mentionnées explicitement dans le cours. Pensez à chercher dans la doc (notamment la doc de Prelude et la doc de Data.List) les fonctions qui peuvent vous être utiles.

  1. Définir un type énuméré Starship représentant les vaisseaux suivants de Star Wars : AWing, XWing, YWing, TIEFighter et MillenniumFalcon. Faire dériver les instances des contraintes nécessaires pour pouvoir comparer et afficher ces valeurs. Choisir l’ordre de déclaration des constructeurs pour obtenir l’ordre conventionnel suivant, utilisé dans cet exercice :
AWing < XWing < YWing < TIEFighter < MillenniumFalcon
λ> AWing < XWing
True
λ> MillenniumFalcon <= YWing
False
λ> compare XWing XWing
EQ

On utilise ensuite ce type comme clé dans les listes d’associations suivantes. Chaque association indique un nombre de vaisseaux d’un modèle donné ; un même modèle peut apparaître plusieurs fois.

fleet :: Dict Starship Int
fleet = Dict
   [ (XWing,6), (MillenniumFalcon,1), (AWing,4), (XWing,3), (YWing,2) ]

orderedFleet :: Dict Starship Int
orderedFleet = Dict
   [ (AWing,4), (XWing,6), (XWing,3), (YWing,2), (MillenniumFalcon,1) ]
  1. Définir une fonction sortDict qui prend une liste d’associations de type Dict k v et renvoie une liste d’associations du même type, triée par clé. L’ordre relatif des associations de même clé doit être conservé.
λ> sortDict fleet
Dict [(AWing,4),(XWing,6),(XWing,3),(YWing,2),(MillenniumFalcon,1)]
λ> sortDict scores
Dict [("Chewbacca",22),("Han",15),("Han",17),("Leia",10),("Leia",18),("Luke",20),("Luke",25),("Obi-Wan",27),("Rey",28),("Yoda",30)]
  1. Définir une fonction insertOrdered qui prend une clé, une valeur et une liste d’associations ordonnée, puis insère la nouvelle association à sa place. Si la clé est déjà présente, placer la nouvelle association après toutes celles de même clé. Ne pas trier à nouveau toute la liste.
λ> insertOrdered XWing 5 orderedFleet
Dict [(AWing,4),(XWing,6),(XWing,3),(XWing,5),(YWing,2),(MillenniumFalcon,1)]
λ> insertOrdered TIEFighter 2 orderedFleet
Dict [(AWing,4),(XWing,6),(XWing,3),(YWing,2),(TIEFighter,2),(MillenniumFalcon,1)]
  1. Définir une fonction lookupAllOrdered qui renvoie toutes les valeurs associées à une clé dans une liste ordonnée. Exploiter l’ordre pour arrêter la recherche dès que les clés dépassent la clé recherchée.
λ> lookupAllOrdered XWing orderedFleet
[6,3]
λ> lookupAllOrdered AWing orderedFleet
[4]
λ> lookupAllOrdered TIEFighter orderedFleet
[]