Le Haskell, un langage au label pure. Seconde partie.

Nous continuons de dĂ©couvrir des paysages fonctionnels Ă  travers le Haskell. Cette fois, nous nous Ă©loignons des gĂ©nĂ©ralitĂ©s et rentrons dans le vif du sujet en nous intĂ©ressant Ă  des aspects plus propre au haskell (bien que d’autres langages fonctionnels implĂ©mentent des fonctionnalitĂ©s similaires).

La premiĂšre partie est disponible ici. La troisiĂšme lĂ .

La force de haskell

Les listes infinies (et listes en compréhension)

Les listes infinies sont une des nombreuses possibilitĂ©s offertes par un langage paresseux. C’est souvent d’elles dont on entend le plus parler pour prĂ©senter le haskell, alors qu’il ne s’agit pourtant que d’une fonctionnalitĂ© original parmi tant d’autres. Cela est sĂ»rement du au fait que la notion d’infinie Ă©veille la curiositĂ© des dĂ©veloppeurs habituĂ© Ă  un monde impĂ©ratif oĂč les tableaux, les listes, et toute structure mĂ©moire est finie.

Le principe est relativement simple : vous définissez une liste, que ce soit de façon récursive ou simplement par compréhension (on vas voir ce que cela signifie dans quelques lignes), puis seulement les éléments de la liste dont le programme auras besoin seront évalué. Les autres ne seront jamais calculés.

Comment faire de telles listes? La façon la plus simple est la dĂ©finition de liste par comprĂ©hension, c’est Ă  dire une dĂ©finition de la forme “L’ensemble des f(trucs) pour les quels P(truc) est vraie”. OĂč f est une formule sur “trucs” et oĂč P est une proposition, disons une fonction qui renvoie True ou False.

Par exemple :

-- "x <- l" signifit "pour x se baladant dans la liste l"
-- l1 = [1, 2, 3, 4, 5]
l1 = [x | x <- [1, 2, 3, 4, 5]]
-- L'opérateur c/c++ != s'écrit /= 
-- l2 = [1, 2, 4, 5]
l2 = [x | x <- [1, 2, 3, 4, 5], x /= 3]

-- l3 = [2, 4, 8, 16, 32]
l2 = [2^x | x <- [1, 2, 3, 4, 5]]

-- l4 = [2, 4, 16, 32]
l4 = [2^x | x <- [1, 2, 3, 4, 5], x /= 3]

En fait, c’est une sorte de sucre syntaxique. Le soucis, c’est que ce que cache les listes en comprĂ©hension ne seras aborder que dans la troisiĂšme partie. On se contenteras donc de la signification et de la façon dont on l’utilise.

Pour en revenir a nos listes en comprĂ©hension infinie, on peut penser Ă  “L’ensemble des entiers qui sont paire” par exemple. Voici quelques listes infinies :

--La liste de tous les entiers Ă  partir de 42 peut s'Ă©crire [42..]
liste_infinie_des_entiers = [1..]

--Pour calculer x % 2 (c/c++), on Ă©crit "x `mod` 2", ou encore "mod x 2".

liste_des_entiers_paires = [2 * x | x <- [1..]]
-- On peut rajouter des conditions séparé par des virgules
liste_des_entiers_paires' = [x | x <- [1..], x `mod` 2 == 0]

-- On peut utiliser plusieurs variables se baladant dans différentes listes :
liste_de_produit = [x * y | x <- [1..5], y <- [1..]]

Une autre façon de dĂ©finir une liste est d’utiliser la rĂ©cusivitĂ©. Voici quelques exemples.

--"map f l" applique la fonction f sur chaque élément de la liste l
-- [a, b] est du sucre syntaxique pour a : b : [].
entiers = 1 : (map (1+) entiers)

