IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Un bref aperçu de haskell


précédentsommairesuivant

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 :

 
Sélectionnez

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

Une fonction qui ajoute 42 à un entier :

 
Sélectionnez

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 :

 
Sélectionnez

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 :

 
Sélectionnez

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 :

 
Sélectionnez

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

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 :

 
Sélectionnez

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

 
Sélectionnez

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

 
Sélectionnez

-- Pour écrire une fonction "anonyme", qui prend trois arguments et renvoi 42, on peut écrire
-- (\x y z -> 42)
--  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 :

 
Sélectionnez

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 :

 
Sélectionnez

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

Enfin, on aurais pu écrire :

 
Sélectionnez

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 :

 
Sélectionnez

type String = [Char]

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

 
Sélectionnez

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

 
Sélectionnez

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.

 
Sélectionnez

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++ :

 
Sélectionnez

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 :

 
Sélectionnez

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 :

 
Sélectionnez


-- Quelque exemples  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,  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' :

 
Sélectionnez

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

 
Sélectionnez

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

 
Sélectionnez

        data UnType = Nombre Int | Chaine String | SuperNombre Int

        --

        case untype of
            Nombre v      -> -- ...
            SuperNombre v -> -- ...
            Chaine v      -> -- ...
      
 
Sélectionnez

        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;
        }
      

précédentsommairesuivant

  

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