Cours 04 : Fonctions d'ordre supérieur

En Haskell, les fonctions peuvent

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

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

:opt no-lint

Premiers exemples (en TP)

applyTwice f x = f (f x)

combine f (x,y) = f x y

-- f x = if x > 10 then 0 else x
-- detectZero f 1

-- numberOf even 10

-- makeDividePredicate 3

Lambdas

Comme en Java, les lambda expressions sont des fonctions anonymes utilisées lorsqu’on a besoin d’une fonction à usage unique.

Pour créer une lambda, on écrit un \ (parce que ça ressemble à la lettre grecque $\lambda$), puis les paramètres, séparés par des espaces. Puis le corps de la fonction est précédé de ->.

En général on met des parenthèses autour, sinon elle s’étend autant que possible vers la droite.

applyTwice (\x -> x^2) 2

16

combine (\x y -> x + y) (2,3)

5

detectZero (\x -> if x > 10 then 0 else x) 1

11

numberOf (\x -> x `mod` 2 == 0) 10

5

Curryfication

La curryfication consiste à représenter une fonction à plusieurs paramètres comme une succession de fonctions à un seul paramètre. Autrement dit, une fonction à n paramètres est une fonction à un paramètre qui renvoie une fonction à n - 1 paramètres, et ainsi de suite.

En Haskell, la flèche -> est associative à droite. Les trois écritures suivantes désignent donc le même type :

a -> b -> c -> d
a -> (b -> c -> d)
a -> (b -> (c -> d))

add = (+)

:t add

add :: forall a. Num a => a -> a -> a

L’addition est une fonction de deux paramètres qui renvoie leur somme.

add2 x y = x + y

:t add2

add2 :: forall a. Num a => a -> a -> a

add 1 2
add2 1 2

3

3

L’addition est aussi une fonction qui prend une valeur x en paramètre et renvoie une fonction qui prend y en paramètre et renvoie la somme x + y :

add3 x = \y -> x + y

:t add3

add3 :: forall a. Num a => a -> a -> a

add3 1 2

3

Ce qui veut dire que l'on peut écrire ce genre de choses :

f = (+) 1

:t f

f :: forall a. Num a => a -> a

f 2

3

Fonctions d'ordre supérieur classiques pour les listes

filter

filter :: (a -> Bool) -> [a] -> [a]

Elle prend un prédicat p et une liste. filter p xs conserve uniquement les éléments de xs pour lesquels p renvoie True, en préservant leur ordre.

Par exemple, pour conserver les nombres impairs :

filter odd [1, 2, 3]

[1,3]

Pour conserver les chaînes de plus de trois caractères :

filter (\word -> length word > 3) ["Hello", ", ", "World", "!"]

["Hello","World"]

Pour supprimer toutes les occurrences de 3 :

filter (/= 3) [1, 2, 3, 4, 3, 2, 1]

[1,2,4,2,1]

map

map :: (a -> b) -> [a] -> [b]

La fonction map prend une fonction f de type a -> b et une liste d’éléments de type a. Elle applique f à chaque élément et renvoie une liste de résultats de type b, en conservant leur ordre.

map f [x1, x2, ..., xn] == [f x1, f x2, ..., f xn]

Par exemple, pour ajouter 1 à chaque élément :

map (+1) [1..10]

[2,3,4,5,6,7,8,9,10,11]

map even [1..10]

[False,True,False,True,False,True,False,True,False,True]

map ('-':) ["un", "deux", "trois"]

["-un","-deux","-trois"]

On peut aussi passer une expression lambda à map :

map (\n -> 3 * n + 1) [1, 2, 3]

[4,7,10]

zipWith

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

Elle prend une fonction à deux arguments et deux listes. Elle applique cette fonction aux éléments de même position et renvoie la liste des résultats :

zipWith f [x1, x2, x3] [y1, y2, y3]
-- [f x1 y1, f x2 y2, f x3 y3]

Par exemple, pour additionner les éléments deux à deux :

zipWith (+) [1, 2, 3] [4, 5, 6]

[5,7,9]

Ou pour concaténer des chaînes de caratères :

zipWith (++) ["hello ", "foo"] ["world!", "bar"]

["hello world!","foobar"]