Regardons se qui se passe si l’on demande les trois premiers Ă©lĂ©ments de la liste, ce qui se fait avec take 3 l. D’abord, il lit 1 : et connais donc le premier Ă©lĂ©ment. Pour avoir le second, il lit (map (1+) entiers). Il applique donc map sur la liste, mais de façon paresseuse, c’est a dire qu’en ne calculant que l’application sur le premier terme. Il obtient donc (1+)(1) = 2. puis, pour avoir le troisiĂšme Ă©lĂ©ment, il doit appliquer (1+) au deuxiĂšme Ă©lĂ©ment de la liste entier. Ça tombe bien, on vient de le calculer, c’est 2. On a donc pour troisiĂšme Ă©lĂ©ment (1+)(2) = 3.

De cette façon, on aurais aussi pu dĂ©finir la liste des entiers pairs, la liste des nombres de fibonacci (mĂȘme si on ne voit pas bien l’intĂ©rĂȘt dans un programme), ou la liste des nombres premiers (plus difficile).

Bon, c’est trĂšs beau tout ça, mais est-ce que ça sert vraiment (parce que, faire des listes infinies pour faire des listes infinies
)? Oui, ça sert, et voici un exemple simple et concret. Disons que vous participez au Google Code Jam. Vous devez fournir des rĂ©ponse en respectant un certain format. Plus prĂ©cisĂ©ment, on vous donne une entrĂ©e de n Ă©lĂ©ments Ă  traiter, par exemple n lignes contenant chacune un nombre, et vous devez fournir le rĂ©sultat de votre traitement sous la forme _Case #i: \n_. En C++, on aurais itĂ©rĂ© sur la liste de rĂ©sultat (ou directement l'entrĂ©e) et provoquĂ© l'Ă©criture de "Case #i" sur la sortie standard juste avant celle de vos donnĂ©es. En haskell, on peut (doit?) faire ça diffĂ©remment (J'ai honteusement pompĂ© ce que propose un dĂ©veloppeur sur [youtube](http://www.youtube.com/watch?v=_tgv3HVgOMc)) :

boilerPlate :: [String]
boilerPlate = ["Case #" ++ show n ++ ": " | n <- [1..]]

standardOutput :: [String] -> [String]
-- zipWith f l1 l2 recole les deux listes l1 et l2 en utilisant la fonction f sur les éléments de chacune des deux listes.
-- La liste produite par zipWith fait la longueur de la plus courte.
-- Par exemple, zipWith (+) [1, 2, 3] [1, 1, 1, 1, 1] = [1+1, 2+1, 3+1]
standardOutput = zipWith (++) boilerPlate

-- Une fois votre sortie sous la forme d'une liste de String, il vous suffit de la donner Ă  standardOutput pour obtenir le formatage attendu

On voit ici que la liste infinie boilerPlate contient tous les formatages possibles. Bien entendu, Ă  chaque exĂ©cution, il n’y auras qu’un nombre finie d’entrĂ©es et de sorties, donc une partie finie de la liste qui seras utilisĂ©.

Data-driven programming

En haskell, manipuler des listes ou des structures similaires est chose courante, et il y a un bon nombre de fonction dĂ©diĂ©s. Par exemple map f l qui permet d’appliquer f sur les Ă©lĂ©ments de l, zip et zipWith qui permettent de souder deux liste en une unique (soit sous forme de liste de couple, soit en utilisant la fonction que vous fournissez). Mais ce n’est pas tout. Nous ne parlerons par exemple pas de foldr et foldl qui permettent a partir d’une liste d’élĂ©ments de l’écraser en un nouvel Ă©lĂ©ment grĂące Ă  une fonction que vous fournissez (leurs usages est multiple. On peut implĂ©menter facilement la somme/produit des Ă©lĂ©ments d’une liste, la conversion d’une liste de mot en une seul chaine de caractĂšre, la transformation d’une liste en un arbre binaire de recherche, etc).

