Premier contact avec Haskell

Environnement

Il existe plusieurs implémentations d’Haskell. Nous utiliserons la Plateforme Haskell qui contient, outre le compilateur GHC (Glasgow Haskell Compiler) et son interprète GHCi, une grande bibliothèque de fonctions, tout ceci accompagné d’une documentation très complète : /usr/share/doc/ghc-doc/html/index.html

Vous pourrez ainsi utiliser :

Les extensions usuelles dans le monde haskell sont :

Interprète GHCi

L’interprète GHCi effectue la boucle : lecture, évaluation et affichage d’expressions. Par défaut, chaque expression doit être écrite sur une seule ligne : dès que vous tapez « Entrée », GHCi évalue l’expression.

En plus des expressions, il propose une série de commandes, commençant par « : », notamment :

Pour chacune de ces commandes, les abréviations d’une seule lettre, par exemple :r, suffisent. Par ailleurs, GHCi permet l’édition de ligne comme on l’aime, en particulier :

En plus des commandes et des expressions, vous pouvez aussi utiliser let pour définir un nom :

Prelude> let a = 1+2
Prelude> a+3
6

Enfin, GHCi donne automatiquement le nom it à la dernière expression évaluée :

Prelude> 1+2
3
Prelude> it+3
6

Petit exemple de session

  1. Créez un petit fichier test.hs contenant le code suivant :

    puis lancez ghci :

    $ ghci
    GHCi, version 7.10.3: http://www.haskell.org/ghc/  :? for help
    Prelude> :l /tmp/test.hs
    [1 of 1] Compiling Main             ( /tmp/test.hs, interpreted )
    Ok, modules loaded: Main.
    *Main>

Prelude est le module chargé initialement. Main est le nom du module pour le code chargé depuis test.hs1.

ghci indique de la sorte quels sont les modules dont les noms peuvent être utilisés dans les expressions. Ainsi, vous pouvez évaluer somme 1234.

Listes

Les listes jouent un rôle fondamental en Haskell2. Le langage fournit notamment un peu de syntaxe pour les écrire et les manipuler élégamment.

Dans les extraits suivants, nous avons activé l’affichage des types des expressions évaluées par un

Prelude> :set +t

Au passage, vous pouvez créer un fichier ~/.ghci contenant cette simple ligne :

:set +t

pour que les types soient toujours affichés dans vos sessions GHCi.

Construction de listes

Haskell permet de manipuler des listes homogènes, c'est-à-dire constituées d’éléments ayant tous le même type.

Les listes sont des structures de données récursives définies à partir de deux constructeurs : [] pour la liste vide, et : pour l’adjonction d’un élément en tête de liste3.

Prelude> 1 : 2 : 3 : []
[1,2,3]
it :: Num a => [a]

Il est aussi possible de construire une liste par énumération de ses éléments sous la forme :

Prelude> [1, 2, 3]
[1,2,3]
it :: Num a => [a]

Il existe encore une autre notation, pour les listes de caractères, à savoir les chaînes (String est un alias pour le type [Char] en Haskell) :

Prelude> "abcdef"
"abcdef"
it :: [Char]
Prelude> ['a','b','c']
"abc"
it :: [Char]

Types listes

À la différence des n-uplets, les listes doivent être homogènes :

Prelude> [1, 'a', True]

