Un court article donnant un petit aperçu du langage haskell, à destination des développeurs aillant l'habitude de travailler avec des langages impératifs. Cet article n'est pas un cours!

Votre avis et vos suggestions nous intéressent !
Alors après votre lecture, n'hésitez pas  : Commentez

- Titre : Un bref aperçu de haskell

- Auteur : Cochoy Jérémy

- Parution : 28 juillet 2013

- Mise à jour : 28 juillet 2013

- Public visé :

- Licence : Les sources présentés sur cette page sont libres de droits, et vous pouvez les utiliser à votre convenance. Par contre cette page de présentation de ces sources constitue une oeuvre intellectuelle protégée par les droits d'auteurs. Copyright © 2013 Zenol. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à 3 ans de prison et jusqu'à 300 000 € de dommages et intérêts. Droits de diffusion permanents accordés à Developpez LLC. Cette page est déposée à la SACD.

Sommaire

- I. Introduction.

- II. Généralités sur les langages fonctionnels.

- II.A. Ce que tout le monde sais... ou presque.

- II.B. Curryfication.

- II.C. Typage.

- II.D. Pattern matching.

- III. Foncteurs.

- III.A. Les listes infinies (et listes en compréhension)

- III.B. Data-driven programming.

- III.C. Les foncteurs.

- IV. Foncteurs applicatifs.

- IV.A. On se prépare au grand saut avec maybe.

- IV.B. Premier plongeon avec les listes.

- IV.C. En apnée : les foncteurs (->) r !

- IV.D. Quelques règles que null ne doit ignorer.

- V. Monades.

- V.A. Être ou ne pas être?

- V.B. Un calcul pas très déterministe.

- V.C. La notation do.

- V.D. Le retour de (->) r

- V.E. Point culture

- VI. Références :

I - Introduction.

Un court article donnant un bref aperçu du langage haskell. Cet article est à destination des développeurs aillant l'habitude de travailler avec des langages impératifs, n'aillant peu ou pas travailler avec des langages fonctionnels, et souhaitant avoir une petite idée de ce à quoi ressemble un bout de code haskell.

Cet article n'est pas un cours! Si vous désirez apprendre haskell, deux excellents livres sont Learn You Haskell For a Great Good et Real World Haskell. Le premier traduit en français, et tous deux sont lisible en ligne. Les développeurs expérimentés préférerons surement le second, plus vaste et technique que le premier.

Encore une fois, si vous êtes décidé et voulez apprendre le haskell, ne perdez pas de temps et lisez un cours complet. Si vous êtes juste curieux, continuez.

L'essentiel de tout les extraits de code peuvent être compiler avec ghc / tester avec ghci.

II - Généralités sur les langages fonctionnels.

On y vas tout en douceur. Curryfication et typage, pour ceux qui n'ont pas déjà découvert les joies (et maux de tête) qu'apportent ces derniers. Si vous avez déjà eu à toucher à des langages fonctionnels, vous souhaiterez sûrement passer directement à la seconde partie où j'aborderais les diverses fonctionnalités original de ce langage, comme les fameuses liste infinies dont tout le monde parle, mais dont trop peu se doutent de l'utilité. On parleras de data driven programming, de fonctions sans effets de bord, etc. Enfin, pour conclure cet article, on abordera les monades.

On ne fera qu'effleurer les constructions monadiques, on ne parlera pas des monades transformer, ni des arrow, et encore moins des nombreuses autres originalités dont le haskell abonde. La raison? C'est technique, et inabordable sans de vrais base dans le langage. Pour y accéder, il vous faudras d'abord avoir de solide bases.

Allons y pour la première partie.

II.A - Ce que tout le monde sais... ou presque.

Faisons un retour sur ce que l'on retrouve dans tous les langages fonctionnels, et ce qui les rend si différents.

Histoire de fixer la syntaxe, une fonction qui prend deux nombres et retourne leur produit s'écrit :

mult :: (Num n) => n -> n -> n
mult a b = a * b

Une fonction qui ajoute 42 à un entier :

addOne :: (Num n) => n -> n
addOne a = a + 42

La première ligne est le typage de la fonction (souvent facultatif), et la seconde est le corps de la fonction. En C++, ça donnerais :

template <class T>
T mult(T a, T b)
{
return a * b;
}

T addOne(T a)
{
return a + 42;
}

En fait, le "n" qui apparaît dans le type peut être remplacé par n'importe quel lettre/mot qui vous plaît. Cela signifie un type quelconque, qui respecte la contrainte "peut être multiplié" décrite par "(Num n) =>".

La présence de "Num" correspond à la nécessiter d'avoir, dans le code c++, une surcharge de l'opérateur *. Remarquez qu'une fonction en haskell correspond naturellement a une fonction template, à moins de forcer les types à être moins "puissant", comme par exemple :

mult :: Int -> Int -> Int
mult a b = a * b

Qui ne sais plus que multiplier des entiers.

II.B - Curryfication.

La curryfication est essentiellement un changement de point de vue. On peux considérer une fonctions prenant deux nombres, et retournant une valeur. Mais on peut aussi changer de point de vue et considérer une fonction prenant un nombre, et renvoyant une nouvelle fonction, prenant un nombre, et retournant une valeur.

Cela explique l'étrange notation pour le type de la fonction mult. En fait, l'opérateur "->" est associatif à droite, c'est à dire qu'il fallait lire :

mult :: (Num n) => n -> (n -> n)

Où X -> Y indique que la fonction prend du type X et retourne du type Y. Ainsi, n -> n signifie prend un type n quelconque et renvoi quelque chose du même type. C'est le type d'une fonction. Si l'on veux un exemple plus concret, Int -> (Float -> Double) signifie une fonction qui prend un entier, puis renvoi une nouvelle fonction. Cette dernière prend un float et le transforme en un double.

Partant de ce point de vue, il parait naturel de fixer les premiers arguments d'une fonction curryfiée. L'application d'un élément à un autre étant associatif à gauche, il suffit de l'appeler avec une partie de ses arguments.