Vous devriez avoir remarquer qu’en haskell, on aime bien concevoir de petites fonctions travaillant sur un Ă©lĂ©ment de type a, et produisant un Ă©lĂ©ment de type b, puis appliquer ces petites fonctions sur les Ă©lĂ©ments de structures de donnĂ©s plus ou moins complexe. Cela a de nombreux avantages : -Il est plus simple de concevoir une fonction de type Int->String qu’une fonction de type [Int] -> [(String, Int)], par exemple. -On est plus gĂ©nĂ©rique ; Si l’on sais transformer du a en b, alors on sais transformer du [a] en [b] et du Tree a en Tree b (oĂč Tree a est un arbre binaire oĂč chaque noeud contient un Ă©lĂ©ment de type a). -En cas de changement de structure mĂ©moire, par exemple pour des raisons de performances, on minimise l’impacte sur le code Ă  modifier. Si l’on souhaite passer de liste Ă  des arbres, seul le traitement effectuĂ© sur les listes devras ĂȘtre rĂ©-Ă©crit pour les arbres, mais rien d’autre.

On se retrouve donc Ă  se concentrer plus sur les types qu’on manipule que la façon dont on les manipule. C’est Ă  dire que l’on dispose d’un nombre important de façon simple de transformer certaines donnĂ©es en d’autres, et les points cruciaux sont alors de: -Bien choisir la façon dont seront reprĂ©sentĂ©s les donnĂ©es traitĂ©es -Trouver les structures de donnĂ©es intermĂ©diaires au cours du dĂ©roulement d’un algorithme.

Si l’on sais exactement de quels donnĂ©s l’on part, et quels donnĂ©s on droit produire, il ne reste alors plus qu’à dĂ©crire les transformations nĂ©cessaire pour passer de l’une Ă  l’autre. Par exemple, faire un programme de reconnaissance de caractĂšre, c’est simplement transformer une image en une chaĂźne de caractĂšre. Pour peut que l’on parvienne Ă  rĂ©duire l’écart entre les structures de donnĂ©s considĂ©rĂ©s (par exemple une image, puis une liste de rectangles de pixels reprĂ©sentant des lignes, puis une liste de liste de rectangles de pixels reprĂ©sentant des mots) il devient trĂšs simple de dĂ©crire la transformation (on a rĂ©ussi a rĂ©duire le problĂšme a savoir dĂ©couper les lignes, dĂ©couper les mots, dĂ©couper les lettres puis reconnaĂźtre une lettre).

Si ce type de raisonnement peut conduire à du code catastrophique dans un langage objet, en haskell c’est trùs certainement l’une des routes les plus sur. Tout, dans le langage, s’adapte parfaitement à cette conduite, et particuliùrement le systùme de types et de classes.

En C++ un type reprĂ©sente un ensemble de fonctionnalitĂ©s. En haskell un type n’est rien d’autre qu’un ensemble possible de valeur. On peut tout de fois prĂ©ciser qu’un type peut ĂȘtre manipulĂ© d’une certaine façon (ordonnĂ©, comparĂ©, affiché ). On pourrait dire que deux Ă©lĂ©ments d’un type que l’on a construit peuvent ĂȘtre affichĂ©, ou encore comparĂ©, en le faisant instance d’une classe. Cela correspond a la surcharge de fonctions/opĂ©rateurs du C++ ; aprĂšs avoir dĂ©clarer une structure struct St;, on peut surcharger l’opĂ©rateur de comparaison pour ce nouveau type par bool operator < (St &a, St &b);. Vient alors l’idĂ©e de ce que doit ĂȘtre quelque chose “d’affichable” ou de “comparable”. C’est un type pour le quel on doit avoir certaines fonctions de dĂ©finies. En java, il y Ă  la notion d’interface, oĂč l’on veut imposer l’existence de certaines mĂ©thodes. Malheureusement, on ne peut le faire que lors de la dĂ©claration d’un type, et l’implĂ©mentation de cette interface est faite “à l’intĂ©rieur” du type. En haskell, pas de fonctions membres, mais des fonctions tout cours. Ce qui fait que n’importe quel type pourra devenir instance de n’importe quel classe (terme haskell dĂ©signant un jeu de fonctions) et Ă  l’instant oĂč vous le dĂ©sirerais. Le sens d’une classe en haskell est donc plus proche de celle de la thĂ©orie des ensembles (une collection d’objets [ici de types] qui respectent certaines conditions [ici, pouvoir ĂȘtre comparĂ©, affiché ]) ou si vous voulait vraiment une analogie en langage impĂ©ratif, des interfaces du java. Ce n’est certainement pas celui des classes C++.

