TP 01 - Débuter en Haskell

Programmation fonctionnelle

Première partie - (Échauffement) Interpréteur GHCi

La documentation de GHCi est ici : https://ghc.gitlab.haskell.org/ghc/doc/users_guide/ghci.html#.

Les directives de base de GHCi commencent par : :

:help ou :? : affiche l’aide.
:type expression ou :t expression : affiche le type d’une expression.
:load Fichier.hs ou :l Fichier.hs : charge un fichier Haskell.
:reload ou :r : recharge le dernier fichier chargé.
:info nom ou :i nom : affiche les informations sur une fonction, un type ou une classe.
:set option : active une option, par exemple :set +s pour afficher le temps et la mémoire utilisés.
:! commande : exécute une commande système, par exemple :! ls.
:quit ou :q : quitte GHCi.

Pour appliquer un réglage à chaque démarrage de GHCi, créez ou modifiez le fichier ~/.ghci. Par exemple :

:set prompt "\ESC[34mλ> \ESC[m"

Et voici un exemple d’utilisation.

λ> :load TP-01.hs
λ> :t map
map :: (a -> b) -> [a] -> [b]
λ> :reload
λ> :quit

Exercice 1.1

Pour chacune des expressions suivantes, déterminer sa valeur et proposer un type explicite correspondant, puis vérifier avec l’interpréteur.

21 + 2
(+) 21 2
21 + 2 * 3
(+) 21 (2*3)
(+) 21 ((*) 2 3)
1 == 2
1 /= 2
1 + (-1)
div 11 2
11 `div` 2
42 `mod` 2 == 0
even 42
odd 42
pred 42
sqrt 49

Pour vérifier le type, vous pouvez essayer d’ajouter une annotation de type à l’expression pour vous assurer que ça ne cause pas d’erreur. Par exemple :

λ> 11 / 2 :: Double
5.5
λ> 11 / 2 :: Int

<interactive>:41:1: error:
    • No instance for (Fractional Int) arising from a use of ‘/’
    ...

Exercice 1.2 - Expressions conditionnelles

La structure de contrôle conditionnelle en Haskell possède la syntaxe suivante :

if expr1 then expr2 else expr3

Attention, il s’agit d’une expression, elle a donc un type et une valeur. L’expression expr1 est de type Bool et les expressions expr2 et expr3 doivent être du même type (qui est également le type de l’expression complète).

λ> if True then "#t" else "#f"
"#t"
λ> if False then "#t" else "#f"
"#f"
λ> :type if True then "#t" else "#f"
if True then "#t" else "#f" :: String

Écrire une expression pour calculer le maximum entre les entiers \(x\) et \(y\) :

λ> x = ...
λ> y = ...
λ> maxValue = ...

Écrire une expression pour calculer la valeur absolue de \(x\) (sans utiliser la fonction abs) :

λ> x = ...
λ> absoluteValue = ...

Étant donné un entier \(x\), en utilisant une expression conditionnelle, donnez le code permettant d’obtenir la partie entière supérieure de \(x/2\) notée \(\lceil x/2 \rceil\) (sans utiliser la fonction ceiling).

λ> x = ...
λ> ceil = ...

Indice : vous pouvez utiliser la parité de \(x\).

Exercice 1.3 - Premières définitions de fonctions

Comment définir ses propres fonctions en Haskell

Une fonction Haskell se définit avec son nom, ses paramètres, puis = et le résultat :

λ> double x = 2 * x

Ici, double reçoit x et renvoie 2 * x.

Par inférence de type, GHC est capable de déterminer le type de la fonction lui-même :

λ> :t double
double :: Num a => a -> a

Mais dans ce cours, je vous demande d’ajouter la signature de type au-dessus de la définition, par exemple :

double :: Int -> Int
double x = 2 * x

Int -> Int signifie : la fonction prend un Int et renvoie un Int.

Avec plusieurs paramètres, ça donne :

addTwo :: Int -> Int -> Int
addTwo x y = x + y

Avec des types différents :

isBig :: Int -> Bool
isBig x = x > 100

Si vous avez essayé de tester, vous avez remarqué que l’on atteint les limites de GHCi car on ne peut pas écrire le type puis la définition de la fonction sur la ligne suivante. À partir de maintenant, vous allez donc écrire toutes vos définitions de fonctions dans un fichier. Aujourd’hui, créez le fichier TP-01.hs et recopiez les définitions précédentes dedans. Puis dans GHCi, vous pouvez charger les définitions et les tester :

λ> :load TP-01.hs
λ> :t isBig 
isBig :: Int -> Bool
λ> isBig 10
False

À vous de jouer.

Définir (avec son type) une fonction myAdd qui calcule la somme de deux entiers.

λ> myAdd 5 8
13

Définir (avec son type) une fonction myMinimum qui calcule le minimum de deux réels.

λ> myMinimum 5.0 8.1
5.0

