URL: https://linuxfr.org/users/guillaum/journaux/haskell-et-le-tri Title: Haskell et le tri Authors: Guillaum Date: 2016年02月18日T17:44:01+01:00 License: CC By-SA Tags: haskell et python Score: 30 Bonjour nal. Introduction ============ Cela fait longtemps que je n'ai pas posté ici, cela me manquait. Je trouve que LinuxFR ne parle pas assez de [Haskell](https://www.haskell.org/), alors je vais en parler un peu aujourd'hui sur une digression totalement inintéressante et proche de la masturbation intellectuelle. On va partir de rien et discuter de la fonction de tri fournie dans la librairie standard (base) de GHC, le compilateur le plus connu / utilisé. L'idée c'est de vous présenter un peu Haskell et sa syntaxe à partir d'un exemple simple à partir d'une fonction simple, le tri. Attention, on ne va pas implémenter de tri, mais on va voir comment utiliser les fonctions déjà existante pour construire une fonction de tri de plus haut niveau. Sort ==== Cette fonction s'appelle [sort](https://hackage.haskell.org/package/base-4.8.2.0/docs/Data-List.html#v:sort) et a comme signature : ```haskell sort :: Ord a => [a] -> [a] ``` Dit autrement, c'est une fonction qui prend `[a]`, une liste de n'importe quel type `a` et renvoie une liste de n'importe quel type `a`. Seule contrainte sur `a`, ce type doit être `Ord`onable, c'est à dire que on doit pouvoir comparer les éléments de `a` entre eux. La liste est une liste simplement chaînées et elle est non modifiable, ainsi le tri ne se fait pas en place, mais crée une nouvelle liste. Cela ressemblerait un peu à cette fonction en c++ : ```c++ template std::list sort(const std::list &l); ``` Exemple d'usage dans l'invite de commande ghci : ```haskell> import Data.List> sort [1, 10, 3, 2, 0, -1] [-1,0,1,2,3,10] ``` Sort By ======= Super ! Bon, il existe un autre variantes de cette fonction, [sortBy](https://hackage.haskell.org/package/base-4.8.2.0/docs/Data-List.html#v:sortBy). ```haskell sortBy :: (a -> a -> Ordering) -> [a] -> [a] ``` `sortBy` accepte une fonction de comparaison en plus de type `(a -> a -> Ordering)`, en gros, elle prend deux éléments et renvoi leur ordre. Exemple d'utilisation : ```haskell> let compareName nameA nameB | | nameA == "Chuck Norris" = GT | | nameB == "Chuck Norris" = LT | | otherwise = compare nameA nameB | > sortBy compareName ["Chuck Norris", "Bruce Wayne", "Bruce Banner", "Zorro", "Denver"] ["Bruce Banner","Bruce Wayne","Denver","Zorro","Chuck Norris"] ``` Notez comment j'écris une fonction de comparaison spécifique qui rend toute sa gloire à **Chuck Norris**. Cette example de code est équivalent au code python suivant, qui ne marche plus qu'en python 2, l'attribut `cmp` de `sorted` ayant disparu en python 3, ce que je regrette. : ```python>>> sorted([1, 10, 3, 2, 0, -1]) [-1, 0, 1, 2, 3, 10]>>> def compareName(nameA, nameB): ... if nameA == "Chuck Norris": return 1 ... if nameB == "Chuck Norris": return -1 ... return cmp(nameA, nameB) ... >>> sorted(["Chuck Norris", "Bruce Wayne", "Bruce Banner", "Zorro", "Denver"], cmp=compareName) ['Bruce Banner', 'Bruce Wayne', 'Denver', 'Zorro', 'Chuck Norris'] ``` Digression paresseuse --------------------- Petite digression sur Haskell, connaissez vous la complexité de cette opération : ```haskell> head (sort [1..100]) 1 ``` Naïvement on pourrait se dire, un tri, **O(n log n)**. Mais non, Haskell est paresseux et rend le résultat en **O(n)** car il n'a pas besoin de calculer le tri entier avant d'obtenir le résultat. Super non ? En pratique cela aide rarement et souvent cela complexifie la réflexion. Tri inversé ----------- Revenons à nos fonctions de tri. Je veux pouvoir trier ma liste à l'envers. En python, rien de plus simple, il suffit d'utiliser le paramètre optionnel `reverse` : ```python>>> sorted(["Chuck Norris", "Bruce Wayne", "Bruce Banner", "Zorro", "Denver"], cmp=compareName, reverse=True) ['Chuck Norris', 'Zorro', 'Denver', 'Bruce Wayne', 'Bruce Banner'] ``` En Haskell, ce n'est pas si simple... On peut utiliser `reverse`, mais cela va trier la liste dans un sens puis l'inverser, quelle perte de temps : ```haskell reverse (sortBy compareName ["Chuck Norris", "Bruce Wayne", "Bruce Banner", "Zorro", "Denver"]) ["Chuck Norris","Zorro","Denver","Bruce Wayne","Bruce Banner"] ``` Mais on peut aussi se dire que si on inversait les arguments de la fonction `compareName` avec `flip` alors cela fonctionnerait sans soucis : ```haskell> (sortBy (flip compareName) ["Chuck Norris", "Bruce Wayne", "Bruce Banner", "Zorro", "Denver"]) ["Chuck Norris","Zorro","Denver","Bruce Wayne","Bruce Banner"] ``` On peut donc facilement crée une fonction de plus haut niveau : ```haskell> let reverseSortBy f = sortBy (flip f) | > reverseSortBy compareName ["Chuck Norris", "Bruce Wayne", "Bruce Banner", "Zorro", "Denver"] ["Chuck Norris","Zorro","Denver","Bruce Wayne","Bruce Banner"] ``` Règle de compilation -------------------- On peut même crée une règle de compilation qui va remplacer automatiquement `reverse (sortBy f l)` par `sortBy (flip f) l` : ```haskell {-# RULES "reverse/sortBy" forall f l. reverse (sortBy f l) = sortBy (flip f) l #-} ``` C'est une chose que j’apprécie vraiment en Haskell, c'est que on peut écrire du code assez clair et plus tard le rendre efficace en transformant notre code automatiquement. Tri multiple ------------ Pour continuer, nous allons nous concentrer sur `sortBy` en Haskell ou l'attribut `cmp` de la fonction `sorted` de python. Je suis maintenant l'heureux utilisateur d'une liste de noms et de poids que je nommerais `l` : ```haskell> let l = [("Bruce Lee", 50), ("Batman", 100), ("Hulk", 200), ("La montagne", 100)] ``` J'aimerais trier ces gens par poids décroissant et par nom croissant en cas d'égalité. Nous allons faire cela en python, puis en Haskell, puis en Haskell for WarLdOrZOrgCoderZZZ. En python tout d'abord : ```python>>> l = [("Bruce Lee", 50), ("Batman", 100), ("Hulk", 200), ("La montagne", 100)]>>> def compare(t0, t1): ... c = cmp(t1[1], t0[1]) ... if c == 0: ... return cmp(t0[0], t1[0]) ... else: ... return c ... >>> sorted(l, cmp=compare) [('Hulk', 200), ('Batman', 100), ('La montagne', 100), ('Bruce Lee', 50)] ``` Rien de bien dramatique. C'est pas forcement beau, mais cela fait le boulot. Ma fonction de comparaison commence par comparer les indices `[1]` (donc les poids), observez l'inversion des arguments de cmp où je passe `t1` puis `t0` pour l'ordre décroissant. Si les deux sont égaux (car `cmp` renvoie `0`) alors je regarde le nom, sinon je renvois le résultat de la comparaison. En Haskell maintenant : ```haskell> let compare' t0 t1 = case (compare (snd t1) (snd t0)) of | EQ -> compare (fst t0) (fst t1) | ltOrGt -> ltOrGt | > sortBy compare' l [("Hulk",200),("Batman",100),("La montagne",100),("Bruce Lee",50)] ``` J'ai appelé ma fonction de comparaison `compare'` pour ne pas la confondre avec celle du système qui s'appelle `compare`. `snd` et `fst` sont sensiblement équivalents aux `[0]` et `[1]` de python. Ce que j'aime en Haskell c'est que bien que je n'ai mis aucune annotation de type, ils existent et sont vérifiés. J'aime aussi le fait que compare me renvoi `EQ` ou `GT` ou `LT` et non pas `-0` ou `-1` ou `1` comme le fait python. Bref, les avantages du typage statique sans les inconvénients. Un des défaut de cette méthode, c'est qu'elle va vite devenir complexe si j'ai plus de critères de tri. Nous allons régler ce problème. Première factorisation ---------------------- En premier lieu je n'aime pas la duplication de code qu'il y a sur `compare (snd t1) (snd t0)` et `compare (fst t0) (fst t1)`. Je propose de factoriser cela dans une fonction que nous nommerons de façon malicieuse `comparing`, je ne me suis pas foulé, elle existe déjà avec ce nom la ;) ```haskell> let comparing f a b = compare (f a) (f b) | > let compare' t0 t1 = case (comparing snd t1 t0) of | EQ -> comparing fst t0 t1 | ltOrGt -> ltOrGt | > sortBy compare' l [("Hulk",200),("Batman",100),("La montagne",100),("Bruce Lee",50)] ``` C'est plus simple ;) Comme [comparing](https://hackage.haskell.org/package/base-4.8.2.0/docs/Data-Ord.html#v:comparing) existe déjà dans la librairie standard, je vais me contenter de l'importer avec `import Data.Ord (comparing)`. On va continuer à factoriser un peu. Je n'aime vraiment pas cette inversion des arguments de `comparing snd t1 t0`. Cela ressemble à un bug, il manque un commentaire pour dire que je veux trier en ordre descendant. Bref, c'est peu agréables. Je vais écrire deux variantes de `comparing` : ```haskell ascending f a b = comparing f a b descending f a b = flip (comparing f) a b ``` Application partielle --------------------- Petite digression sur l'application partielle. En Haskell, tout est fonction. Il y a les fonctions constantes de type `t` et les fonctions unaires de type de type `t -> t'`. Par exemple, `abs` qui donne la valeur absolue, est une fonction unaire de `Int -> Int`. Mais le type de retour d'une fonction unaire peut être aussi une fonction. On peut donc avoir une fonction du type `a -> (b -> r)` qui peut s'écrire `a -> b -> c`. En appliquant cette fonction une unique fois sur une valeur de type `a` on obtient une fonction de type `b -> c`. Bref. On se sert souvent de cette propriété pour créer des fonctions avancée à partir de fonction plus simples. Exemple, la fonction d'addition s'écrit `(+)`, notez dans l'exemple suivant comment on peut l'utiliser en forme infix ou postfix, et comment on peut créer une fonction partiellement appliquée `inc` : ```haskell> (+) 1 2 3> 1 + 2 3> let inc = (+) 1> inc 5 6 ``` De façon similaire, toutes ces notations sont équivalentes, seul changent le fait que les arguments sont explicitement présents ou pas : ```haskell let add x y = (+) x y let add x y = x + y let add x = (+) x let add = (+) ``` Seconde factorisation --------------------- Revenons à nos fonctions `ascending` et `descending`. Voici le code prenant en compte ces nouvelles fonctions. Notez que j'ai un peu simplifié l'écriture de `ascending` et `descending` afin d'utiliser l'application partielle : ```haskell> let ascending = comparing> let descending = flip . comparing> let compare' t0 t1 = case (descending snd t0 t1) of | EQ -> ascending fst t0 t1 | ltOrGt -> ltOrGt |> sortBy compare' l [("Hulk",200),("Batman",100),("La montagne",100),("Bruce Lee",50)] ``` Bon, les choses commencent à devenir intéressantes. Ma fonction `compare'` commence à être bien claire, si ce n'est le case pour enchaîner sur le critère suivant si le premier critère est égale à `EQ`. On pourrait définir un opérateur binaire permettant de réaliser ce traitement, appelons cet opérateur `blork` juste parce que c'est marrant de lui donner ce nom et qu'aucun autre ne me vient à l'esprit là maintenant... ```haskell> let blork a b | | a == EQ = b | | otherwise = a ``` Notez la syntaxe de guard, qui permet de tester différentes équations afin de trouver la valeur de retour. Réécrivons encore une fois notre code, notez que j'utilise `blork` comme opérateur infix. ```haskell> let compare' t0 t1 = descending snd t0 t1 `blork` ascending fst t0 t1> sortBy compare' l [("Hulk",200),("Batman",100),("La montagne",100),("Bruce Lee",50)] ``` On factorise encore plus ------------------------ Cela va commencer à devenir plus simple de chaîner les prédicats puisqu'au lieu d'une cascade de `case` je peux simplement ajouter une composition avec `blork`. On pourrait même commencer à virer `compare'` et à mettre en place une fonction lambda anonyme : ```haskell> sortBy (\t0 t1 -> descending snd t0 t1 `blork` ascending fst t0 t1) l [("Hulk",200),("Batman",100),("La montagne",100),("Bruce Lee",50)] ``` Bon. Mais je ne suis encore pas satisfait par ça. Je n'aime pas cette fonction, la presence de `t0` et `t1` de partout. Ce que j'aimerais c'est écrire une fonction `blirk` qui permet de combiner deux fonctions de comparaison ensemble. On va l'écrire vite : ```haskell> let blirk f0 f1 a b = f0 a b `blork` f1 a b> sortBy (descending snd `blirk` ascending fst) l [("Hulk",200),("Batman",100),("La montagne",100),("Bruce Lee",5)] ``` Et voila, là je suis super content... J'ai une belle api, cela permet d'expliquer vraiment simplement ce que je veux. Mais il y a toujours ces deux fonctions `blirk` et `blork` pour lesquels j'ai du mal à donner un nom. Monoids ======= Je rappel, `blork` retourne le premier terme qui n'est pas `EQ`, tel que : ```haskell EQ `blork` GT `blork` LT == GT LT `blork` EQ `blork` GT = LT ``` Cela ne vous rappel rien ? : ```haskell True and True and True == True True and False and True == False ``` C'est très proche de l’opérateur `and` ou de l’opérateur `or` logique. En généralisant un peu, il s'agit d'un [Monoid]. Non, ce n'est pas une pub pour du shampoing, un monoid c'est un ensemble qui admet un élément neutre et une operation de réduction associative. Comme `(+)` et `0` ou `(*)` et `1` pour les entiers. Nos résultats d’égalité forment un monoid. L’élément neutre étant `EQ` et l'operation entre les éléments étant `blork`. On et bien avancé, oui ! Car ce concept est tellement courant qu'il y a une librairie standard dans Haskell qui gère les Monoids, [Data.Monoid](https://hackage.haskell.org/package/base-4.8.2.0/docs/Data-Monoid.html). Et coup de chance, `Ordering`, le type de `EQ`, `LT` et `GT` est géré. En haskell, les Monoids ont deux fonctions utiles, `mappend` et `mempty`. Regardons un peu celles-ci en action sur différents monoids. Tout d'abord les elements neutres, avec `mempty`. Ici, c'est un peu tordu, car `mempty` est une fonction constante polymorphique, c'est à dire que sa valeur dépend du type utilisé, d'où les annotation de type faites avec `::` que j'ai rajoutées. ```haskell> mempty :: Sum Int Sum {getSum = 0}> mempty :: Product Int Product {getProduct = 1}> mempty :: Ordering EQ> mempty :: String ""> mempty :: [Int] [] ``` Puis la fonction de réduction, `mappend` : ```haskell> Sum 5 `mappend` Sum 12 Sum {getSum = 17}> Product 5 `mappend` Product 12 Product {getProduct = 60}> [1,2,3] `mappend` [4,5,6] [1,2,3,4,5,6]> "Hello" `mappend` "you" "Helloyou"> EQ `mappend` GT GT> EQ `mappend` LT LT> GT `mappend` LT GT> GT `mappend` LT ``` Application au critères de tri ------------------------------ Donc en fait, ici, `mappend` c'est la fonction `blork`. Et comme `mappend` est super utilisée, il a un synonyme, l'operateur `()`. Nous pouvons donc dégager `blork` et utiliser `()` à la place. Qu'en est il de `blirk` ?. Rappel, cette fonction permettait de combiner ensemble plusieurs fonctions binaire retournant des monoids afin de crée une unique fonction binaire. Il se trouve que les fonctions sont aussi des monoids, voyons ce que cela implique. Je reprend donc ma définition de `blirk`: ```haskell> let blirk f0 f1 a b = f0 a b `blork` f1 a b ``` Je remplace `blork` par `` comme vu dernièrement : ```haskell> let blirk f0 f1 a b = f0 a b f1 a b ``` Au lieu d'appliquer l’opérateur `` entre les résultats de `f0` et `f1` appliqués à `a` et `b`, je peux appliquer l’opérateur `` entre f0 et f1 : ```haskell> let blirk f0 f1 a b = (f0 f1) a b ``` Bon... Super... Je vais nettoyer un peu en virant `a` et `b` grâce à l'application partielle : ```haskell> let blirk f0 f1 = f0 f1 ``` C'est pas mal, blirk est bien plus simple maintenant, mais est toujours là... Juste pour la forme, je pourrais écrire `` sous forme prefix : ```haskell> let blirk f0 f1 = () f0 f1 ``` Tient, mais je peux utiliser l'application partielle ici ! : ```haskell> let blirk = () ``` Et voila `blirk` n'est autre que l’opérateur de réduction des monoids... Je n'ai donc plus besoin de mes fonctions blirk et blork. Voici maintenant une session de shell complète me permettant d'arriver à mon résultat : ```haskell> import Data.List (sortBy)> import Data.Ord (comparing)> import Data.Monoid (())> let l = [("Bruce Lee", 50), ("Batman", 100), ("Hulk", 200), ("La montagne", 100)]> let ascending = comparing> let descending = flip . comparing> sortBy (descending snd ascending fst) l [("Hulk",200),("Batman",100),("La montagne",100),("Bruce Lee",50)] ``` Voila. Grâce à trois fonctions de la librairie standard et deux définitions triviales pour `ascending` et `descending`, j'ai réalisé un mini langage me permettant de paramétrer ma fonction `sortBy` pour réaliser n'importe quel type de tri. Définir ses propres types ------------------------- Notez que dans la vraie vie, je n'aime pas les tuples anonymes, donc je ferais mon propre type super hero que j'exploiterais de cette manière : ```haskell> data Hero = Hero {name :: String, weight :: Int} deriving (Show)> let l = [Hero "Bruce Lee" 50, Hero "Batman" 100, Hero "Hulk" 200, Hero "La montagne" 100]> sortBy (descending weight ascending name) l [Hero {name = "Hulk", weight = 200},Hero {name = "Batman", weight = 100},Hero {name = "La montagne", weight = 100},Hero {name = "Bruce Lee", weight = 50}] ``` Ceci afin de vous montrer la souplesse d'Haskell à ce niveau là. Je crois que `sortBy (descending weight ascending name)` ne peut pas être plus clair et de façon intéressante, cela n'a demandé aucun boilerplate. L'annotation `deriving (Show)` permet de munir mon type "Hero" d'un affichage par défaut que nous voyons dans le résultat. C'est l'équivalent de la surcharge de `__str__` en python ou de `ostream &operator<<(ostream&)` en C++, mais avec un comportement par défaut pas trop mal. Sort On ======= Je disais que je regrettais la disparition du paramètre `cmp` de la fonction `sorted` de python. Il est maintenant remplacé par le paramètre `key` qui s'utilise un peu comme notre fonction `comparing`. En python : ```python>>> sorted(["Hello", "My", "Friend"], key=len) ['My', 'Hello', 'Friend'] >>> sorted(["Hello", "My", "Friend"], key=len, reverse=True) ['Friend', 'Hello', 'My'] ``` La difference étant que cette approche n'appelle la fonction `key` qu'une fois par élément de la liste contrairement à la version avec `cmp` qui appelle cette fonction en moyenne **O(n log n)** fois. Mais en pratique elle nécessite de stocker une liste temporaire en plus. C'est donc un compromis entre mémoire utilisée et efficacité de la fonction de comparaison. La fonction [sortOn](https://hackage.haskell.org/package/base-4.8.2.0/docs/Data-List.html#v:sortOn) en Haskell fonctionne de façon similaire : ```haskell> sortOn length ["Hello", "My", "Friend"] ["My","Hello","Friend"] ``` Mais qu'en est il du tri inversé. Encore une fois il n'y a pas de fonction de tri avec reverse. L'idée étant que la fonction attendue par `sortOn`, ici `length` transforme nos éléments en une autre valeur qui est triable. Ici, Haskell propose un type, [Down](https://hackage.haskell.org/package/base-4.8.2.0/docs/Data-Ord.html#t:Down) qui inverse les propriétés de tri du type interne. Exemple : ```haskell> sortOn (Down . length) ["Hello", "My", "Friend"] ["Friend","Hello","My"] ``` La différence en terme d'API avec python est faible, mais revenons à un example plus complexe comme celui du tri de notre liste de héros. Nous allons réaliser une fonction de tri qui transforme un hero en tuple (poids du hero descendant, nom du héro), les tuples étant triés dans l'ordre lexicographique, cela résous notre problème : ```haskell> sortOn (\hero -> (Down (weight hero), name hero)) l [Hero {name = "Hulk", weight = 200},Hero {name = "Batman", weight = 100},Hero {name = "La montagne", weight = 100},Hero {name = "Bruce Lee", weight = 50}] ``` A ma connaissance il n'y a pas d'équivalent direct de `Down` en python, alors nous allons l'écrire. J'en profite pour aussi crée le type `Hero` pour pouvoir facilement comparer : ```python>>> class Hero: ... def __init__(self, name, weight): ... self.name = name ... self.weight = weight ... ... def __repr__(self): ... return "Hero(%r, %r)" % (self.name, self.weight) ... >>> l = [Hero("Bruce Lee", 50), Hero("Batman", 100), Hero("Hulk", 200), Hero("La montagne", 100)]>>> class Down: ... def __init__(self, obj): ... self._obj = obj ... def __lt__(self, other): ... return self._obj.__gt__(other._obj) ... def __gt__(self, other): ... return self._obj.__lt__(other._obj) ... def __eq__(self, other): ... return self._obj.__eq__(other._obj) ... >>> sorted(l, key=lambda hero: (Down(hero.weight), hero.name)) [Hero('Hulk', 200), Hero('Batman', 100), Hero('La montagne', 100), Hero('Bruce Lee', 50)] ``` Voila, on peut faire la même chose, mais la lib standard Haskell propose ici des solutions déjà implémentées. Conclusion ========== Voila, j'espère que cette introduction à Haskell vous aura fait plaisir, j'ai essayé d'aborder un problème simple, le tri, et en tirant un peu dessus, montrer quelques subtilités du langage. A bientôt.

AltStyle によって変換されたページ (->オリジナル) /