Quand on prĂ©tend qu’un type est instance d’une classe, on doit fournir l’implĂ©mentation des fonctions de la classe, mais pas nĂ©cessairement toutes. Les classes fournissent souvent une implĂ©mentation des fonctions, souvent en terme rĂ©cursif. Par exemple on pourrais dĂ©finir a /= b Ă  partir de == et a == b Ă  partir de /=. De cette façon, il suffit de dĂ©finir l’une des deux fonctions pour pouvoir immĂ©diatement utiliser les deux opĂ©rateurs. (Le compilateur s’assurant que cela n’engendre pas de sur-coĂ»t en terme de performances).

Voici par exemple la classe Eq, dĂ©crivant deux objets pouvant ĂȘtre comparĂ© :

class  Eq a  where
class Eq a where
    (==) :: a -> a -> Bool
    (/=) :: a -> a -> Bool
    x == y = not (x /= y)
    x /= y = not (x == y)

On rend un type instance d’une classe de la façon suivante (exemple honteusement tirer de Learn you haskell for a great good :

data TrafficLight = Red | Yellow | Green

instance Eq TrafficLight where
    Red == Red = True
    Green == Green = True
    Yellow == Yellow = True
    _ == _ = False

On dĂ©finit l’égalitĂ© grĂące au filtrage par motif, en dĂ©finissant seulement l’opĂ©rateur ==.

Bon, à vrais dire, pour les classes comme Eq (comparable) et Show (affichable), on peut laisser haskell s’en charger comme un grand :

data TrafficLight = Red | Yellow | Green deriving (Show, Eq)

En fait, quand on parleras de foncteurs, foncteurs applicatifs ou monades, on parleras de type qui sont instance respectivement de Functor (Prelude.Functor), de Applicative (Control.Applicative) et de Monad (Control.Monad).

Les foncteurs

Les foncteurs (Ă  nouveau, le terme est Ă  prendre au sens e la thĂ©orie des catĂ©gories) constituent le point de dĂ©part vers les monades. Faisons un petit dĂ©tour par les maths et dĂ©finissons ce qu’est un foncteur (il n’est pas nĂ©cessaire de comprendre ce paragraphe pour la suite, c’est pour la culture).

La catĂ©gorie des types :_ Une catĂ©gorie $\mathcal{C}$ est une collection d’ensembles. Ici, on regarderas la collection de tous les types hasell possible. Un ensemble seras donc un type. Ses Ă©lĂ©ments seront les valeurs qui sont de ce type. Par exemple Int seras un semble et 1, 4, 6 sont des Ă©lĂ©ments de cette ensemble. Il n’y a que deux Ă©lĂ©ments dans l’ensemble Bool, et une infinitĂ© d’élĂ©ments pour Integer. Pour que ce soit une catĂ©gorie, il faut qu’étant donnĂ© deux ensembles de notre collection $A$ et $B$, il existes une ensemble d’applications de $A \to B$. Dans notre cas ce seras toute les fonctions de type A -> B . On parle des “flĂšches de A vers B”. Pour la culture, on note l’ensemble de ces applications $Hom_{\mathcal{C}}(A, B)$.

Attention, pour que ce soit vraiment une catégorie, il faut quelques conditions sur ces flÚches :

1) Si $A$ est un Ă©lĂ©ment de $\mathcal{C}$, alors il faut que l’identitĂ© soit une flĂšche. Dans notre cas, on veut que la fonction id x = x de type A -> A soit bien une fonction haskell. Ce qui est le cas, puisque je viens de vous donner le code haskell qui permet de la dĂ©finir :)

