TP 04 - Fonctions d’ordre supérieur

Programmation fonctionnelle

Prendre une fonction en paramètre, retourner une fonction

En Haskell, les fonctions peuvent

• prendre d’autres fonctions en paramètres,
• renvoyer des fonctions comme valeur de retour.

Une fonction capable de l’une de ces deux choses est une fonction d’ordre supérieur.

Exercice 1 - Premières fonctions d’ordre supérieur

1. On veut créer une fonction applyTwice qui prend une fonction f et une valeur x en paramètre, et applique f à x deux fois de suite :

applyTwice f x = f (f x)

Quel est son type ?

2. On veut créer une fonction combine qui prend en paramètre une fonction f et un couple (x,y) et renvoie f x y :

combine f (x,y) = f x y 

Quel est son type ?

3. 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 >= x0 tel que f x vaut 0. Quel est son type ? Définir 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

4. 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. Les fonctions even et isPrime, par exemple, sont des prédicats 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 la fonction numberOf.

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

5. 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 la fonction makeDividePredicate. On suppose ici que d > 0.

λ> p = makeDividePredicate 3
λ> p 5
False
λ> p 6
True

Exercice 2 — Fonctions d’ordre supérieur sur les listes

Pour chaque question, définir la fonction demandée avec son type, en utilisant la récursivité et du pattern matching (bien sûr, vous ne devez pas utiliser directement la fonction équivalente de la bibliothèque standard).

1. La fonction map de Prelude applique une fonction à chaque élément d’une liste. Définir une fonction map' ayant le même comportement. La fonction appliquée peut changer le type des éléments.

λ> map' (+1) [1,2,3]
[2,3,4]
λ> map' even [1,2,3,4]
[False,True,False,True]
λ> map' length ["Haskell","est","amusant"]
[7,3,7]

2. La fonction filter de Prelude conserve les éléments d’une liste qui satisfont un prédicat, c’est-à-dire une fonction qui renvoie un booléen. Définir une fonction filter' ayant le même comportement. L’ordre des éléments doit être conservé.

λ> filter' even [1,2,3,4,5,6]
[2,4,6]
λ> filter' (>3) [1,5,2,4,3]
[5,4]
λ> filter' (\word -> length word > 3) ["le","chat","dort"]
["chat","dort"]

3. La fonction takeWhile de Prelude conserve les éléments au début d’une liste tant qu’ils satisfont un prédicat. Elle s’arrête dès le premier élément qui ne le satisfait pas. Définir une fonction takeWhile' ayant le même comportement.

λ> takeWhile' even [2,4,5,6,8]
[2,4]
λ> takeWhile' even [1,2,4]
[]
λ> takeWhile' (<5) [1..]
[1,2,3,4]

4. La fonction concatMap de Prelude applique une fonction à chaque élément d’une liste, puis concatène les listes obtenues. Définir une fonction concatMap' ayant le même comportement.

λ> concatMap' (\value -> [value,value]) [1,2,3]
[1,1,2,2,3,3]
λ> concatMap' (replicate 3) "abc"
"aaabbbccc"
λ> concatMap' (take 3) [[1..],[10..],[100..],[1000..]]
[1,2,3,10,11,12,100,101,102,1000,1001,1002]

5. Définir une fonction isValid qui prend une relation entre deux éléments et une liste, puis vérifie que cette relation est satisfaite pour chaque paire d’éléments consécutifs. Une liste vide ou réduite à un élément est considérée comme valide.

λ> isValid (<) [1,3,5,8]
True
λ> isValid (<) [1,3,3,8]
False
λ> isValid (<=) [1,3,3,8]
True
λ> isValid (\first second -> even first /= even second) [1,2,5,8]
True

6. La fonction zipWith de Prelude combine deux listes élément par élément à l’aide d’une fonction à deux arguments. Si les listes n’ont pas la même longueur, elle s’arrête lorsque la plus courte est terminée. Définir une fonction zipWith' ayant le même comportement.

