TP 03 - Typage

Programmation fonctionnelle

Comprendre le système de types

Exercice 1.1 - Inférence de type

L’inférence de type est la capacité à déterminer automatiquement le type d’une expression ou d’une fonction, sans qu’on ait besoin de l’écrire.

Il s’agit pour le compilateur de trouver le type le plus général que puisse prendre l’expression. Les avantages à disposer de ce mécanisme sont multiples : le code source est plus aéré, le développeur n’a pas à se soucier de retenir les noms de types, l’interpréteur fournit un moyen au développeur de vérifier (en partie) le code qu’il a écrit et le programme est peu modifié en cas de changement de structure de données. Les expressions restent les plus générales possibles — l’inférence de types va de pair avec le polymorphisme, puisque le compilateur génère des types abstraits (comme a -> a) au besoin. Enfin, le compilateur, lui, dispose de toutes les informations de type, il y a un typage fort et statique, ce qui lui permet de produire du code plus sûr et plus efficace (Wikipédia).

Haskell est capable de faire de l’inférence de type, il n’est donc en réalité pas nécessaire d’indiquer les types des expressions/fonctions que vous définissez. C’est malgré tout une bonne pratique de le faire pour les fonctions (si vous ne savez pas à l’avance quel est le type de la fonction que vous allez définir, il est peu probable que votre définition soit correcte).

Ceci étant dit, ici, le type n’est volontairement pas indiqué : l’exercice consiste justement à le “deviner”.

Pour chacune des expressions suivantes, essayez d’inférer le type le plus général possible puis vérifiez avec l’interpréteur.

1. Expressions simples

1

2.3

pi

True

[]

[1]

(1)

(1, 2)

2. Calculs

21 + 2 * 31

mod 11 2

pi * 12

42 `mod` 2 == 0

3. Fonctions.

   Quelques indications sur la méthode à appliquer :

   • Identifier les arguments et le résultat de la fonction.
   • Examiner les opérations utilisées dans le corps.
   • Déduire les égalités nécessaires entre les types et les contraintes imposées par ces opérations.
   • Construire la signature la plus générale satisfaisant toutes ces contraintes.

log

round

isBig x = x > 100

myAdd x y = x + y

myAdd' x y = if x == 0 then y else succ (myAdd' (pred x) y)

nextSyracuse n = if even n then n `div` 2 else 3 * n + 1

syracuse n = if n == 1 then 0 else 1 + syracuse (nextSyracuse n)

countSetBits number
  | number == 0 = 0
  | even number = countSetBits (number `div` 2)
  | otherwise   = 1 + countSetBits (number `div` 2)

4. Ovnis

(/= 0)

\x -> if even x then "Pair" else "Impair"

Exercice 1.2 - Nouvelles fonctions

1. Définir, avec son type (le plus général possible), une fonction isIncreasing qui teste si les éléments d’une liste sont en ordre croissant.

λ> isIncreasing [1,2,2,4]
True
λ> isIncreasing [1,3,2]
False
λ> isIncreasing []
True

2. Définir, avec son type (le plus général possible), une fonction uniques qui retire les doublons d’une liste. Lorsqu’un élément apparaît plusieurs fois, seule sa dernière occurrence est conservée.

λ> uniques [1,2,1,3,2]
[1,3,2]
λ> uniques "abracadabra"
"cdbra"

3. Définir, avec son type (le plus général possible), une fonction unzipParity qui prend une liste de nombres, puis renvoie une paire de listes telle que la première contient les nombres pairs et la seconde les nombres impairs.

λ> unzipParity [1,2,3,4,5,6]
([2,4,6],[1,3,5])
λ> unzipParity [1,2,1,2,2,2]
([2,2,2,2],[1,1])

4. Définir, avec son type (le plus général possible), une fonction runs qui découpe une liste en sous-listes croissantes maximales. Une sous-liste croissante maximale ne peut pas être prolongée avec l’élément suivant de la liste.

λ> runs [1,2,2,1,3,0]
[[1,2,2],[1,3],[0]]
λ> runs [1,2,3,4]
[[1,2,3,4]]
λ> runs []
[]

5. Définir, avec son type (le plus général possible), une fonction runsAndSizes qui découpe une liste en sous-listes croissantes maximales, comme runs. Chaque sous-liste doit être associée à sa taille dans une paire (taille, run).

λ> runsAndSizes [1,2,2,1,3,0]
[(3,[1,2,2]),(2,[1,3]),(1,[0])]
λ> runsAndSizes [1,2,3,4]
[(4,[1,2,3,4])]
λ> runsAndSizes [4,3,2]
[(1,[4]),(1,[3]),(1,[2])]
λ> runsAndSizes []
[]

6. Définir, avec son type, une fonction contains qui prend deux chaînes de caractères et teste si la première apparaît dans la seconde.

Indication : qu’auriez-vous fait, dans un style impératif ?

λ> contains "askell" "Haskell"
True
λ> contains "Hsk" "Haskell"
False
λ> contains "hello" "Hello"
False
λ> contains "" "Haskell"
True
λ> contains "Haskell" ""
False