En effet, écrire mult a b signifie ((mult a) b). C'est à dire appliquer mult à a pour obtenir une fonction qui "prend un entier et le multiplie par a", puis évaluer cette fonction sur l'entier b.

Par exemple :

-- Définition
nouvelle_fonction = mult 42

-- Utilisation de la nouvelle fonction
nouvelle_fonction 23

correspond à fixer la première valeur de la fonction mul à 42.

En C++ 98/03, il n'existe pas de mécanisme d'application partiel. Il nous faudrai donc écrire

-- Il nous faux ajouter cette version 'partiellement applicable' de mult.
template<class T, T n>
T mult(T b)
{
return n * b;
}

-- Définition
template<class T>
T nouvelle_fonction(T b)
{
return mult<T,42>(b);
}

-- Utilisation
nouvelle_fonction(23);

Depuis C++11, on peut enfin effectuer des applications partiels à partir de la première définition de mult. Il faudrais quelque chose de la forme auto f = std::bind(42, std::placeholders::_1);. C'est malheureusement toujours moins lisible qu'en haskell.

Pour finir, puisque l'on est en plein dans la manipulation de fonctions, on peut écrire une fonction comme une valeur, et la stocker dans une "variable".

-- Pour écrire une fonction "anonyme", qui prend trois arguments et renvoi 42, on peut écrire
-- (\x y z -> 42)
-- Où x y z seront les trois arguments, et ce qui suit -> est la "valeur de retour".
-- On aurait donc pu écrire la fonction mult de la façon suivante :
mult = (\a b -> a * b) :: (Num n) => n -> n -> n

--On peut aussi écrire \a -> \b -> à la place de \a b, grâce à la curryfication.

Le typage est bien-sur facultatif.

On a alors deux fonctions bien pratiques pour manipuler des fonctions ; l'identité et la composition :

id = \x -> x
a . b = \x -> a (b x)

On peut composer la multiplication par 2 et l'addition à 3 de la façon suivante :

add a b = a + b
superFct = mult 2 . add 3

Enfin, on aurais pu écrire :

mult = (*)
add = (+)
superFct = (2*) . (3+)

II.C - Typage.

Les types, en langage fonctionnel, disent beaucoup de choses, et sont lourd de sens. En haskell, une liste d'entiers se note [Int]. Si a est un type, alors une liste de a est de type [a]. Les chaînes de caractères sont par exemple des [Char].

Alors, que devrait faire une fonction de type (a -> b) -> [a] -> [b] ? Et bien, elle prend une fonction transformant du a en b, une liste de a, et produit une liste de b. Le bon sens veux que cette fonction applique la première fonction sur chaque élément de la liste a, pour produire la liste b.

Encore un, pour la route. Que dire du type [[a]] -> [a]? On prend une liste de liste, et on produit une liste. La première chose qui nous vient à l'esprit est de concaténer toute ces listes les unes à la suite des autres.

Voyez tout ce qu'on peut deviner grâce aux types. Trouver le type de la fonction que l'on veux écrire, c'est parfois avoir accomplit la moitier du travail.

On peu aussi construire des alias de type. Par exemple, plutôt que décrire [Char], on peut écrire String, définit par :

type String = [Char]

C'est très utile pour annoter une fonction. Par exemple, on peut imaginer le scénario suivant :

type Nom = String
type Prenom = String
type Identifiant = Int

getSomeone :: Nom -> Prenom -> Identifiant

Ces alias, sont une façon d'ajouter une valeur sémantique (signification du premier argument) au type de la fonction getsomeone.

Mais le meilleur est à venir : les constructeurs de type. Attention, un constructeur en haskell est tout sauf un constructeur C++. Ça se rapprocherais plutôt de la structure, et encore...

Pou faire bref, les constructeur permettent de fabriquer des instances d'un type. Considérons quelques types (on parle de types algébriques) :

data Personne = ConstructeurDePersonne Nom Prenom Identifiant
data Reponse = Oui | Non
data LaValeur = Entier Int | Flotant Float
data ListeEntier = Element Int Liste | Vide
data ArbreEntier = Noeud Int Arbre Arbre | Vide

Considérons des équivalents à ces types en C/C++. Le premier type, Personne, est une structure à trois champs. Le second, est un type booléen, qui peut soit être construit par le constructeur Oui, soit par le constructeur Non. Le troisième est une union pouvant contenir un Int ou un Float. Les derniers sont respectivement un type liste d'entier et arbre binaire d'entier. Le système de types permet de considérer des objets plus proche des données représentée, et de s'abstraire de l'implémentation.

Remarquez comme l'utilisation des constructeurs permet de savoir immédiatement si l'union de type LaValeur contient un entier ou bien un nombre flottant. En C/C++, il nous aurait fallut placer notre union dans une structure avec un champ indiquant quel constructeur a été utilisé. Il nous aurait aussi fallut maintenir "à la main" la cohésion entre ce champ et ce qui est stocké.

Donnons une correspondance C++ des deux derniers exemples dans leur version "polymorphique", où Liste et Arbre deviennent des constructeurs de type, et prennent donc en paramètre le type qu'ils doivent contenir.

data Liste a = Element a Liste | Vide
data Arbre a = Noeud a Arbre Arbre | Vide

type ListeEntier = Liste Int
type ArbreEntier = Arbre Int

L'équivalent C++ :

template <class T>
struct Liste
{
union
{
struct Element
{
T value;
struct List *next;
}  firstConstructor;
struct Vide
{} secondConstructor;
};
};

template <class T>
struct Arbre
{
union
{
struct Noeud
{
T value;
struct Arbre *left;
struct Arbre *right;
}  firstConstructor;
struct Vide
{} secondConstructor;
};
};

Un petit exemple d'utilisation :

personnage = ConstructeurDePersonne "Dent" "Arthur" 42
estCeVrai = Oui
valeur = Entier 42
uneListe = Element 1 ( Element 2 ( Element 3 ( Element 4 Vide ) ) )
racine = Noeud 4 (Noeud 2 Vide Vide) (Noeud 6 Vide Vide)

II.D - Pattern matching.