2) Si $f: A \to B$ et $g : B \to C$ sont deux flĂšches (respectivement de $A$ dans $B$ et de $B$ dans $C$), alors la composĂ© $g \circ f$ est une flĂšche de $A$ dans $C$. Dans le cas qui nous intĂ©resse, cette rĂšgle est bien respectĂ©e car si f et g sont deux fonctions haskell, alors la composĂ© est la fonction \x -> g (f x), que l’on peut aussi Ă©crire f . g.

Donc, pour rĂ©sumer : La collection de tous les types haskell est une catĂ©gorie. Si a et b sont deux types haskell, l’ensemble de toute les fonctions de a -> b sont appelĂ©s les flĂšches entre a et b.

Les foncteurs (covariants) : Un foncteur $F$ d’une catĂ©gorie $\mathcal{C}$ vers une catĂ©gorie $\mathcal{D}$ est :

1) Pour chaque semble $A$ de $\mathcal{C}$, un ensemble de $\mathcal{D}$ qu’on noteras $F(A)$.

2) Pour chaque flùche $f : A \to B$ entre des ensembles de $\mathcal{C}$, une flùche $F(A) \to F(B)$ qu’on noteras $F(f)$.

3) Il faut que $F(g \circ f) = F (g) \circ F(f)$ et que $F(id) = id$. C’est Ă  dire que composer des flĂšches avant transformation est la mĂȘme chose que les composer aprĂšs, et l’identitĂ© $id: A \to A$ (flĂšche qui ne fait rien) est bien envoyer sur l’identitĂ© $id: F(A) -> F(A)$.

Un foncteur est donc une façon de transformer une catégorie $\mathcal{C}$ en une partie (sous-catégorie) de $\mathcal{D}$.

Point culture (pour les curieux) : Les foncteurs contravariants sont simplement des foncteurs qui “renversent” les flùches, c’est à dire en transforment A -> B en F(A) <- F(B).</i>

Ici, ce qui nous intĂ©resse sont les foncteurs de $\mathcal{C}$ dans $\mathcal{C}$ (on dit des endofoncteurs). À partir de maintenant, on ne considĂšre plus que la catĂ©gorie $\mathcal{T}$ des types haskell. Un foncteur Fonc, en haskell, est un foncteur de $\mathcal{T}$ dans $\mathcal{T}$. C’est Ă  dire :

1) Une façon Ă  tout type a d’associer un type Fonc a. Ainsi Fonc est un constructeur de type, par exemple Liste ou Arbre des exemples prĂ©cĂ©dents. C’est peut-ĂȘtre le bon moment d’aller feuilleter quelques lien sur les constructeurs de type et leur “kind”. Disons simplement qu’un type comme int ou bool est de kind * mais que Liste et Arbre sont de kind * -> *. Cela signifit que ces deux dernier mangent un type T et fabrique des nouveaux types Liste T et Arbre T. Liste n’est donc pas un type, mais un constructeur de type.

2) Une façon à toute fonction f :: a -> b d’associer une fonction f' :: Fonc a -> Fonc b

3) Cette façon de faire doit transformer l’identitĂ© (\x -> x) :: a -> a en l’identitĂ© (\x -> x) :: Fonc a -> Fonc a

4) Cette façon de faire doit passer Ă  la composition, c’est Ă  dire que si l’on transforme f :: a -> b en f' :: Fonc a -> Fonc b et g :: b -> c en g' :: Fonc b -> Fonc c, alors ` g . f ` seras transformĂ© en g' . f'.

Pour qu’un constructeur de type Fonc soit un foncteur, on le fait instance de la classe Functor dĂ©finie comme suit :

class  Functor f  where
    fmap        :: (a -> b) -> f a -> f b