<interactive>:36:10:
    Couldn't match expected type `Char' with actual type `Bool'
    In the expression: True
    In the expression: [1, 'a', True]

Gloups ! Autrement dit, en essayant de trouver le type de la liste, GHCi vérifie si 'a' (de type Char) et True (de type Bool) ont le même type. Comme ce n’est pas le cas, il donne l’expression dans laquelle l’erreur apparaît.

(On retrouve au passage le fait que GHCi aurait attribué le nom it pour la valeur de l’expression que l’on a donnée s’il avait réussi à l’interpréter.)

Le type d’une liste de valeurs de type τ est noté [τ] :

Prelude> [1, 2, 3]
[1,2,3]
it :: Num t => [t]
Prelude> [True, False]
[True,False]
it :: [Bool]
Prelude> [(1,2),(3,4)]
[(1,2),(3,4)]
it :: Num t => [(t, t)]

La liste vide peut être d’un type polymorphe si elle est construite avec le constructeur [] :

Prelude> []
[]
it :: [t]

ou d’un type instancié si elle est obtenue à partir d’une autre liste :

Prelude> tail [True]
[]
it :: [Bool]
Prelude> tail [1]
[]
it :: Num a => [a]
Prelude> tail "a"
""
it :: [Char]

Fonctions sur les listes

Le module standard de manipulation des listes est Data.List. Mais, comme nous l’avons dit, les listes jouent un rôle fondamental dans le langage. Du coup une grande partie des fonctions de ce module sont réexportées dans le Prelude. Vous trouverez ainsi dans la documentation du Prelude (à retrouver dans la liste des documentations de tous les modules des bibliothèques installées) une section « List operations ».

  1. Allez lire cette documentation.

Les fonctions dont les noms sont composés de symboles (++ la concaténation et !! la récupération du enième élément) sont utilisées en notation infixe :

Prelude> [True, False] !! 1
False
it :: Bool
Prelude> "abcdef" !! 3
'd'
it :: Char

Notez que la documentation indique des conditions d’utilisation pour certaines fonctions. En particulier, head ne peut être utilisée que sur une liste non-vide, sans quoi :

Prelude> head []
*** Exception: Prelude.head: empty list

Filtrage de motif sur les listes

Comme dit plus haut, les listes sont des structures de données récursives définies à partir de deux constructeurs : [] pour la liste vide, et : pour l’adjonction d’un élément en tête de liste. Les fonctions qui prennent en argument une liste peuvent bien entendu utiliser les fonctions standard (null pour savoir si la liste est vide, head pour en extraire le premier élément, etc.) pour accéder aux éléments de la liste, mais elles gagnent souvent en concision et en lisibilité en utilisant un filtrage de motif.

Voici par exemple programmées par filtrage de motifs les fonctions tete et reste équivalentes aux fonctions head et tail. Ces deux fonctions déclenchent une exception lorsque la liste est vide.

tete (x:_) = x

reste (_:xs) = xs

Remarque : il est de coutume d’utiliser un genre de notation hongroise pour les noms des paramètres en Haskell. Ainsi les noms de paramètres contenant une liste finissent généralement par un s (marque du pluriel… ; une liste de listes sera xss, etc.). N’oubliez pas qu’un code lisible est plus facile à comprendre, même à son auteur, et qu’il contient donc moins de bogues.

Notez que nous n’avons pas défini de comportement dans le cas d’une liste vide :

*Main> tete "acdef"
'a'
it :: Char
*Main> tete ""
*** Exception: test.hs:1:1-14: Non-exhaustive patterns in function tete

mais cette erreur sera détectable à la compilation, quand le compilateur nous donnera un exemple de liste que notre fonction tete ne sait pas traiter :

test.hs:1:1: Warning:
    Pattern match(es) are non-exhaustive
    In an equation for `tete': Patterns not matched: []

Nous pouvons alors rajouter une equation de sorte que la définition complète de tete soit :

tete (x:_) = x
tete []    = error "tete: liste vide"

(ce qui aura le même effet d’interrompre l’exécution à cet endroit, mais avec un message un peu plus compréhensible…)

Remarque : malgré cet exemple, les exceptions sont très peu utilisées en Haskell car elles sont par nature impures ; au même titre qu’un abort(); en C, elles sont à réserver essentiellement aux cas où l’on veut avorter immédiatement le programme complet.

Le calcul de la longueur d’une liste avec un filtrage de motifs se programme tout simplement aussi.

longueur []     = 0
longueur (_:xs) = 1 + longueur xs