Si l'on peut construire des types, on peut aussi les détruire, où plus exactement, les dé-construire. Partant d'un objet de type liste, on veux récupérer le première élément, si la liste n'est pas vide. Cela se fait en faisant "matcher" un pattern sur l'instance d'un type :

-- Quelque exemples où le premier argument des fonctions est dé-construit.

obtenirNom (ConstructeurDePersonne nom _ _) = nom

obtenirPrenom (ConstructeurDePersonne _ prenom _) =  prenom

obtenirID (ConstructeurDePersonne _ _ id) = id

recupererValeur (Entier v) = v

-- Un exemple plus réaliste, où l'on veux des implémentations différente celons
-- ce que le premier argument contient.

premierElement (Element v sousListe) = v
premierElement Empty = 0

Il est très important que les pattern écrit soient exhaustifs. C'est à dire que tous les cas qui peuvent se produire doivent avoir une implémentations. Si ce n'est pas le cas, et que vous avez activé les warnings à la compilation, GHC vous préviendra. Si vous avez compiler avec des patterns non exhaustif, et que lors de l'exécution il se trouve que vous appelez votre fonction avec un pattern dont aucun motif ne correspond, vous aurez un très élégant crash avec un "non exhaustive patterns".

Il est aussi possible de 'pattern-matcher' dans le corps d'une fonction. Cela se fait avec un 'case of' :

premierElement' arg = 23 + case arg of
(Element v sousListe) -> v
premierElement Empty  -> 0

Il est aussi possible de dé-construire un objet au milieu d'une fonction avec l'opérateur let. On utilisera cette syntaxe quand il n'y a qu'un motif 'toujours vrais' (on parle de motif irréfutable).

recupererValeur' truc = let (Entier v) = truc in v

Le caractère ' est un caractère valide comme un autre pour un nom de fonction/variable (en fait, en haskell, il n'y a pas de variable au sens usuel).

Quand on type commence a avoir plus de trois valeur, il vaut mieux utiliser une "reccord syntax". On pourra consulter le chapitre de Learn You a Haskell sur les types algébriques.

Vous vous demandez peut-etre comment effectuer quelque chose de similaire en C++? Un façon envisageable est proposée ci dessous, utilisant un équivalent aux types algébriques nécessitant de tout faire à la main (énorme source d'erreurs, inutilisable en pratique).

data UnType = Nombre Int | Chaine String | SuperNombre Int

--

case untype of
Nombre v      -> -- ...
SuperNombre v -> -- ...
Chaine v      -> -- ...

struct UnType
{
//Équivalent des constructeurs haskell
static UnType Nombre(int v)
{
UnType untype;
untype.c = c1;
untype.v.num = v;
return untype;
}
static UnType SuperNombre(int v)
{
UnType untype;
untype.c = c3;
untype.v.num = v;
return untype;
}
static UnType Chaine(const char* v)
{
UnType untype;
untype.c = c2;
untype.v.string = v;
return untype;
}

enum constructeurs
{
// Nombre int
c1,
// Chaine const char*
c2,
// SuperNombre int
c3
} c;

union
{
int num;
const char *string;
} v;
}

//On construit
UnType untype = UnType::Nombe(42);

// On """patern match""" à la main :
switch(untype.c)
{
case UnType::c1:
//...
break;
case UnType::c2:
//...
break;
case UnType::c3:
//...
break;
}

III - Foncteurs.

III.A - 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. Bref, trêve de bavardages et de suppositions fumeuses.

De tels listes peuvent exister grâce au caractère paresseux de haskel : tant que vous n'avez pas besoin de la valeur situer à la xième position, alors toute la portion (infinie) de la liste qui lui succède ne sera ni évaluée, ni présente en mémoire, ni parcourue.

Comment faire de telles listes? Par récursion ou par compréhension. 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.

Commençons par des liste en compréhension finies :

-- "x <- l" signifie "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 (monades) ne sera aborder que dans la troisième partie. On prendra donc notre mal en patience.

Pour en revenir a nos listes en compréhension infinie, on peut penser à "l'ensemble des entiers qui sont paire" ou. 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".
-- La fonction even :: Int -> Bool indique si un nombre est paire.

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]
liste_des_entiers_paires'' = [x | x <- [1..], even x]

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

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 ce 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, on évalue "1 :" et connais donc le premier élément. Pour avoir le second, (map (1+) entiers). On 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. On obtient donc (1+)(1) = 2. puis, pour avoir le troisième élément, on 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 (le hello world de la programmation fonctionnelle), 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: <vos données>\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 faire ça différemment :

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 sera utilisée.

III.B - 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 chaîne 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], du Either a c en Either b c, 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 (qui est dictée par le type).

Cette affirmation n'est plus vrai quand on travaille dans des monades comme IO où le type n'indique pas beaucoup plus que "Il vas se passer quelque chose".

C'est à dire que l'on dispose d'un nombre important de façon élémentaires 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.

- Résoudre le puzzle des types. Par exemple pour combiner un (a -> b) avec [[a]] pour produire un [b], il faut penser à ((.).(.)) (concat $) (fmap . fmap).

Si l'on sais exactement de quels donnés l'on part, et quels donnés on doit 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 transformer une image en une chaîne de caractère. Pour peu 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 appliqué au c++ conduit facilement à un code catastrophique, en haskell c'est très certainement l'une des routes les plus sur. Le système de types et de classes de type rendent cette approche encore plus efficace.

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 valeurs. 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 une famille de type pour les quels on dispose d'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. C'est donc très différent 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 a Haskell) :

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 parlera de foncteurs, foncteurs applicatifs ou monades, on parlera de type qui sont instances respectivement de Functor (Prelude.Functor), de Applicative (Control.Applicative) et de Monad (Control.Monad).

III.C - Les foncteurs.

Les foncteurs (à nouveau, le terme est à prendre au sens de 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 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 et , il existes une ensemble d'applications de . 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 .

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

1) Si est un élément de , 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 et sont deux flèches (respectivement de dans et de dans ), alors la composé est une flèche de dans . 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 d'une catégorie vers une catégorie est :