Définir (avec son type) une fonction myMinimumOfThree qui calcule le minimum de trois réels. On rappelle que la programmation fonctionnelle repose en partie sur la composition de fonctions.

λ> myMinimumOfThree 5.0 8.1 2.3
2.3

Écrire une fonction récursive.

Une fonction récursive est une fonction qui s’appelle elle-même. Pour l’écrire, il faut d’abord préciser exactement ce qu’elle doit calculer, puis identifier :

un cas de base, que l’on sait résoudre directement ;
une façon de réduire la taille du problème ;
une façon d’obtenir la solution à partir de celle du problème plus petit.

La question à se poser est : « Si je connais la solution pour un problème plus petit, comment puis-je en déduire la solution pour le problème initial ? » Il faut aussi vérifier que chaque appel récursif rapproche du cas de base.

Par exemple, voici la défintion de la factorielle :

fac :: Int -> Int
fac n = if n == 0 then 1 else n * fac (n - 1)

Sans utiliser ni + ni -, ni myAdd, définir (avec son type) une fonction myAdd' qui calcule la somme de deux entiers \(x\) et \(y\). Nous supposerons dans cet exercice que \(y \geq 0\). Rappel : en Haskell, il existe des fonctions pour obtenir le prédécesseur ou le successeur d’un entier.

λ> myAdd' 5 8
13

La suite de Syracuse est une suite d’entiers naturels définie de la manière suivante : on part d’un nombre entier strictement positif ; s’il est pair, on le divise par 2 ; s’il est impair, on le multiplie par 3 et l’on ajoute 1. En répétant l’opération, on obtient une suite d’entiers strictement positifs dont chacun ne dépend que de son prédécesseur.
1. Définir (avec son type) une fonction nextSyracuse qui, étant donné un entier, calcule le suivant dans la suite de Syracuse.
```
λ> nextSyracuse 14
7
λ> nextSyracuse 7
22
```
1. Définir (avec son type) une fonction syracuse qui, étant donné un entier, renvoie le nombre d’étapes pour que la suite de Syracuse arrive à 1 (remarque : la conjecture de Syracuse, aussi appelée conjecture de Collatz, affirme que, quelle que soit la valeur entière positive de départ, la suite finit toujours par atteindre 1… mais ce n’est pas prouvé).
```
λ> syracuse 14
17
```
Définir, avec son type, une fonction sumDigits qui prend un entier positif ou nul et renvoie la somme de ses chiffres.

λ> sumDigits 2048
14
λ> sumDigits 111
3

Définition locale

Le mot-clé where permet de définir des fonctions ou variables locales, utilisées uniquement par la fonction qui le précède. Par exemple, on peut écrire :

circleArea :: Double -> Double
circleArea radius = pi * squaredRadius
  where
    squaredRadius = radius * radius

La structure est toujours :

functionName parameters = expression
  where
    localDefinition1 = ...
    localDefinition2 = ...

Définir, avec son type, une fonction numberAndSumDigits qui prend un entier positif ou nul et renvoie une paire contenant son nombre de chiffres et la somme de ses chiffres. L’objectif de cette question est de ne faire la décomposition récursive en chiffres qu’une seule fois.

λ> numberAndSumDigits 2048
(4,14)
λ> numberAndSumDigits 111
(3,3)

Définir, avec son type, une fonction isPrime qui teste si un entier \(n\) est premier. On rappelle qu’un nombre premier est un nombre entier naturel qui possède exactement deux diviseurs entiers positifs distincts : 1 et lui-même. On supposera ici que \(n\) est positif. Souvenez-vous qu’il est souvent utile de définir des fonctions intermédiaires.

λ> isPrime 6
False
λ> isPrime 7
True

Exercice Optionnel - Guards! Guards!

Les gardes permettent de choisir un résultat selon des conditions. Elles s’écrivent après les paramètres d’une fonction avec |.

absoluteValue :: Int -> Int
absoluteValue number
  | number >= 0 = number
  | otherwise   = -number

Les gardes sont testées dans l’ordre :

grade :: Int -> String
grade score
  | score >= 16 = "very good"
  | score >= 10 = "passed"
  | otherwise   = "failed"

λ> grade 18
"very good"
λ> grade 12
"passed"
λ> grade 7
"failed"

La structure générale est :

functionName parameters
  | condition1 = result1
  | condition2 = result2
  | otherwise  = defaultResult

Notez qu’il n’y a pas de = après les paramètres et avant les gardes.

On peut les combiner avec where :

fizzBuzz :: Int -> String
fizzBuzz number
  | divisibleBy3 && divisibleBy5 = "FizzBuzz"
  | divisibleBy3                 = "Fizz"
  | divisibleBy5                 = "Buzz"
  | otherwise                    = ""
  where
    divisibleBy3 = number `mod` 3 == 0
    divisibleBy5 = number `mod` 5 == 0

Les gardes permettent d’écrire des suites de if-then-else imbriqués de façon lisible.

