Programmation fonctionnelle
En Haskell, les fonctions peuvent
Une fonction capable de l’une de ces deux choses est une fonction d’ordre supérieur.
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 ?
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 ?
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
TruedetectZero 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
7numberOf 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
4Pour 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).
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]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]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"]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]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')]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]
Truepartition 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"])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.
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])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]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]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.
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"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 :
zipWith ;zip.λ> isValid' (<) [1,3,5,8]
True
λ> isValid' (<) [1,3,3,8]
FalsenubBy 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"]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.
foldrPour 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.
Écrire concatMap'' qui fonctionne comme
concatMap.
Écrire filter'' qui fonctionne comme
filter.
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..]
TrueNotez que le dernier appel peut renvoyer un résultat alors que la liste est infinie…
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.
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"]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