1) Pour chaque semble de , un ensemble de qu'on noteras .

2) Pour chaque flèche entre des ensembles de , une flèche qu'on noteras .

3) Il faut que et que . C'est à dire que composer des flèches avant transformation est la même chose que les composer après, et l'identité (flèche qui ne fait rien) est bien envoyer sur l'identité .

Un foncteur est donc une façon de transformer une catégorie en une partie (sous-catégorie) de .

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).

Ici, ce qui nous intéresse sont les foncteurs de dans (on dit des endofoncteurs). À partir de maintenant, on ne considère plus que la catégorie des types haskell. Un foncteur Fonc, en haskell, est un foncteur de dans . 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 signifie 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 vers . 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 mapper 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 chaînes 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)
</paragraph>
<paragraph>
-- 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 suffira 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 ité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 le fonctionnement des foncteurs pour la suite. La dernière partie ne traitera 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".

IV - Foncteurs applicatifs.

Les foncteurs applicatifs sont un enrichissement des foncteurs. C'est donc une classe, définie dans le module Control.Applicative, de la façon suivante :

class (Functor f) => Applicative f where
pure  :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b

Avec un type fonctoriel Fonc, on pouvais :

- Prendre un élément de type c et le transformer en Fonc c, c'est à dire le "placer dans un contexte minimal".

- Prendre une fonction de type a->b et la transformer en une fonction de type Fonc a -> Fonc b grâce à fmap.

Grâce à un foncteur applicatif, on peut :

- Prendre un élément de type c et le transformer en type Fonc c, cela se fait grâce à la fonction pure :: (Applicative f) => c -> f c.

- Prendre une fonction dans un foncteur (ie un élément de type Fonc (a->b)) et l'appliquer à un élément de type Fonc a pour produire un Fonc b. L'opérateur permettant une telle chose est noté <*> :: (Applicative f) => f (a -> b) -> f a -> f b.

La seconde notion est plus puissante, car si vous avez un constructeur de type Fonc qui est une instance de Applicative (La classe des foncteurs applicatifs), alors c'est un foncteur de la façon suivante :

instance Functor Fonc where
fmap f e = (pure f) <*> e

C'est à dire : Prenez f une fonction de type a -> b, alors vous savez comment l'appliquer sur un Fonc a. Il suffit de la "placer" elle aussi dans un foncteur, pour se retrouver avec une "fonction dans un contexte" de type Fonc (a->b) à appliquer sur un "élément dans un contexte" de type F a.

C'est donc pour cela que l'on impose à tout foncteur applicatif d'être d'abord une instance de Functor, et que vous avez la contraire "Functor f" dans la définition de la classe applicative.

IV.A - On se prépare au grand saut avec maybe.

Tout ceci est très abstrait, alors regardons ce que cela donne avec un exemple simple. On considère Maybe qui est une instance de Applicative de la façon suivante :

instance Applicative Maybe where
pure = Just
(Just f) <*> (Just x) = Just (f x)
_        <*> _        = Nothing

