Cours 02 : 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.
-- commentaire : directive pour le compilateur ghc
:opt no-lint
(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 [[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)$.
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)$.
[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.
Exercice¶
Parmi ces expressions, lesquelles sont valides en Haskell, et pourquoi ?
([2,4],[2,4,5])
([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.
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
'a': "bcd"
"abcd"
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
Il existe également des fonctions pour manipuler les caractères dans le module Data.Char.
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 (déconstruction):
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 (3,2) (1,8)
6.324555320336759
On peut utliser where combiné avec le pattern matching :
distance :: (Double, Double) -> (Double, Double) -> Double
distance (x, y) (0, 0) = sqrt (x ^ 2 + y ^ 2)
distance (0, 0) (x, y) = sqrt (x ^ 2 + y ^ 2)
distance p1 p2 = sqrt ((x2 - x1) ^ 2 + (y2 - y1) ^ 2)
where
(x1, y1) = p1
(x2, y2) = p2
distance (0,0) (1,8)
8.06225774829855
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
Pattern matching pour les listes¶
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
atLeastTwo :: [a] -> Bool
atLeastTwo [] = False
atLeastTwo [_] = False
atLeastTwo _ = True
atLeastTwo [1]
atLeastTwo [1..10]
False
True
Une liste est une structure de données récursive : elles est soit vide, soit composée d'un élément suivi une liste. Le pattern matching permet de suivre cette décomposition naturellement.
sum' :: [Int] -> Int
sum' [] = 0
sum' (x:xs) = x + sum' xs
size :: [a] -> Int
size [] = 0
size (_:xs) = 1 + size xs
atLeastTwo :: [a] -> Bool
atLeastTwo (x:y:xs) = True
atLeastTwo _ = False
Exemples classiques¶
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 ["avion","ballon","chat"]
["chat","ballon","avion"]
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¶
Recoder des fonctions classiques sur les listes en utlisant le pattern matching (voici quelques exemples).
take 10 [1..]
[1,2,3,4,5,6,7,8,9,10]
:t take
drop 10 ['a'..'z']
"klmnopqrstuvwxyz"
Quelle est la complexité de ces différentes 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"