Remarquez que l’on peut lire fmap :: (a -> b) -> (f a -> f b) ce qui signifie : fmap(fonctorial mapping) prend une fonction de type a -> b et la transforme en une fonction de type f a -> f b. On a donc bien une transformation d’une flĂšche de a vers b en une flĂšche de $f a$ vers $f b$. Si l’on a donc un constructeur de type qui est instance de Functor, on a bien un endofoncteur de la catĂ©gorie des types. Maintenant que nous avons le sentiment que toutes nos considĂ©rations thĂ©oriques nous ont apportĂ© une comprĂ©hension profonde du sujet, nous allons pouvoir les oublier et passer Ă  la pratique.

A quoi sert un foncteur : Un constructeur de type fonctoriel, c’est un constructeur de type oĂč l’on sauras maper des fonctions. Si notre type Liste devient instance de Functor, et que l’on a un Liste Int, on peut construire rapidement une liste de tous ces nombres reprĂ©sentĂ© par des chaines de caractĂšres. Il suffit de disposer d’une fonction Int -> String. Haskell nous en fournis une, c’est show. Alors, on n’a plus qu’a appliquer cette fonction sur chacun des Ă©lĂ©ments de la liste par map show liste.

Regardons comment rendre Liste instance de Functor :

instance  Functor Liste  where
    fmap f Vide = Vide
    fmap f (Element h t) = Element (f h) (fmap f t)

-- Maintenant, on peut mapper des fonctions sur des listes
estPositif n = (n >= 0)

listeEntiers = Cons 1 (Cons (-5) (Cons (-30) (Cons 4 Vide) ) )
listeEstPositif = fmap estPositif listeEntiers
-- listeEstPositif = Cons True (Cons False (Cons False (Cons True Vide)))

Si vous rĂ©flĂ©chissez bien, ça ressemble beaucoup Ă  ce que vous faites Ă  chaque fois que vous appliquez un traitement aux Ă©lĂ©ments d’un container ; vous parcourez une liste, et vous appliquez votre procĂ©dure Ă  chaque Ă©lĂ©ment. L’avantage d’avoir une unique fonction fmap implĂ©mentĂ© pour chaque type, c’est que si vous dĂ©cidez de modifier votre container, vous n’aurez que trĂšs peut de changement Ă  faire. Il suffiras de rendre le nouveau container instance de Functor, alors qu’en C++, si vous utilisiez auparavant des containers de la STL, il vous faudra vous assurer que votre nouvelle structure fournie elle aussi des littĂ©rateurs, ce qui peut ĂȘtre assez lourd Ă  fournir, voir impossible si vous n’ĂȘtes pas auteur de la classe.

Parmi les instances de Functor il y a donc les listes (les vrais listes []), mais aussi Maybe. On peut donc utiliser Maybe pour utiliser des valeurs dans un contexte. Par exemple :

divideBy :: Int -> Int -> Maybe Int
divideBy n m = if m == 0 then Nothing else (n `div` m)


doSomething :: Int -> Int
doSomething n = (n + 32) * 5


res = fmap doSomething (divideBy 3 7)

Il est trĂšs important de bien saisir l’intĂ©rĂȘt des foncteurs (qui n’est pas cantonnĂ© aux langages fonctionnels), et leur fonctionnement pour la suite. La derniĂšre partie ne traiteras que de leurs spĂ©cialisations : les foncteurs applicatifs et les monades.

Point culture : Et si l’on veux un foncteur contravariant en haskell? On peut prendre par exemple le constructeur de type type Func a = a -> Int et la fonction map :: (a -> b) -> (b -> Int) -> (a -> Int) ; map f fa = fb . f. On construit bien une fonction de type a -> Int Ă  partir d’une fonction de type b -> Int. On a donc “inversĂ© les flĂšches”, puisque l’on part de “a -> b” pour obtenir du “Func b -> Func a”.</i>

Références :