La méthode pure prend un truc :: a et le place dans un Maybe a par Just truc. C'est la façon la plus intuitive de placer notre truc dans un Maybe, sans perdre d'information. L'opérateur <*> se contente lui de récupérer la fonction à sa gauche, la valeur à sa droite, d'effectuer le calcul (l'application de f à x) puis de placer le résultat dans un contexte minimal en utilisant le constructeur Just. La dernière ligne s occupe des cas où il manque la fonction, l'argument, ou bien les deux. Dans ces trois cas, on ne peut effectuer le calcul, et l'on ne peut donc produire de résultat.

Comme dit plus haut, si l'on vais une fonction qui prend la racine carré (sqrt :: Int) d'un entier, et "peut-être un nombre" (un v :: Maybe Int), on pouvais mapper notre fonction avec la ligne fmap sqrt v. Avec un foncteur applicatif, on peut aussi écrire :

resultat = (pure sqrt) <*> v

Mais alors, quel est l intérêt des foncteurs applicatifs? Regardons l'application d'une fonction prenant trois entier à trois "peut-être un entier".

--Ici, v1, v2 et v3 sont de type Maybe Int.
--Si vous voulez savoir d'où il viennent, disons que ce sont le résultat
--de la lecture d'une chaîne de caractère et de tentative de conversion de
--la chaîne en nombres. Si c'était possible, alors on a des valeurs de la forme "Just 42".
--Sinon, on aura "Nothing".

--On a une superbe fonction :
deepThought :: Int -> Int -> Int -> Answer

--Et on veut l'appliquer à v1, v2, v3.
--Si l'on essaye avec un foncteur :
premiereApplication :: Maybe (Int->Int->Answer)
premiereApplication = fmap deepThought v1

--Maintenant, on est bloquer, on ne sais pas appliquer
-- une fonction qui se trouve dans un maybe...
--... à moins d'utiliser <*> :)
secondeApplication :: Maybe (Int -> Answer)
secondeApplication = premiereApplication <*> v2
derniereApplication :: Maybe Answer
derniereApplication = secondeApplication <*> v3

--En fait, on aurait pu d'abord placer la fonction dans un Just,
-- puis appliquer v1, v2 et v3 avec <*> :
toutEnUn :: Maybe Answer
toutEnUn = (pure deepThought) <*> v1 <*> v2 <*> v3

--Et pour finir, sachez qu'il existe un petit sucre syntaxique
-- pour "(pure f) <*> x" ; l'opérateur <$> :
toutEnUn :: Maybe Answer
toutEnUn' = deepThought <$> v1 <*> v2 <*> v3

Mais parce que le haskell recèle encore bien des surprises, intéressons nous à une autre instance de Applicative : Les listes.

IV.B - Premier plongeon avec les listes.

Comme nous l'avions vu la dernière fois, les listes sont un excellent exemple de foncteur. Mais pouvons nous en faire des foncteurs applicatifs? Il est facile de placer une valeur dans un contexte minimal : on définira pure a = [a]. En fait, il nous faudrait répondre à la question suivante : Si l'on a une liste de fonction [f1, f2, f3] et de valeurs [2, 3, 4], comment définir l'opérateur <*> ?

La solution retenue par haskell est on ne peut plus simple : on applique toutes les fonctions à toutes les valeurs. Voici la définition de l'instance :

instance Applicative [] where
pure x = [x]
fs <*> xs = [f x | f <- fs, x <- xs]

Cela donne une façon très facile d'effectuer de nombreux calculs différents. C'est à dire : Vous disposez d'un ensemble de valeurs, et d'un ensemble de fonctions. Vous voulez connaître TOUS les résultats possibles. Il suffit alors d'appliquer la liste des fonctions sur la liste des valeurs avec l'opérateur <*>. Un exemple, en partie tiré de Learn You Haskell for Great Good est le parcoure d'un cavalier. Un cavalier est situé quelque part sur un échiquier infini, et vous voulez connaître toute les positions où il peut se trouver après 5 coups. Il suffit décrire une fonction par déplacement possible et de les placer dans une liste, disons [u1, u2, l1, l2, r1, r2, d1, d2] et d'appliquer cette liste à la position d'origine dans un contexte [(x, y) ou encore pure (x, y). La solution est donné par :

u1 (l, c) = (l+2,c+1)
u2 (l, c) = (l+2,c-1)
d1 (l, c) = (l-2,c+1)
d2 (l, c) = (l-2,c-1)
l1 (l, c) = (l+1,c-2)
l2 (l, c) = (l-1,c-2)
r1 (l, c) = (l+1,c+2)
r2 (l, c) = (l-1,c+2)

fctListe = [u1, u2, d1, d2, l1, l2, r1, r2]
origine (l, c) = [(l,c)]

etapeSuivante position = fctListe <*> position

solution (l, c) = etapeSuivante . etapeSuivante . etapeSuivante . etapeSuivante . etapeSuivante $ origine (l, c)

IV.C - En apnée : les foncteurs (->) r !

On les avais cacher lors de la discussion des foncteurs, car ils sont difficile à cerner, leur intérêt n'est pas évident au premier abord, et leur construction est quelque peu... surprenante. Mais puisqu'ils sont utile comme foncteur applicatif, parlons en! Si la partie la plus abstraite vous échappe, aucune raison de vous inquiéter, l'idée est de survoler les notions pour avoir un aperçu, éveiller la curiosité et peut être vous inciter à lire des livres/articles dédiés. Si tout cela vous intéresse, sautez à la section "Foncteurs applicatifs" de Learn You a Haskell.

L'opérateur -> est un constructeur de type, à deux arguments. Vous lui donnez deux types, a et b, et il vous construiras le type "prend du a et retourne du b". On peut donc écrire f :: a -> b ou encore f :: (->) a b. Que signifie alors (->) r ? Cela signifie que l'on parle d'un constructeur de type à un argument, et que si vous lui donnez un type a, il désigneras alors les fonctions de type a -> r Si r désigne un type, on peut alors faire de (->) r une instance de functor où mapper une fonction de type a->b signifie l'appliquer au résultat de l'évaluation de la fonction de type (-> r a. Plus précisément :

instance Functor ((->) r) where
fmap f g = (\x -> f (g x))

L'intérêt peux sembler limiter, puisque (fmap f g) 42 se simplifie en f . g $ 42 qui est bien plus lisible. Outre sa fantastique capacité à mettre votre esprit à rude épreuve, ce changement de point de vue devient très intéressant avec la classe applicative, puisqu'il donne la possibilité d'avoir un ensemble de paramètres.

Un exemple commenté :

--Notre type "paramètre". On aurais pu construire une sorte de grosse structure
-- avec diverses informations.
--Dans cette example, on se contenteras d'un nombre.
type Param = Int

unEntier :: Param -> Int
unEntier = pure 5

unAutreEntier :: Param -> Int
unAutreEntier param = 5 + param

uneFonction :: Param -> Int - > String
uneFonction param arg = show (arg + param)

somme = pure (+) <$> unEntier <*> unAutreEntier
affichage = uneFonction <*> somme

--Vaut 94 :
evaluationDansUnCOntexte = affichage 42

IV.D - Quelques règles que null ne doit ignorer.

Comme on dit, dura lex, sed lex. Les foncteurs devaient respecter certaines règles, et il en est de même des foncteurs applicatifs. Une fois habitué aux foncteurs applicatifs, ces règles semblent découler du bon sens. Ce sont des invariants que doivent respecter vos instances d'Applicative. Si vous ne les respectez pas, c'est que ce que vous voulez faire n'est pas un foncteur applicatif, et n'a donc aucune raison d être instance d'Applicative.

Sans trop rentrer dans les détails, les voici, brièvement commentés :

-- Neutre :
pure id <*> v = v
--Cela signifie qu'appliquer la fonction identité
-- (id = (\x -> x) ) a un élément v via <*> le laisse inchangé.
--C'est une sorte de "neutre à gauche".

-- Composition :
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
--Cela signifie que composer les fonctions à l'intérieur de u et v
-- via l'opérateur .  (C'est la partie pure (.) <*> u <*> v) revient à calculer u sur le résultat de v.
--Comme on compare deux fonctions sur leur valeur, et que l'on parle de résultat, on doit introduire
-- un certain mister w, et on vérifie que quelque soit ce w, on a bien que u calculer sur v calculé sur w donne bien le même résultat que la composé (pure (.) <*> u <*> v) calculé sur w.

-- Morphisme :
pure f <*> pure x = pure (f x)
--Cette égalité garanti que : placer f dans un contexte minimal, placer x dans un contexte
-- minimal, puis "mouliner" donne le même résultat que f x placé dans un contexte minimal. En quelque sorte,
-- on transforme l'opérateur $ :: (a->b) -> a -> b en l'opérateur <*> :: f (a->b) -> f a -> f b.

-- ' Échange '
u <*> pure y = pure ($ y) <*> u