On peut réécrire ces fonctions sans utiliser directement le filtrage à gauche du = en utilisant l’expression case … of Par exemple :

longueur' xs = case xs of
                 []    -> 0
                 _:xs' -> 1 + longueur' xs'

Attention : il est très important de bien aligner les différents cas, [ et _ doivent être sur la même colonne. Comme les alignements sont un cauchemar quand on mélange tabulations et espaces, configurez votre éditeur pour qu’il n’indente qu’en utilisant des espaces.

Notez aussi que, toujours en suivant les coutumes haskellesques, nous avons utilisé xs' comme nom pour la sous-liste de xs : les noms xs et xs' apparaissent ainsi immédiatement liés pour le lecteur humain ce qui aide, encore une fois, la lecture et compréhension du code.

Un dernier exemple, pour la route, où l’on voit que le filtrage peut s’appliquer sur tous les paramètres d’une fonction :

liste_sommes []     []     = []
liste_sommes (x:xs) (y:ys) = x+y : liste_sommes xs ys

Ici, l’idée est bien de constituer la liste des sommes : l’expression x+y : liste_sommes xs ys doit être lue comme (x+y) : (liste_sommes xs ys). Haskell est un langage purement fonctionnel : l’application d’une fonction comme liste_sommes à ses arguments prime sur tous les opérateurs, comme :. Il faut encore départager + et :. Utilisez des parenthèses quand vous n’êtes pas sûrs des priorités4.

Exercices

  1. Programmez la fonction sommeDeXaY du TD1.

  2. Programmez une fonction somme de type [Int] -> Int qui calcule la somme des éléments de la liste.

  3. Re-programmez les fonctions standard last et init en utilisant uniquement les fonctions head, tail, !!, take, drop, length, ++, reverse.

  4. Re-programmez les fonctions standard !!, ++, concat, map (en leur donnant un autre nom pour éviter le conflit avec les fonctions du Prelude) en n’utilisant que du filtrage de motifs.

  5. Si l est une liste (de type [a], ignorons pour l’instant le type des éléments), que représente la déclaration

  6. Utilisez map et somme pour définir une fonction calculant la longueur d’une liste.

  7. Programmez une fonction qui prend pour paramètres :
    1. une fonction f de type a -> a,
    2. un élément x de type a,
    3. et un entier n (≥ 0),

    et construit la liste [x, f x, f (f x), ..., f (f (f ... (f x) ... )] où le dernier élément est fn(x).

    Vous proposerez une version récursive et une version utilisant les fonctions standard iterate et take.

  8. Utilisez la fonction précédente pour définir une fonction à un argument entier n ≥ 0 qui produit la liste des entiers consécutifs de 0 à n.

Si vous terminez rapidement, vous pouvez poursuivre la lecture du LYAH en français ou en anglais.


  1. Nous verrons plus tard comment nommer un module

  2. Et dans la plupart des langages fonctionnels.

  3. Attention, les significations de : et :: sont exactement inverses entre Haskell et OCaml…

  4. Pour apprendre les priorités des opérateurs, vous pouvez utiliser la commande :info :

    L’information que l’on cherche est donnée par les lignes infix… (puisque les opérateurs s’utilisent en général en notation infixe, c’est-à-dire entre leurs deux arguments).

    +, à 6, est prioritaire sur :, à 5. Cela signifie que x+y:z est parsé comme (x+y):z.

    Par ailleurs, + associe à gauche (l) de sorte que 1 + 2 + 3 est parsée comme (1 + 2) + 3, tandis que : associe à droite (r) de sorte que 1 : 2 : [] est parsée comme 1 : (2 : []) (heureusement ! (1 : 2) : [] n’est pas ce qu’on veut dire, puisque 2 n’est pas une liste ; de façon générale, il est plus courant d’ajouter deux éléments en tête d’une liste plutôt que d’ajouter une tête à une liste qu’on ajoute dans une liste de listes… d’où le choix d’associativité de :).