TP 04 - Fonctions d’ordre supérieur

Programmation fonctionnelle

Prendre une fonction en paramètre, retourner une fonction

En Haskell, les fonctions peuvent

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 ?

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

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

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]
  1. 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]
  1. 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"]
  1. 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]
  1. 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')]
  1. 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 (\x y -> even x /= even y) [1,2,5,8]
True
  1. 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. 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),("Duncan",4)]
(["Chani","Leto","Duncan"],[14,12,4])
  1. Définir une fonction applyAll qui prend une liste de fonctions et une valeur, puis renvoie la liste des résultats obtenus en appliquant chaque fonction à cette valeur. L’ordre des fonctions doit être conservé.
λ> applyAll [(+1),(*2),(^2)] 3
[4,6,9]
λ> applyAll [even,(> 5),(==3)] 3
[False,False,True]
  1. 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]
  1. Définir une fonction positionsWhere qui prend un prédicat et une liste, puis renvoie, dans l’ordre croissant, les indices des éléments qui satisfont le prédicat. Les indices commencent à zéro.
λ> positionsWhere even [7,4,9,2]
[1,3]
λ> positionsWhere (> 10) [1,2,3]
[]
λ> positionsWhere (== 'a') "banana"
[1,3,5]

Indication : la fonction zip peut s’avérer très utile ici.

  1. 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"
  1. 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 :

λ> isValid' (<) [1,3,5,8]
True
λ> isValid' (<) [1,3,3,8]
False
  1. 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.

λ> nubBy' (==) [1,2,1,3,2,1]
[1,2,3]
λ> nubBy' (\x y -> x `mod` 3 == y `mod` 3) [0,2,1,5,3,4]
[0,2,1]
λ> nubBy' (\x y -> length x == length y) ["chat","le","dort","ici","un"]
["chat","le","ici"]
  1. Définir une fonction cartesianWith qui prend une fonction à deux arguments et deux listes, puis applique cette fonction à toutes les paires formées d’un élément de la première liste et d’un élément de la seconde. Pour chaque élément de la première liste, parcourir tous les éléments de la seconde, dans leur ordre d’apparition.
λ> cartesianWith (,) [1,2] "ab"
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]
λ> cartesianWith (+) [1,2] [10,20,30]
[11,21,31,12,22,32]

Indication : vous allez avoir besoin, à la fois, de map et concatMap.

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 concatMap'' qui fonctionne comme concatMap.

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

  3. Définir une fonction anyMatch qui prend un prédicat et une liste, puis teste si au moins un élément satisfait le prédicat. Pour une liste vide, elle renvoie False.

λ> anyMatch even [1,3,4,7]
True
λ> anyMatch even [1,3,7]
False
λ> anyMatch (> 10) [1..]
True

Notez que le dernier appel peut renvoyer un résultat alors que la liste est infinie…

  1. Définir une fonction countAndSum qui prend un prédicat et une liste de nombres, puis renvoie un couple contenant le nombre d’éléments satisfaisant le prédicat et leur somme. Utiliser un seul appel à foldr.
λ> countAndSum (> 0) [2,-1,4,0]
(2,6)
λ> countAndSum even [1,2,3,4,5,6]
(3,12)

Indication : vous pouvez commencer par une version sans le prédicat.

  1. Définir une fonction groupRuns qui regroupe les éléments identiques consécutifs d’une liste en sous-listes non vides. L’ordre des éléments doit être conservé. Deux occurrences identiques séparées par un élément différent appartiennent à des groupes distincts.
λ> groupRuns [1,1,2,3,3,3,1]
[[1,1],[2],[3,3,3],[1]]
λ> groupRuns "aaabbcaa"
["aaa","bb","c","aa"]
  1. Définir une fonction composeAll qui prend une liste de fonctions et renvoie leur composée. L’appel composeAll [f,g,h] x doit calculer f (g (h x)) : la dernière fonction de la liste est donc appliquée en premier. Pour une liste vide, la fonction obtenue renvoie son argument sans le modifier.
λ> composeAll [(+1),(*2)] 3
7
λ> composeAll [(*2),(+1)] 3
8
λ> composeAll [(+1),(*2),(+1),(*2)] 3
15