-- C'est une sorte de commutativité du pauvre. On ne peut pas vraiment échanger les arguments à droite et à gauche, car l'un est une fonction, l'autre une valeur. Mais on peut transformer une évaluation "f y" en "$ f y ", ce qui permet de changer l'ordre des arguments.

V - Monades.

Les monades, c'est avoir un pied sur la terre, et un pied dans la mer. On ne veut plus seulement mapper des fonctions f: a -> b à l'intérieur d'un Fonc a, ni évaluer des fonctions Fonc (a -> b) dans un contexte F a. Maintenant, on dispose de fonctions qui travaillent sur une valeur, et produisent un résultat dans un contexte. Des fonctions e type f :: a -> Fonc b. Si l'on essayais de les mapper comme des foncteurs sur un Fonc a, on se retrouverais avec du Fonc (Fonc b), et ce n'est pas du tout ce que l'on veut. Il nous faut donc une fonction capable de recoller ces "Fonc Fonc" en "Fonc". C'est ce que fournissent les monades.

Tout de suite, la classe monade :

class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
-- On l'appelle aussi "bind"

(>>) :: m a -> m b -> m b
-- C'est une sorte d'opérateur de concaténation.
-- >> Ignore le premier argument et renvoi la valeur du second.
-- En fait, c'est très utile, avec la monade IO, où cela permet de demander
-- l'execution de deux programmes "l'un apprès l'autre".

return :: a -> m a
-- C'est notre bon vieux pure, sous un autre nom.

fail :: String -> m a
-- On ne l'utilisera pas, et on en parleras pas.
-- Sachez toute fois que ca renvoi moralement un "contexte sans information".
-- Par exemple une liste vide, un Nothing, etc.
-- Le soucis, c'est que bien souvent, cette fonction n'est pas implémenté.
-- La raison de son existence est essentiellement historique.

join :: m m a -> m a
-- Elle "comprime" un élément qui est dans "un contexte dans un contexte" en un élément dans un contexte.
-- Par exemple, un "Just (Just 3)" devient un "Just 3".

Les deux opérateurs principaux sont bind et return, ou bien join et return. L'opérateur join peux s'écrire avec bind, et l'opérateur bind peux s'écrire avec join. Haskell fournis une implémentation par défaut de chacun d'eux, si bien que nous avons besoin de n'en définir qu'un. À titre purement indicatif, voici join et bind :

join :: m m a -> m a
join mma = mma >>= (\ma -> ma)

(>>=) :: m a -> (a -> m b) -> m b
(>>=) ma f = join $ fmap f ma

Voyons comment on pourrait, partant d'une monade, la faire instance d'Applicative :

instance Monade Fonc where
pure = return
-- L'astuce est de construire une fonction f' :: (a -> m b) que l'on puisse utiliser à la place de f.
-- On la construit grâce à "pure . f".
-- Mais comme f est elle même dans un contexte, il faut faire cette transformation dans le contexte.
mf (<*>) mv = mf >>= (\f -> mv >>= return . f)
-- On donne mf à manger a la grande expression de droite. La grande expression de droite récupère la fonction f, la transforme en une f' par <i>return . f</i>. On donne donc la valeur v contenue dans mv à manger a la fonction f' grâce à >>=.

Si vous avez parfaitement tout saisit jusque là, soit vous connaissez déjà le haskell ou avez beaucoup travaillé avec des langages fonctionnels, soit vous êtes des sur-hommes. Voyons donc en pratique ce qu'apportent les monades, et pourquoi est-ce que bien utilisées, elles offrent une nouvelle façon de résoudre certains problèmes bien connus du monde impératif.

V.A - Être ou ne pas être?

Dans un "vrai" programme, on n'a pas toujours une valeur a retourner pour une fonction. Que faire si l'on demande le premier élément d'une liste vide? Et si jamais on veut convertir une chaîne en un nombre, qui par malheur n'est pas un nombre? En bref, comment gérer une erreur correspondant à l absence d'un résultat?

Une réponse est la monade maybe. Commençons par des fonctions qui renvoient peut-être une valeur :

maybeHead :: [a] -> Maybe a
maybeHead [] = Nothing
maybeHead (head : tail) = Just head

maybeList :: (Int, Int) -> Maybe [Int]
maybeList (first, last) = if first <= last then [first..last] else Nothing

maybeRange :: Bool -> Maybe (Int, Int)
maybeRange False = Nothing
maybeRange True = (23, 42)

On voudrais maintenant récupérer le premier élément de la liste pour les valeur donné par maybeRange, si la liste existe, bien sure. C'est la que les monades interviennent! Grâce au monades, on peut composer les deux fonctions, bien qu'un Maybe [Int] ne soit pas un [Int].

resultat :: Maybe Int
resultat choice = maybeRange choice >>= maybeList >>= maybeHead

Si l'une des étapes ne produit pas de résultat (un Nothing), alors l absence de résultat seras propagé et on obtiendras un Nothing.

Cette méthode a de nombreux avantages par rapport aux deux solutions très connues suivantes :

1) Le "code d'erreur", c'est à dire placer nullptr quand on pointeur n'existe pas, ou encore "-1" ou 0 pour signaler une erreur. L'inconvénient de cette méthode est d'obliger le développeur à vérifier chacune des valeurs de retour avec un if, généralement pour sortir de la fonction, souvent en retournant un nouveau code d erreur pour signaler que le résultat produit n'est pas "vraiment" un résultat, mais une absence de résultat.

L'utilisation de la monade Maybe permet d'éviter ces testes répété. Si une seul des fonctions ne peut pas fournir de résultat, alors les applications suivantes seront toute ignoré et, bien entendu, ces fonctions ne seront pas évaluées, donc pas de cout en temps de calcul.

2) Les exceptions. Cela consiste à interrompre l'exécution normale du programme pour remonter a travers toute la pile d'appels, en espérant que quelqu'un seras assez gentil pour s'occuper de cette erreur. Cela a un cout en terme de performances, et doit être réserver pour les évènements exceptionnels. L'impossibilité de produire un résultat est rarement exceptionnel, c'est plutôt chose commune.

