Un bref aperçu de haskell

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.

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

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)

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