Si les listes ont des longueurs différentes, le traitement s’arrête à la fin de la plus courte :

zipWith (*) [1, 2, 3] [10, 20]

[10,40]

Les deux listes peuvent contenir des éléments de types différents :

zipWith (\name score -> name ++ " : " ++ show score) ["Alice", "Bob"] [14, 12]

["Alice : 14","Bob : 12"]

partition

partition :: (a -> Bool) -> [a] -> ([a], [a])

Elle prend un prédicat et une liste. Elle renvoie un couple de listes :

• la première contient les éléments qui satisfont le prédicat ;
• la seconde contient ceux qui ne le satisfont pas.

L’ordre des éléments est conservé dans chaque liste.

Par exemple, pour séparer les nombres pairs et impairs :

partition even [1, 2, 3, 4, 5, 6]

([2,4,6],[1,3,5])

Pour séparer les nombres strictement inférieurs à 5 des autres :

partition (< 5) [7, 2, 5, 1, 8]

([2,1],[7,5,8])

Contrairement à filter, qui conserve uniquement les éléments satisfaisant le prédicat, partition fournit également ceux pour lesquels le prédicat est faux.

Cette fonction doit être importée : import Data.List (partition)

concatMap

concatMap :: (a -> [b]) -> [a] -> [b]

Elle prend en paramètre une fonction qui transforme chaque élément en une liste. Elle applique cette fonction à tous les éléments d'une liste, puis concatène les listes obtenues :

concatMap f [x1, x2, x3]
-- f x1 ++ f x2 ++ f x3

Par exemple, pour répéter chaque élément deux fois :

concatMap (\value -> [value, value]) [1, 2, 3]

[1,1,2,2,3,3]

Chaque élément peut produire un nombre différent de résultats, y compris aucun :

concatMap (\count -> replicate count '*') [2, 0, 3]

"*****"

On peut filter certains éléments :

concatMap (\x -> if even x then [x] else []) [1,2,3,4]

[2,4]

On peut l’appliquer à n’importe quel type de liste :

concatMap (take 3) [[1..], [10..], [100..], [1000..]]

[1,2,3,10,11,12,100,101,102,1000,1001,1002]

Au sujet du type…

:t concatMap

concatMap :: forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]

Folding

foldr combine les éléments d’une liste avec une fonction et une valeur initiale.

foldr :: (a -> b -> b) -> b -> [a] -> b

Elle prend 3 paramètres :

• une fonction qui combine un élément de type a avec un résultat partiel de type b pour renvoyer une nouvelle valeur de type b ;
• une valeur initiale de type b, utilisée pour la liste vide ;
• une liste d’éléments de type a.

Elle est définie ainsi :

foldr f acc []     = acc
foldr f acc (x:xs) = f x (foldr f acc xs)

Ou encore :

foldr f acc xs = go xs
  where 
    go []     = acc
    go (x:xs) = f x (go xs)

Elle reproduit le schéma récursif classique sur les listes

sum []     = 0
sum (x:xs) = (+) x (sum xs)

Elle réduit une liste à une unique valeur par une opération binaire de droite à gauche. Les opérations sont associées à droite, d’où le nom fold right.

foldr f z [x1, x2, ..., xn] == f x1 (f x2  ... (f xn z)...)

Par exemple, pour additionner :

foldr (+) 0 [1,2,3] 
-- 1 + (2 + (3 + 0))

6

Ou parcourir une liste :

foldr (:) [] [1,2,3] 
-- 1 : (2 : (3 : []))

[1,2,3]

Voici quelques exemples classiques :

map'' ::  (a -> b) -> [a] -> [b]
map'' f xs = foldr (\x acc -> f x : acc) [] xs

concat' :: [[a]] -> [a]
concat' xss = foldr (++) [] xss

and' :: [Bool] -> Bool
and' xs = foldr (&&) True xs

or' :: [Bool] -> Bool
or' xs = foldr (||) False xs

sum' :: Num a => [a] -> a
sum' xs = foldr (+) 0 xs

-- liste non vide
maximum' :: Ord a => [a] -> a
maximum' (x:xs) = foldr max x xs

Il existe plusieurs variantes, notamment foldl qui traite les opérations de gauche à droite, mais nous ne les verrons pas dans ce cours.