Le chaînage de monade Maybe a l'avantage de ne pas déclencher un erreurs qui pourrait se perdre et aller jusqu'à interrompre le programme. Que les valeurs soient présente ou non, le comportement est toujours "simple" à prédire. Et plus un code est simple, moins il y a de risque qu'une erreurs s'introduisse.

En règle générale, dès que le résultat peut ne pas être fournit, vous pouvez utiliser la monade Maybe. Si parfois une certaine fonction f que vous voulez chaîner produit toujours un résultat, alors vous pouvez la placer au milieu d'une chaîne de >>= en écrivant return . f. Vous pouvez aussi une fmap, car toute les monades sont des foncteurs.

Nb : Peut-être avez vous besoin de conserver une information sur l'origine de l'erreur. Ceci est possible grâce à la monade Either.

Pour finir, voici l'instance de cette monade :

instance Monad Maybe where
return x = Just x
Nothing >>= f = Nothing
Just x >>= f  = f x
fail _ = Nothing

V.B - Un calcul pas très déterministe.

Nous avions vu comment les listes comme foncteurs applicatifs permettent de résoudre élégamment la question du déplacement d'un cavalier. Mais dans un échiquier fini, on ne savais pas trop comment gérer les bords. Revenons sur ce problème.

Les listes, vu comme monade, nous permettent de combiner des fonctions de type a -> [b]. L'idée est que vous disposez de diverse fonctions qui prennent une valeur, et produise divers résultats possible. Vous voulez alors appliquer des fonctions sur chacun de ces résultats. On peut donc parler de calcul non-déterministe : une valeur donne plusieurs résultats possible.

On peut donc réaliser un remake du cavalier, en se servant de ce calcul non déterministe, partant du fait que depuis une position, on a un certain nombre variable de positions possibles.

--Quelques types pour plus de lisibilité,
-- histoire de rappeler que les types sont
-- aussi là pour fournir des informations sémantiques.
type Ligne = Int
type Collone = Int
type Position = (Ligne, Collone)

--Fonction utilisé pour ne garder que les positions dans l'échiquier
dansLechiquier :: Position -> Bool
dansLechiquier (l, c) = l `elem` [1..8] && c `elem` [1..8]

--Produit une liste des positions possibles
deplacerCavalier :: Position -> [Position]
deplacerCavalier (l, c) = filter dansLechiquier liste
where liste = [(l+2,c-1),(l+2,c+1),(l-2,c-1),(l-2,c+1)
,(l+1,c-2),(l+1,c+2),(l-1,c-2),(l-1,c+2)]

--Donne la liste des positions possible du cavalier, partant de (4, 5), et après trois déplacements.
resultat = return (4, 5) >>= deplacerCavalier >>= deplacerCavalier >>= deplacerCavalier

En fait, une autre façon de faire serais de mapper la fonction deplacerCavalier dans la liste de positions, produisant un "[[Position]]", puis d'appeler concat sur cette liste, la recollant en une "[Position]". C'est d'ailleurs se que fait l'opérateur >>= !

L'utilisation des listes sous leur forme de monade n'est pas limité à cette exemple. Je peux mentionner un exemple qui vous paraîtras peut-être moins académique. Disons que vous voulez enregistrer une image, et que vous disposez d'une fonction qui vous donne les couleurs r, g, b, a sous la forme d'une liste de nombres, c'est à dire getPixel (x, y) :: [Word8] (Word8 est un nombre codé sur 8 bits). Sachant que pour enregistrer l'image, vous devez fournir un tableau, qui peut être très facilement construit à partir de la liste des valeurs qu'il vas contenir. (Le compilateur (ghc) est très malins, et le programme compilé ne s'amusera pas à produire une liste, la construire en mémoire, puis la placer dans le tableau.) La monade [] permettent d'écrire en une ligne, de façon très élégante, la création d'un tableau où les valeurs sont bien la succession des valeurs de getPixel calculé à chaque coordonné. Bien-sur, on aurais pu utiliser concat et map, puisque c'est justement ce que fait l'opérateur bind. Tout ça pour dire que les listes vue comme monade ne sont pas un gadget, mais bien un outil.

Voici la définition de l'instance pour les curieux :

instance Monad [] where
return x = [x]
xs >>= f = concat (map f xs)
fail _ = []

V.C - La notation do.

La notation do est un sucre syntaxique. Seulement, les monades sont tellement amère que vous aurez vraiment besoin de ce sucre, je vous l'assure. La notation do permet décrire facilement le chaînage d'actions, et le fait de récupérer des valeurs dans un contexte.

Considérons l'exemple suivant tiré de Learn You a Haskell :

foo :: Maybe String
foo = Just 3   >>= (\x ->
Just "!" >>= (\y ->
Just (show x ++ y)))

On récupère deux valeurs de monades à travers x et y, puis l'on place le résultat de show x ++ y dans un contexte. C'est lourd a écrire, demande l'imbrication de fonctions... Avec la notation do, cela revient à :

foo :: Maybe String
foo = do
x <- Just 3
y <- Just "!"
Just (show x ++ y)

-- Ou encore :
foo :: Maybe String
foo = do
x <- Just 3
y <- Just "!"
return (show x ++ y)

Dans les deux premières lignes, on récupère x et y depuis Just 3 et Just "!", puis on fait notre traitement.

Mais ça ressemble a des listes en compréhension tout ça! Revoyons l'exemple précédent avec des listes :

foo :: Maybe String
foo = [1, 2, 3]   >>= (\x ->
[".", "!", "?"] >>= (\y ->
[show x ++ y]))

Le résultat produit est toute les façons de coller l'un des signes de ponctuations après l'un des nombres. C'est exactement la même chose que :

foo :: Maybe String
foo = do
x <- [1, 2, 3]
y <- [".", "!", "?"]
return (show x ++ y)

-- Ou encore :
foo = [show x ++ y | x <- [1, 2, 3] | y <- [".", "!", "?"]]

