Le Haskell, un langage au label pure. PremiĂšre partie.

Mauvais jeux de mots mit Ă  part, ce trĂšs court et succin billet (vous me voyez venir) va traiter du haskell. Haskell, de monsieur Haskell Brook Curry, un monsieur trĂšs Ă©picĂ©, est un langage fonctionnel. Comme beaucoup de langages fonctionnel, cela reprĂ©sente un choque culturel que de les apprĂ©hender. Mais le haskell semble avoir un petit quelque chose que n’ont pas les autres langages fonctionnels. À travers les trois prochains billets, j’espĂšre vous convaincre que, si un jour, dans votre vie, vous avez l’occasion de creuser un language fonctionnel, alors vous devriez creuser le haskell.

La seconde partie est disponible ici.

On y vas tout en douceur. Curryfication et typage, pour ceux qui n’ont pas dĂ©jĂ  dĂ©couvert les joies (les dolipranes?) 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 du haskell, 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 et de parallĂ©lisation des calculs en haskell (avec un VRAI exemple!). Enfin, apogĂ©e, moment de transe et de plaisir inĂ©gale, on abordera la huitiĂšme merveille du monde : les monades.

Ce que tout le monde sais dĂ©jà
 ou pas.

Faisons un petit 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.

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 est trĂšs simple 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. (Et oui, puisque Ă©crire mult a b signifie alors ((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, nouvelle_fonction = mult 42 correspond Ă  fixer la premiĂšre valeur de la fonction mul Ă  42.

En C++, il faudrais Ă©crire

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

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 aurais 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 petites fonctions bien pratique pour manipuler des fonctions ; l’identitĂ© et la composition :

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

On peut alors composer la multiplication par 2 et l’addition à 3 :

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

Enfin, on aurais pu Ă©crire :

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

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 que l’on appellera f, une liste de a, et produit une liste de b. Le bon sens veux que cette fonction applique f Ă  chaque Ă©lĂ©ment de la liste de a, pour produire une liste de 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 pour n’en produire plus qu’une.

Voyez tout ce qu’on peut deviner sur le comportement d’une fonction grñce aux types.

Pour éviter les noms à rallonge, on peu aussi construire des alias de type. 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

Grùce à ces alias, vous avez une idée claire du comportement de la fonction getSomeone simplement en lisant son type.

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 :

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

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, et 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.

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)

Patern matching

Si l’on peut construire des types, on peut aussi les dĂ©truire, oĂč plus prĂ©cisĂ©ment, les dĂšs-construire. Partant d’un objet de type liste, on peut vouloir 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 :

obtenirNom (ConstructeurDePersonne nom _ _) = nom

obtenirPrenom (ConstructeurDePersonne _ prenom _) =  prenom

obtenirID (ConstructeurDePersonne _ _ id) = id

recupererValeur (Entier v) = v

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

Il est aussi possible de dĂ©construire un objet au milieu d’une fonction, sous rĂ©serve d’ĂȘtre certain que l’objet respecte le pattern spĂ©cifiĂ© :

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

Nb : Le caractùre ‘ est un caractùre valide comme un autre pour un nom de fonction ou de variable (bien qu’en fait, en haskell, il n’existe pas de variable au sens usuel).

Voilà, ce seras tout pour aujourd’hui :)

Références :