Haskell Language
Fonctions d'ordre supérieur

Remarques

Principes de base des fonctions d'ordre supérieur

Passez en revue l' application partielle avant de continuer.

Dans Haskell, une fonction pouvant prendre d'autres fonctions comme arguments ou fonctions de retour est appelée fonction d'ordre supérieur .

Toutes les fonctions d'ordre supérieur sont les suivantes :

map       :: (a -> b) -> [a] -> [b]
filter    :: (a -> Bool) -> [a] -> [a]
takeWhile :: (a -> Bool) -> [a] -> [a]
dropWhile :: (a -> Bool) -> [a] -> [a]
iterate   :: (a -> a) -> a -> [a]
zipWith   :: (a -> b -> c) -> [a] -> [b] -> [c]
scanr     :: (a -> b -> b) -> b -> [a] -> [b]
scanl     :: (b -> a -> b) -> b -> [a] -> [b]

Celles-ci sont particulièrement utiles car elles nous permettent de créer de nouvelles fonctions par-dessus celles que nous avons déjà, en passant des fonctions comme arguments à d'autres fonctions. D'où le nom, les fonctions d'ordre supérieur .

Considérer:

Prelude> :t (map (+3))
(map (+3)) :: Num b => [b] -> [b]

Prelude> :t (map (=='c'))
(map (=='c')) :: [Char] -> [Bool]

Prelude> :t (map zipWith)
(map zipWith) :: [a -> b -> c] -> [[a] -> [b] -> [c]]

Cette capacité à créer facilement des fonctions (comme par exemple une application partielle telle qu’elle est utilisée ici) est l’une des caractéristiques qui rendent la programmation fonctionnelle particulièrement puissante et nous permet de dériver des solutions courtes et élégantes qui prendraient des dizaines de lignes dans d’autres langues. Par exemple, la fonction suivante nous donne le nombre d'éléments alignés dans deux listes.

aligned :: [a] ->  [a] -> Int
aligned xs ys = length (filter id (zipWith (==) xs ys))

Expressions lambda

Les expressions Lambda sont similaires aux fonctions anonymes dans d'autres langues.

Les expressions lambda sont des formules ouvertes qui spécifient également les variables à lier. L'évaluation (recherche de la valeur d'un appel de fonction) est alors réalisée en substituant les variables liées dans le corps de l'expression lambda aux arguments fournis par l'utilisateur. En termes simples, les expressions lambda nous permettent d'exprimer des fonctions au moyen de la liaison de variables et de la substitution .

Les expressions lambda ressemblent à

\x -> let {y = ...x...} in y

Dans une expression lambda, les variables du côté gauche de la flèche sont considérées comme liées dans la partie droite, c'est-à-dire le corps de la fonction.

Considérons la fonction mathématique

f(x) = x^2

En tant que définition de Haskell, c'est

f    x =  x^2

f = \x -> x^2

ce qui signifie que la fonction f est équivalente à l'expression lambda \x -> x^2 .

Considérons le paramètre de la map fonction d'ordre supérieur, qui est une fonction du type a -> b . Dans le cas où il n'est utilisé qu'une fois dans un appel à map et nulle part ailleurs dans le programme, il convient de le spécifier comme une expression lambda au lieu de nommer une telle fonction. Écrit comme une expression lambda,

\x -> let {y = ...x...} in y

x contient une valeur de type a , ...x... est une expression Haskell qui fait référence à la variable x et y détient une valeur de type b . Ainsi, par exemple, nous pourrions écrire ce qui suit

map (\x -> x + 3)

map (\(x,y) -> x * y)

map (\xs -> 'c':xs) ["apples", "oranges", "mangos"]

map (\f -> zipWith f [1..5] [1..5]) [(+), (*), (-)]

Currying

Dans Haskell, toutes les fonctions sont considérées comme curry: c'est-à-dire que toutes les fonctions de Haskell ne prennent qu'un seul argument.

Prenons la fonction div :

div :: Int -> Int -> Int

Si nous appelons cette fonction avec 6 et 2, nous obtenons sans surprise 3:

Prelude> div 6 2
3

Cependant, cela ne se comporte pas comme nous pourrions le penser. Le premier div 6 est évalué et renvoie une fonction de type Int -> Int . Cette fonction résultante est ensuite appliquée à la valeur 2 qui donne 3.

Lorsque nous regardons la signature de type d'une fonction, nous pouvons changer notre façon de penser de "prend deux arguments de type Int " pour "prend un Int et retourne une fonction qui prend un Int ". Ceci est réaffirmé si l'on considère que les flèches dans la notation de type associent à la droite , donc div peut en fait être lu ainsi:

div :: Int -> (Int -> Int)

En général, la plupart des programmeurs peuvent ignorer ce comportement au moins pendant qu'ils apprennent la langue. D'un point de vue théorique , "les preuves formelles sont plus faciles lorsque toutes les fonctions sont traitées de manière uniforme (un argument, un résultat)."