Voilà donc l'explication des liste en compréhension! Et oui, il nous auras fallut arriver jusqu'ici pour pouvoir enfin dire ce qu'est une liste en compréhension. C'est simplement une notation spécifique au liste d'un bloque do. C'est donc de la manipulation de monade que vous faites à chaque fois que vous écrivez une liste en compréhension. Si c'est si pratique avec les listes, vous vous doutez bien que pouvoir le faire avec divers structures, comme des arbres, est tout aussi pratique.

Vous vous demandez alors comment ajouter les conditions, comme dans [x^2 | x <- [1..20], x `mod` 2 == 0] ? Et bien vous pouvez utilisez la fonction guard, qui produiras une liste vide si la condition n'est pas vérifiée :

foo = do
x <- [1..20]
guard (\x -> x `mod` 2 == 0)
return x^2

V.D - Le retour de (->) r

Nous avions utilisé le foncteur applicatif (->) r pour représenter des calculs qui dépendent d'un contexte. On savais donc appliquer des fonctions r -> (a->b) sur des valeurs r -> a. Seulement, il est plus commun de partir d'une valeur, et produire un résultat qui dépend du contexte. On voudrais donc une monade, pour pouvoir combiner des fonctions de type a -> (r -> b) (Les parenthèses sont là pour faire ressortir que l'on considère (->) r comme un foncteur/ une monade, mais bien-sur facultatives).

Comme (->) r est l'une des monades les plus abstraites, regardons un exemple concret, où le contexte est la position d'une caméra dans un raytracer.

--On définit une caméra.
--Une caméra contient la position depuis la quelle
-- les rayons sont lancé, la distance à la quel se trouve
-- le plan, et la taille de celui ci.
type Position = (Double, Double, Double)
type Direction = (Double, Double, Double)
type Distance = Double
type Coordonnee = Int
type Largeur = Coordonnee
type Hauteur = Coordonnee
type Plan = (Largeur, Hauteur)
data Camera = Camera Position Distance Plan

getRay :: Coordonnee -> (Camera -> Direction)
getRay (i, j) cam = let (Camera (x, y, z) _ _ _) = cam in normalize (i - x, j - y, -z)
where
normalize (x, y, z) = let norme = sqrt(x^2 + y^2 + z^2) in (x / norm, y / norm, z / norm)

rayTraceScene :: Scene -> Direction -> (Camera -> (Object, Distance))
rayTraceScene = -- Imaginons que l'on fait le nécessaire pour raytracer une scène.

computeColor :: (Object, Distance) -> Camera -> [Word8]
computeColor = -- Calcule la couleur en tenant compte de l'angle de la caméra, etc.

--Pour getPixel, on préférera souvent spécialiser d'abord la Caméra,
-- puis appeler cette spécialisation sur toute les coordonnées de l'image.
-- C'est pourquoi le type est "Camera -> Coordonnee -> [Word8]" plutôt
-- que "Coordonnee -> Camera -> [Word8]". On perd donc la possibilité
-- d'utiliser getPixel avec la monade "(->) Camera".
getPixel :: Camera -> Coordonnee -> [Word8])
getPixel cam coords = (return coords >>= getRay >>= (rayTraceScene uneScene) >>= computeColor) cam

V.E - Point culture

Comprenez bien que les monades ne sont pas indispensable, et que l'on faisait des monade avant la création de la classe Monade. C'est simplement de nouveaux outils à votre disposition pour résoudre des problèmes, et ils permettent parfois de résoudre certains problèmes de façon très élégante et concise (ce qui est un excellent point pour l'évolutivité du code).

Sachez que les monades aussi doivent respecter certaines règles, tous comme les foncteurs et les foncteurs applicatifs. Cela assure qu'une monade seras bien un foncteur (applicatif), de la façon décrite plus haut. Les voici :

-- Neutre à gauche
return a >>= f = f a
-- Neutre à droite
m >>= return = m
-- Associativité
(m >>= f) >>= g = m >>= (\x -> f x >>= g)

Vous trouverez des liens dans les références pour plus de détails.

On n'a pas aborder la monade IO. Cette monade permet de ramener les actions propre a l'impératif, les "effets de bord", dans le langage haskell. L'astuce diabolique est la suivante : Puisque qu'un programme haskell ne peut produire d'effet de bord, un programme haskell décriras comment composer, juxtaposer, et transformer les résultats produits par des programmes à effets de bord. Utiliser la monade IO, c'est jouer avec la composition et la juxtaposition de programmes. C'est alors que l'opérateur ">>" prend tout son sens! Il permet de juxtaposer deux programmes impératifs et ne retenir le résultat que du second, par exemple :

afficherMessage = putStrLn "Bonjour," >> putStrLn "monde!"

En dire plus sur cette monade n'a d'intérêt que pour les personne voulant écrire des programmes en haskell. Si c'est votre cas, je vous invite à lire, au choix, Learn You a Haskell for Great Good ou (plus technique et plus ... "professionnel") Real World Haskell, chez O'Reilly.

VI - Références :

- Plus sur les foncteurs applicatifs : Applicative Programming with Effects

- Quelques détails sur les constructeurs : http://www.haskell.org/haskellwiki/Constructor

- Catégories : http://fr.wikipedia.org/wiki/Théorie_des_catégories

- Foncteurs : http://fr.wikipedia.org/wiki/Foncteur

- Apprendre Haskell vous fera le plus grand bien : http://lyah.haskell.fr/ ou http://learnyouahaskell.com/

- Real World Haskell : http://book.realworldhaskell.org/read/

- Haskell "kind" : http://www.haskell.org/haskellwiki/Kind (type :k Maybe and :k Bool on GHCI)

- La classe functor : http://en.wikibooks.org/wiki/Haskell/The_Functor_class

- Une video de haskell pour google code jam : youtube

- La loi des monades : http://www.haskell.org/haskellwiki/Monad_laws

- Either - http://hackage.haskell.org/packages/archive/category-extras/0.53.1/doc/html/Control-Monad-Either.html

- Hoogle (moteur de recherche, très efficace pour rechercher une fonction à partir de son type) - http://www.haskell.org/hoogle/

Un bref aperçu de haskell

Auteur

Cochoy Jérémy