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 son type, puis vérifier avec l’interpréteur.

1. 21 + 2
2. (+) 21 2
3. 21 + 2 * 3
4. (+) 21 (2*3)
5. (+) 21 ((*) 2 3)
6. 1 == 2
7. 1 /= 2
8. 1 + (-1)
9. div 11 2
10. 11 `div` 2
11. 42 `mod` 2 == 0
12. even 42
13. odd 42
14. pred 42
15. sqrt 49

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

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

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

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

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

3. É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.

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

λ> myAdd 5 8
13

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

λ> myMinimum 5.0 8.1
5.0

3. 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

4. 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

5. 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

   2. 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

6. (Optionnel) 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

7. On veut définir une fonction detectZero qui prend en paramètre une fonction \(f\) et un entier \(x0\) et retourne le plus petit entier \(x\geq x0\) tel que \(f(x)\) vaut \(0\). Quel est son type ? Définir (avec son type) la fonction detectZero.

λ> f x = if x > 10 then 0 else x
λ> detectZero f 1
11
λ> g x = x `mod` 7
λ> detectZero g 1
7

8. On appelle prédicat une fonction qui prend un paramètre et renvoie un booléen. On dit qu’un paramètre vérifie le prédicat si ce dernier renvoie True pour le paramètre. La fonction isPrime est un prédicat sur les entiers. On veut définir une fonction numberOf qui prend en paramètre un prédicat et un entier \(n\) et qui compte le nombre d’entiers compris entre \(1\) et \(n\) (inclus) qui vérifient le prédicat. Quel est son type ? Définir (avec son type) la fonction numberOf.

λ> numberOf even 10
5
λ> numberOf isPrime 8
4

9. Un opérateur unaire de type t est une fonction qui prend en paramètre une valeur de type t et renvoie une (autre) valeur de type t. Définir (avec son type) une fonction go qui, étant donné un opérateur unaire entier et un entier, renvoie le nombre de fois qu’il faut appliquer l’opérateur pour obtenir 1. Utiliser ensuite cette fonction pour définir une fonction syracuse' qui fait la même chose que syracuse.

λ> go pred 8
7
λ> syracuse' 14
17

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 = ...

10. Utiliser where pour ré-écrire la fonction syracuse' de la question précédente avec une définition locale pour go.

11. On veut définir une fonction makeDividePredicate qui prend en paramètre un entier \(d\) et renvoie un prédicat qui vérifie si un entier \(n\) est divisible par \(d\). Quel est son type ? Définir (avec son type) la fonction makeDividePredicate. On suppose ici que \(d>0\).

λ> p = makeDividePredicate 3
λ> p 5
False
λ> p 6
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.

1. Définir numberOf' avec des gardes.

2. 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.

1. 'a'
2. "abc"
3. []
4. ['a']
5. ['a', 'b']
6. ["abc", "def"]
7. ['a', "abc"]
8. ('a', 'b')
9. ('a', "abc")
10. ('a', "abc", 1)
11. [odd, even]
12. [odd, even, (==) 1]
13. [odd, even, mod]
14. (odd, even, mod)

Exercice 2.2 - Fonctions sur les listes

1. 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]

2. 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]

3. 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]

4. 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.

λ> 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]

5. 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.

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

6. 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)]

7. 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] []
[]

9. 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)]

10. 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])

11. 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]