Enutilisant des guardes, définir, avec son type, une fonction countSetBits qui prend un entier positif ou nul et compte les chiffres 1 dans son écriture binaire.

λ> countSetBits 13
3
λ> countSetBits 8
1
λ> countSetBits 0
0

Enutilisant des guardes, définir, avec son type, une fonction isPowerOfThree qui teste si un entier positif est une puissance de 3. On considère que 1 est une puissance de 3, car 1 = 3^0.

λ> isPowerOfThree 81
True
λ> isPowerOfThree 45
False
λ> isPowerOfThree 1
True
λ> isPowerOfThree 0
False

Définir isPrime' avec des gardes.

Deuxième partie

Exercice 2.1

Pour chacune des expressions suivantes, déterminer son type, puis vérifier avec l’interpréteur.

'a'
"abc"
[]
['a']
['a', 'b']
["abc", "def"]
['a', "abc"]
('a', 'b')
('a', "abc")
('a', "abc", 1)
[odd, even]
[odd, even, (==) 1]
[odd, even, mod]
(odd, even, mod)

Exercice 2.2 - Fonctions sur les listes

La fonction delete du module Data.List supprime la première occurrence d’un élément dans une liste. Définir, avec son type, une fonction delete' ayant le même comportement pour les listes d’entiers.

λ> delete' 2 [1,2,3,2,1]
[1,3,2,1]
λ> delete' 20 [1,2,3,2,1]
[1,2,3,2,1]

Définir, avec son type, une fonction deleteAll' qui prend un entier et une liste d’entiers, puis supprime toutes les occurrences de cet entier dans la liste.

λ> deleteAll' 2 [1,2,3,2,1]
[1,3,1]

La fonction repeat de Prelude construit une liste infinie contenant toujours le même élément. Définir, avec son type, une fonction repeat' ayant le même comportement.

λ> take 10 (repeat' 1)
[1,1,1,1,1,1,1,1,1,1]

La fonction take de Prelude prend les n premiers éléments d’une liste. Si la liste contient moins de n éléments, elle renvoie la liste entière. Définir, avec son type, une fonction take' ayant le même comportement. Ici, pour simplifier, on suppose que n n’est pas négatif.

λ> take' 10 [1..100]
[1,2,3,4,5,6,7,8,9,10]
λ> take' 10 [1..]
[1,2,3,4,5,6,7,8,9,10]
λ> take' 10 [1..2]
[1,2]

La fonction drop de Prelude retire les n premiers éléments d’une liste. Si la liste contient moins de n éléments, elle renvoie la liste vide. Définir, avec son type, une fonction drop' ayant le même comportement. Ici, pour simplifier, on suppose que n n’est pas négatif.

λ> drop' 10 [1..15]
[11,12,13,14,15]
λ> drop' 10 [1..2]
[]

Définir, avec son type, une fonction twoByTwo qui transforme une liste en une liste de paires d’éléments consécutifs. Si la liste contient un nombre impair d’éléments, le dernier est ignoré.

λ> twoByTwo [1..10]
[(1,2),(3,4),(5,6),(7,8),(9,10)]
λ> twoByTwo [1..11]
[(1,2),(3,4),(5,6),(7,8),(9,10)]

La fonction intersperse du module Data.List insère un élément entre chaque paire d’éléments consécutifs d’une liste. Définir, avec son type, une fonction intersperse' ayant le même comportement.

λ> intersperse' 0 [1,2,3,4]
[1,0,2,0,3,0,4]
λ> intersperse' 0 []
[]

La fonction intercalate du module Data.List insère une liste entre les listes d’une liste de listes, puis concatène le résultat. Définir, avec son type, une fonction intercalate' ayant le même comportement.

λ> intercalate' [0] [[1,2],[3,4],[5]]
[1,2,0,3,4,0,5]
λ> intercalate' [0] []
[]

La fonction zip associe deux listes élément par élément pour former une liste de paires. Si les listes n’ont pas la même longueur, elle s’arrête lorsque la plus courte est terminée. Définir, avec son type, une fonction zip' ayant le même comportement que zip.

λ> zip' [1,2,3] [9,8,7]
[(1,9),(2,8),(3,7)]
λ> zip' [1,2,3,4,5] [9,8]
[(1,9),(2,8)]

La fonction unzip réalise l’opération inverse de zip : elle prend une liste de paires et la sépare en une paire de listes. Définir, avec son type, une fonction unzip' ayant le même comportement que unzip.

λ> unzip' [(1,2),(2,3),(3,4)]
([1,2,3],[2,3,4])

La fonction intersect du module Data.List conserve les éléments de la première liste qui sont présents dans la seconde liste. Définir, avec son type, une fonction intersect' ayant le même comportement pour des listes d’entiers.

λ> intersect' [1,2,3,4] [5,4,3]
[3,4]
λ> intersect' [1,1,2,2,3,3,4,4] [5,4,3]
[3,3,4,4]