Première partie : pourquoi apprendre à programmer en Haskell ?¶
Qu'est-ce que Haskell ?¶
C'est un langage fonctionnel.¶
La programmation fonctionnelle, est basée sur l'évaluation et la composition de fonctions. Elles peuvent être manipulées comme des valeurs, passées en argument et renvoyées comme résultat.
On oppose souvent la programmation fonctionnelle à la programmation impérative qui favorise l'exécution d'une séquence d'instructions pour modifier l'état du programme. Beaucoup de langages (par ex. C, Java, JavaScript, Python,...) permettent les deux.
Il n'y a pas de notion d'instruction, mais uniquement des expressions qui ont nécessairement une valeur. En particulier, il n'y a pas d'affectation (mutable) comme dans Java, Python ou C. On ne peut pas "modifier une variable".
Cela implique, entre autres, qu'on ne peut pas écrire de boucles impératives classiques comme for ou while, car elles reposent sur la modification d'un état. Pour obtenir un comportement équivalent, il faut utiliser des fonctions récursives.
Haskell est un langage de programmation fonctionnel pur.¶
Toutes les fonctions sont considérées comme des fonctions mathématiques déterministes, ou des fonctions pures:
- Si une fonction est appelée plusieurs fois, avec les mêmes paramètres, alors il est garanti qu'elle renverra le même résultat.
- Elle ne peut être affectée ni par un état mutable ni par d'autres effets de bord.
Cela implique la transparence référentielle : n'importe quelle expression peut être remplacée par sa valeur, sans changer le comportement du programme. Par exemple, en C, ce n'est pas vrai : on peut remplacer (1+2) par 3 mais pas x++ par sa valeur, qui est x.
Cela permet de raisonner sur le comportement du programme, de déduire facilement (et même de prouver) qu'une fonction est correcte, puis de construire des fonctions plus complexes en composant des fonctions simples.
Haskell est un langage paresseux.¶
L’évaluation paresseuse (lazy), est une stratégie d’évaluation qui retarde l’évaluation d’une expression jusqu’au moment où sa valeur est nécessaire. Par exemple, les paramètres d'une fonction ne sont pas évalués avant que les résultats de cette évaluation ne soient réellement nécessaires.
Haskell est un langage typé statiquement.¶
Le type des valeurs est déterminé et vérifié avant l’exécution du programme, généralement au moment de la compilation, par opposition au typage dynamique (Python, JavaScript, ...). Par exemple, Java est statiquement typé, mais utilise aussi des mécanismes de typage dynamique lorsque le type déclaré et le type réel d'un objet sont différents.
Comme en à Java (depuis les var) et contriarement au C, en Haskell, il n'est pas nécessaire de déclarer les types des expressions explicitement. L'interpréteur ou le compilateur est capable de déduire automatiquement le type des valeurs et expressions, c'est ce qu'on appelle l'inférence de type.
Haskell est un langage compilé.¶
Avec le compilateur le plus courant, GHC (Glasgow Haskell Compiler), le code Haskell est généralement compilé en code natif, ou parfois en bytecode, avant d’être exécuté.
Il existe aussi un mode interactif qui est celui que nous allons utiliser en TP avec la commande ghci.
Ce mode permet de charger un fichier, évaluer des expressions et tester des fonctions rapidement. Cela ressemble à un interpréteur, mais GHCi utilise en pratique du bytecode ou de la compilation dynamique.
Premiers pas¶
-- commentaire : directive pour le compilateur ghc
:opt no-lint
Premières expressions, nombres, calcul¶
Comme dans la plupart des langages, on peut calculer.
-- expression simple
1
1
-- additionner, soustraire
3 + 5
8
Nous venons d'utiliser un opérateur infixe.
-- multiplier
3 * 5
15
-- diviser
5 / 2
2.5
On remarque qu'il s'agit d'une division sur les réels (pas une division entière).
-- plusieurs calculs
1 - 2 * 3
1 - (2 * 3)
(1 - 2) * 3
-5
-5
-3
Booléens¶
-- vrai
True
True
-- opérateurs booléens
True || False
True && False
not True
True
False
False
-- tester l'égalité de booléens
True == False
False
-- tester l'(in)égalité de nombre
1 /= 2
True
1 == True
<interactive>:1:1: error:
• No instance for (Num Bool) arising from the literal ‘1’
• In the first argument of ‘(==)’, namely ‘1’
In the expression: 1 == True
In an equation for ‘it’: it = 1 == True
⚠ L'opérateur == est typé. Le premier argument est 1, c'est un nombre. Donc, l'inférence de type essaie de savoir si True, qui est un booléen, peut être considéré comme un nombre au même titre que 1.
Haskell est fortement typé¶
L'exemple précédent nous rappelle que même si nous n'écrivons pas explicitement les types, toutes les expressions Haskell sont typées.
"2" + 3
<interactive>:1:1: error:
• No instance for (Num String) arising from a use of ‘+’
• In the expression: "2" + 3
In an equation for ‘it’: it = "2" + 3
-- quel est le type de True ?
:type True
-- quel est le type de 'a' ?
:t 'a'
-- quel est le type de "Abc" ?
:t "Abc"
:t (True, True)
:t (True, 'a', "cat")
-- quel est le type de 1 ?
:t 1
Types "basiques"¶
Bool— Valeurs logiques.Char— Caractères individuels.String— Chaînes de caractères (équivalent de[Char]).Int— Entiers à précision fixe.Integer— Entiers à précision arbitraire.Float— Nombres à virgule flottante à simple précision.Double— Nombres à virgule flottante à double précision.
On verra le système de types plus en détail au prochain cours.¶
Haskell est un langage fonctionnel¶
Exemples d'utilisation de fonction¶
-- calculer la racine carrée de 16
sqrt 16
4.0
-- calculer le minimum de 2 nombres
min 2 4
2
On remarque que l'on n'utilise pas de parenthèses pour appeler une fonction avec un (des) paramètre(s).
min 2 -2
<interactive>:1:1: error:
• Non type-variable argument in the constraint: Num (a -> a)
(Use FlexibleContexts to permit this)
• When checking the inferred type
it :: forall a. (Ord a, Num a, Num (a -> a)) => a -> a
⚠ L'application de fonction est l'opération qui a la priorité maximale. Dans l'expression ci-dessus, on essaie donc d'appliquer min à l'entier 2 et à l'opérateur -, ce qui ne correspond pas au type de min qui doit prendre en paramètre deux nombres comparables.
min 2 (-2)
-2
-- on a déjà vu un exemple de fonction dans la première partie...
-- quel est le type de l'expression que nous venons d'évaluer ?
:t not True
-- quel est le type de la fonction not ?
:t not
Le type d'une fonction s'écrit toujours type param1 -> type param2 -> ... -> type de retour, avec des parenthèses éventuelles.
-- quel est le type de la fonction sqrt ?
:t sqrt
Ici, le type signifie : pour n'importe quel type de flottant (on a vu Float et Double) que l'on nomme a, la fonction sqrt prend en paramètre une valeur de type a et renvoie une valeur de type a.
La signature de la fonction est la partie qui vient après =>.
even 15
even 16
False
True
:t even
Ici, le type signifie : pour n'importe quel type d'entier (on a vu Int et Integer) que l'on nomme a, la fonction even prend en paramètre une valeur de type a et renvoie un booléen.
div 5 2
2
5 / 2
2.5
On peut transformer n'importe quel opérateur infixe en fonction (préfixe) en l'écrivant entre parenthèses.
(/) 5 2
2.5
:t div
:t (/)
Ici, le type signifie : pour n'importe quel type entier (ou fractionnaire) que l'on nomme a, la fonction prend en paramètre deux valeurs de type a et renvoie une valeur de type a.
On peut transformer une fonction préfixe à deux paramètres en opérateur infixe en utilisant des backquotes.
5 `div` 2
2
pi
round pi
3.141592653589793
3
(sin pi)^2 + (cos pi)^2
1.0
Haskell est un langage paresseux¶
-- l'évaluation de cette expression provoque une erreur
div 10 0
divide by zero
f x = 1
:t f
f (div 10 0)
1
f x = x
:t f
f (div 10 0)
divide by zero
On a dit "pas d'affectation de variable"... vraiment ?¶
a = 1
a
1
a = 2
a
2
:t a
a = a + 1
-- a
L'évaluation ne s'arrête jamais...
En Haskell, a = 1 n'est pas une affectation au sens impératif. C’est une définition ou une liaison.
La différence est essentielle. En Java, par exemple (ou C, ou Python,...), une affectation modifie l’état d’une variable, on peut écrire :
a = 1
a = 2
Après la seconde ligne, la variable a contient une nouvelle valeur. On a modifié le contenu de son emplacement en mémoire. En Haskell, une définition associe un nom à une expression. La ligne
a = 1
signifie que a désigne la valeur 1.
Quand on écrit
a = a + 1
ce n'est pas une incrémentation de la variable a, c'est une définition récursive.
Quels sont les inconvénients d'un langage fonctionnel ? Et de Haskell en particulier ?¶
On considère souvent que les langages fonctionnels sont plus difficiles à apprendre, en particulier pour les programmeurs déjà formés aux langages impératifs. Plusieurs notions habituelles doivent être repensées : absence d'affectation mutable par défaut, recours fréquent à la récursivité, immutabilité des données, niveau d'abstraction plus élevé, typage parfois sophistiqué, etc.
Pour des raisons similaires, c'est souvent plus difficile à debugger qu'une suite d'instructions modifiant progressivement un état.
Haskell ne permet pas de faire "simplement" des effets de bord, donc les entrées-sorties ne sont pas facilement accessibles (elles doivent être représentées explicitement, par exemple au moyen du type IO).
Les performances peuvent également être plus difficiles à contrôler. L'immutabilité, l'évaluation paresseuse,... rendent parfois le coût en temps ou en mémoire moins prévisible. De plus, certaines structures de données ne peuvent pas toujours être implémentées aussi efficacement que dans un langage impératif, notamment les tableaux ou les tables de hachage modifiables en place.
Enfin, le style fonctionnel est beaucoup moins largement utilisé que le style impératif dans l'industrie. Haskell, en particulier, reste très peu utilisé professionnellement par comparaison avec des langages comme Java, Python, JavaScript, C# ou C++.
Mais alors, pourquoi apprendre Haskell ?¶
Pour améliorer le code que vous écrivez 😊¶
- Pour mieux comprendre les aspects fonctionnels des langages que vous utilisez déjà ou que vous utiliserez plus tard (Python, Java, JavaScript, Rust, ...)
- Pour apprendre à coder sans effets de bord et avec des objets non mutables (c'est bien pour faire de la concurrence, entre autres...).
- Pour être plus à l'aise avec les notions de typage avancées
- Pour s'habituer à programmer de façon modulaire : écrire une fonction de façon récursive oblige à savoir spécifier précisément ce que fait une fonction.
Éléments de correction de la première partie du TP¶
-- myAdd
-- myMinimumOfThree
-- isPrime
Deuxième partie : on commence à programmer¶
Vous avez commencé à vous familiariser avec le langage et l'interpréteur ghci et vous avez défini vos premières fonctions. Nous allons ajouter d'autres éléments pour continuer.
Structures de données et un peu de syntaxe¶
Tuples¶
Nous avons vu, au détour d'un exemple, que l'on pouvait définir des tuples assez naturellement.
(1,2)
(1,2)
(1,2,3)
(1,2,3)
:t ('a','b')
:t ('a',True)
-- ceci n'est pas un tuple
:t ('a')
(1,(2,3))
(1,(2,3))
fst ("a",'b')
"a"
snd ("a",'b')
'b'
Remarque : ces fonctions s'appliquent uniquement aux paires. Elles ne fonctionnent pas avec les triplets, les quadruplets, etc. Nous verrons un peu plus loin d’autres façons d’extraire des données d’un tuple.
Premières listes¶
[1,2,3]
[1,2,3]
:t [True,False,False]
[]
[]
:t []
:t [[]]
:t [[1,2],[],[1,2,3]]
On peut définir des ranges.¶
[1..10]
[1,2,3,4,5,6,7,8,9,10]
[10..1]
[]
[10,9..1]
[10,9,8,7,6,5,4,3,2,1]
[1,3..10]
[1,3,5,7,9]
-- [1,3..]
Remarque : en Haskell, il est possible de définir des listes en compréhension, comme en Python. Dans ce cours, nous n'utiliserons pas cette façon de faire afin de limiter la quantité de syntaxe à maîtriser.
1 : [2, 3]
[1,2,3]
"Hello" : ["World"]
["Hello","World"]
:t (:)
(:) prend une valeur de type a et une liste de type [a] et renvoie une nouvelle liste de type [a] constituée de la valeur suivie des éléments de la liste d'origine. La complexité de cette fonction est $O(1)$.
[1..10] ++ [11,12]
[1,2,3,4,5,6,7,8,9,10,11,12]
:t (++)
(++) prend deux listes de type [a] et renvoie une nouvelle liste de type [a] qui est la concaténation de ces deux listes.
⚠ La complexité de cette fonction est $O(n)$ où $n$ est la longueur de la première liste.
head [1,2,3,4,5]
tail [1,2,3,4,5]
1
[2,3,4,5]
Ces fonctions renvoient respectivement le premier élément et la fin d'une liste. La complexité de ces fonctions est $O(1)$.
Exercice : parmi les expressions suivantes, lesquelles sont valides en Haskell, et pourquoi ?¶
([2,4],[2,4,5])
[(2,4),(5,5),('a','b')]
1 : (2,3)
(2,4) : (2,3)
(2,4) : []
(2,4) ++ []
head [1..10] == [1]
head [1..10] + 100
[1..10] + 100
Quelques fonctions supplémentaires sur les listes¶
length [1..2^10]
1024
elem 'a' ['A'..'Z']
False
last [1,2,3,4,5]
init [1,2,3,4,5]
5
[1,2,3,4]
Ces fonctions renvoient respectivement le dernier élément et le début d'une liste. ⚠ Attention, la complexité de ces fonctions est $O(n)$ où $n$ est la longueur de la liste.
take 10 [1..]
[1,2,3,4,5,6,7,8,9,10]
:t take
drop 10 ['a'..'z']
"klmnopqrstuvwxyz"
reverse ["avion","ballon","chat"]
["chat","ballon","avion"]
Quelle est la complexité de ces différentes fonctions ?
La documentation de toutes les fonctions standard sur les listes se trouve ici.
Chaînes de caractères¶
En Haskell, les chaînes de caractères sont simplement des listes de caractères, le type String est donc équivalent au type [Char].
"abc" == ['a','b','c']
True
Il existe quelques fonctions spécifiques aux caractères et aux chaînes de caractères.
words "Il etait une fois... \n ou deux"
["Il","etait","une","fois...","ou","deux"]
show 42
"42"
:t show
read "42" :: Int
42
:t read
import Data.Char
isAlpha '4'
isAlpha 'A'
False
True
isDigit 'a'
False
toUpper 'a'
'A'
ord 'a'
97
Il en existe d'autres, consultez la documentation pour les connaître.
Pattern matching¶
Le pattern matching consiste à choisir une définition selon la forme ou la valeur des paramètres reçus par une fonction.
Une suite d’expressions syntaxiques, appelées patterns, permet de choisir entre plusieurs résultats du même type. Le pattern générique _ correspond à n’importe quelle valeur.
- Si le premier pattern correspond, le premier résultat est choisi.
- Sinon, si le deuxième pattern correspond, le deuxième résultat est choisi.
- Et ainsi de suite...
On commence avec quelques exemples simples :¶
intToText :: Int -> String
intToText 0 = "zero"
intToText 1 = "un"
intToText 2 = "deux"
intToText _ = "non compris entre 0 et 2"
intToText 1
"un"
intToText 3
"non compris entre 0 et 2"
La factorielle, grand classique :
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)
factorial 5
120
Calcul de $x^n$ :
pow :: Int -> Int -> Int
pow x 0 = 1
pow x 1 = x
pow x n = x * pow x (n - 1)
pow 2 10
1024
Le "ET" logique :
and' :: Bool -> Bool -> Bool
and' True True = True
and' True False = False
and' False True = False
and' False False = False
and' (10 == 2 *5) ('a' == head ['a'])
True
and' :: Bool -> Bool -> Bool
and' True b = b
and' False _ = False
and' :: Bool -> Bool -> Bool
and' True True = True
and' _ _ = False
Extraire les données d'un triplet :
first3 :: (a, b, c) -> a
first3 (x, _, _) = x
second3 :: (a, b, c) -> b
second3 (_, y, _) = y
third3 :: (a, b, c) -> c
third3 (_, _, z) = z
first3 (10,20,30)
second3 (10,20,30)
third3 (10,20,30)
10
20
30
Distance entre deux points $(x_1,y_1)$ et $(x_2,y_2)$ :
distance :: (Double, Double) -> (Double, Double) -> Double
distance (x1, y1) (x2, y2) = sqrt ((x2 - x1) ^ 2 + (y2 - y1) ^ 2)
distance (2,3) (1,8)
5.0990195135927845
On peut utliser where combiné avec le pattern matching :
distance :: (Double, Double) -> (Double, Double) -> Double
distance (x1, y1) (x2, y2) = sqrt (dx ^ 2 + dy ^ 2)
where
dx = x2 - x1
dy = y2 - y1
Attention au pattern matching non exhaustif :
intToText :: Int -> String
intToText 0 = "zero"
intToText 1 = "un"
intToText 2 = "deux"
intToText 3
<interactive>:(2,1)-(4,20): Non-exhaustive patterns in function intToText
Le pattern matching est très utile pour définir des fonctions (récursives) sur les listes¶
-- mot d'exactement trois caractères commençant par un 'a'
test :: [Char] -> Bool
test ['a', _, _] = True
test _ = False
test "abc"
test "abcd"
test "cba"
True
False
False
isEmpty :: [a] -> Bool
isEmpty [] = True
isEmpty _ = False
isEmpty []
isEmpty [1..]
True
False
isEmpty :: [a] -> Bool
isEmpty (x:xs) = False
isEmpty _ = True
atLeastTwo :: [a] -> Bool
atLeastTwo [] = False
atLeastTwo [_] = False
atLeastTwo _ = True
atLeastTwo []
atLeastTwo [1]
atLeastTwo [1..10]
False
False
True
atLeastTwo :: [a] -> Bool
atLeastTwo (x:y:xs) = True
atLeastTwo _ = False
On peut recoder facilement les fonctions standard sur les listes.¶
-- on suppose que la liste ne peut pas être vide, on verra plus tard comment gérer ça.
last' :: [a] -> a
last' [x] = x
last' (_ : xs) = last' xs
last' [1..100]
100
elem' :: Eq a => a -> [a] -> Bool
elem' _ [] = False
elem' e (x : xs) = x == e || elem' e xs
elem' 5 [1,2,3,4,5,6,7]
elem' 15 [1,2,3,4,5,6,7]
True
False
reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = (reverse' xs) ++ [x]
reverse' [1..10]
[10,9,8,7,6,5,4,3,2,1]
Hum... et la complexité ?
En TP, on recode d'autres fonctions¶
zip [1,2,3,4,5] ['a','b','c','d','e']
zip [1,2,3] ['a','b','c','d','e']
zip [1,2,3,4,5] ['a','b','c']
[(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e')]
[(1,'a'),(2,'b'),(3,'c')]
[(1,'a'),(2,'b'),(3,'c')]
unzip [(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e')]
([1,2,3,4,5],"abcde")
import Data.List
intersperse 0 [1..10]
intersperse ',' ['a'..'z']
[1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9,0,10]
"a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z"
intercalate [0] [[1,2],[3,4],[5,6]]
intercalate "-" ["b","cd","efg"]
[1,2,0,3,4,0,5,6]
"b-cd-efg"