Programmation fonctionnelle
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) ]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
[]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")]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 [])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)]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.
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)]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"))]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"])]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
NothinglookupMany 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 []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 xL’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 :
[] -> Nothing : si la liste obtenue est vide, aucun
élément ne convient.x:_ -> Just x : si elle est non vide, x
désigne son premier élément. Le symbole _ indique que l’on
ignore le reste de la liste.Par exemple :
λ> findWhere even [3,7,4,8]
Just 4
λ> findWhere (>10) [2,5,8]
NothingOn 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 xcase 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.
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.
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
EQOn 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) ]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)]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)]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
[]