λ> zipWith' (+) [1,2,3] [10,20,30]
[11,22,33]
λ> zipWith' (*) [1,2,3,4] [10,20]
[10,40]
λ> zipWith' (++) ["bon","bon"] ["jour","soir"]
["bonjour","bonsoir"]
λ> zipWith' (,) [1,2,3] "abc"
[(1,'a'),(2,'b'),(3,'c')]

7. La fonction partition du module Data.List sépare une liste en deux listes : la première contient les éléments qui satisfont un prédicat, la seconde ceux qui ne le satisfont pas. Définir une fonction partition' ayant le même comportement. L’ordre des éléments doit être conservé dans chaque liste.

λ> partition' even [1,2,3,4,5,6]
([2,4,6],[1,3,5])
λ> partition' (<3) [5,1,3,2,4]
([1,2],[5,3,4])
λ> partition' (\word -> length word > 3) ["le","chat","dort"]
(["chat","dort"],["le"])

Exercice 3 — Combiner des fonctions d’ordre supérieur

Pour chaque question, définir la fonction demandée avec son type, sans récursivité explicite : vous devez uniquement utiliser les fonctions d’ordre supérieur existantes telles que map, filter, …, mais sans utiliser foldr.

1. Définir une fonction deleteAll' qui prend un entier et une liste d’entiers, puis supprime toutes les occurrences de cet entier. L’ordre des éléments restants doit être conservé.

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

2. 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 une fonction intersperse' ayant le même comportement, y compris sur la liste vide.

λ> intersperse' 0 [1,2,3,4]
[1,0,2,0,3,0,4]
λ> intersperse' ',' "abc"
"a,b,c"
λ> intersperse' 0 [1]
[1]

3. 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 une fonction intercalate' ayant le même comportement, en utilisant intersperse'.

λ> intercalate' [0] [[1,2],[3,4],[5]]
[1,2,0,3,4,0,5]
λ> intercalate' ", " ["Chani","Leto","Duncan"]
"Chani, Leto, Duncan"
λ> intercalate' [0] [[],[1],[]]
[0,1,0]

4. La fonction unzip sépare une liste de paires en une paire de listes : la première contient les premières composantes, la seconde les secondes composantes. Définir une fonction unzip' ayant le même comportement.

λ> unzip' [(1,'a'),(2,'b'),(3,'c')]
([1,2,3],"abc")
λ> unzip' [("Chani",14),("Leto",12)]
(["Chani","Leto"],[14,12])

5. La fonction intersect du module Data.List conserve les éléments de la première liste qui sont présents dans la seconde. Définir une fonction intersect' ayant le même comportement. L’ordre et les occurrences des éléments de la première liste doivent être conservés.

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

6. Définir une fonction isValid' qui prend une relation entre deux éléments et une liste, puis vérifie que cette relation est satisfaite pour chaque paire d’éléments consécutifs. Une liste vide ou réduite à un élément est considérée comme valide.

Proposer deux versions :

• une version utilisant zipWith ;
• une version utilisant zip.

λ> isValid' (<) [1,3,5,8]
True
λ> isValid' (<) [1,3,3,8]
False

7. La fonction nubBy du module Data.List supprime les doublons selon une relation d’équivalence fournie en argument. Définir une fonction nubBy' ayant le même comportement : seule la première occurrence de chaque classe d’équivalence doit être conservée.

Pour cette question, la récursivité est autorisée. Utiliser filter pour retirer les éléments équivalents à l’élément conservé avant de poursuivre récursivement.

λ> nubBy' (==) [1,2,1,3,2,1]
[1,2,3]
λ> nubBy' (\first second -> first `mod` 3 == second `mod` 3) [0,2,1,5,3,4]
[0,2,1]
λ> nubBy' (\first second -> length first == length second) ["chat","le","dort","ici","un"]
["chat","le","ici"]

Exercice 4 — Définir des fonctions avec foldr

Pour chaque question, définir la fonction demandée avec son type, en utilisant foldr, sans récursivité explicite ni appel à la fonction équivalente de la bibliothèque standard.

1. Écrire filter'' qui fonctionne comme filter.

2. Écrire zipWith'' qui fonctionne comme zipWith

3. Écrire concatMap'' qui fonctionne comme concatMap.