Tutoriel pour apprendre le langage Scala par l'exemple


précédentsommairesuivant

5. Fonctions de première classe

En Scala, une fonction est une « valeur de première classe ». Comme n'importe quelle autre valeur, elle peut être passée en paramètre ou renvoyée comme résultat. Les fonctions qui prennent en paramètres d'autres fonctions ou qui les renvoient comme résultat sont appelées fonction d'ordre supérieur. Ce chapitre présente ces fonctions d'ordre supérieur et montre qu'elles constituent un mécanisme souple et puissant pour la composition des programmes.

À titre d'exemple, considérons ces trois tâches apparentées :

  • écrire une fonction additionnant tous les entiers compris entre deux bornes a et b :
 
Sélectionnez
def sumInts(a: Int, b: Int): Int =
 if (a > b) 0 else a + sumInts(a + 1, b)
  • écrire une fonction additionnant les carrés de tous les entiers compris entre deux bornes a et b :
 
Sélectionnez
def square(x: Int): Int = x * x
def sumSquares(a: Int, b: Int): Int =
    if (a > b) 0 else square(a) + sumSquares(a + 1, b)
  • écrire une fonction additionnant les puissances de 2 de tous les entiers compris entre deux bornes a et b :
 
Sélectionnez
1.
2.
3.
def powerOfTwo(x: Int): Int = if (x == 0) 1 else 2 * powerOfTwo(x - 1)
def sumPowersOfTwo(a: Int, b: Int): Int =
    if (a > b) 0 else powerOfTwo(a) + sumPowersOfTwo(a + 1, b)

Ces fonctions étant toutes des instances de

kitxmlcodelatexdvp\sum\limits_{n=a}^{b} f(n)finkitxmlcodelatexdvp

(« Somme de f(n) pour n variant de a à b »), nous pouvons mettre ce motif commun en facteur en définissant une fonction sum :

 
Sélectionnez
def sum(f: Int => Int, a: Int, b: Int): Int =
    if (a > b) 0 else f(a) + sum(f, a + 1, b)

Le type Int => Int est celui des fonctions qui prennent un paramètre de type Int et qui renvoient un résultat de type Int. sum est donc une fonction qui prend en paramètre une autre fonction - autrement dit, c'est une fonction d'ordre supérieur.

Grâce à elle, nous pouvons reformuler nos trois fonctions précédentes de la façon suivante :

 
Sélectionnez
1.
2.
3.
def sumInts(a: Int, b: Int): Int = sum(id, a, b)
def sumSquares(a: Int, b: Int): Int = sum(square, a, b)
def sumPowersOfTwo(a: Int, b: Int): Int = sum(powerOfTwo, a, b)

avec :

 
Sélectionnez
1.
2.
3.
def id(x: Int): Int = x
def square(x: Int): Int = x * x
def powerOfTwo(x: Int): Int = if (x == 0) 1 else 2 * powerOfTwo(x - 1)

5-1. Fonctions anonymes

Le fait de passer des fonctions en paramètre pousse à créer de nombreuses petites fonctions. Dans l'exemple précédent, nous avons défini id, square et powerOfTwo comme des fonctions séparées afin de pouvoir les passer en paramètre à sum.

Au lieu d'utiliser des définitions de fonctions nommées pour ces paramètres, nous pouvons les formuler plus simplement à l'aide de fonctions anonymes. Une fonction anonyme est une expression dont l'évaluation produit une fonction - cette fonction est définie sans qu'on lui donne un nom. À titre d'exemple, voici une fonction anonyme qui calcule le carré d'un entier :

 
Sélectionnez
(x: Int) => x * x

La partie située avant la flèche => est la liste des paramètres de la fonction, la partie située après est son corps. Voici une fonction anonyme qui multiplie ses arguments :

 
Sélectionnez
(x: Int, y: Int) => x * y

Grâce aux fonctions anonymes, nous pouvons reformuler les deux premières fonctions de sommation sans utiliser de fonctions auxiliaires nommées :

 
Sélectionnez
def sumInts(a: Int, b: Int): Int = sum((x: Int) => x, a, b)
def sumSquares(a: Int, b: Int): Int = sum((x: Int) => x * x, a, b)

Le plus souvent, le compilateur Scala peut déduire les types des paramètres à partir du contexte de la fonction anonyme, auquel cas ceux-ci peuvent être omis. Pour sumInts et sumSquares, par exemple, le type de sum nous indique que le premier paramètre doit être une fonction de type Int => Int. Le type Int du paramètre de la fonction anonyme est donc redondant et peut être omis. En outre, lorsqu'il n'y a qu'un seul paramètre et que l'on ne précise pas le type, nous pouvons également supprimer les parenthèses qui l'entourent :

 
Sélectionnez
def sumInts(a: Int, b: Int): Int = sum(x => x, a, b)
def sumSquares(a: Int, b: Int): Int = sum(x => x * x, a, b)

Généralement, le terme Scala (x1: T1, …, xn: Tn) => E définit une fonction qui fait correspondre à ses paramètres x1, …, xn le résultat de l'expression E (où E peut utiliser x1, …, xn). Les fonctions anonymes ne sont pas des éléments de langage essentiels de Scala, car elles peuvent toujours s'exprimer en termes de fonctions nommées. La fonction anonyme

 
Sélectionnez
(x1: T1, ..., xn: Tn) => E

est équivalente au bloc

 
Sélectionnez
{ def f (x1: T1, ..., xn: Tn) = E ; f _ }

f est un nouveau nom qui n'est utilisé nulle part ailleurs dans le programme. On dit aussi que les fonctions anonymes sont du « sucre syntaxique ».

5-2. Curryfication

Notre dernière formulation des fonctions de sommation est déjà très compacte, mais nous pouvons faire mieux. Vous remarquerez que a et b apparaissent comme paramètres et arguments de chaque fonction, mais qu'ils ne semblent pas faire grand-chose d'intéressant. Peut-on donc s'en débarrasser ?

Réécrivons sum pour qu'elle ne prenne pas les bornes a et b en paramètre :

 
Sélectionnez
1.
2.
3.
4.
5.
def sum(f: Int => Int): (Int, Int) => Int = {
    def sumF(a: Int, b: Int): Int =
        if (a > b) 0 else f(a) + sumF(a + 1, b)
    sumF
}

Ici, sum est une fonction qui renvoie une autre fonction, celle qui effectue la somme : sumF. C'est cette dernière qui fait tout le travail : elle prend les bornes a et b en paramètre, elle applique la fonction f qui a été passée à sum à tous les entiers compris entre ces bornes et additionne les résultats.

Grâce à cette nouvelle formulation de sum, nous pouvons maintenant écrire :

 
Sélectionnez
1.
2.
3.
def sumInts = sum(x => x)
def sumSquares = sum(x => x * x)
def sumPowersOfTwo = sum(powerOfTwo)

Ou, avec des définitions de valeurs :

 
Sélectionnez
1.
2.
3.
val sumInts = sum(x => x)
val sumSquares = sum(x => x * x)
val sumPowersOfTwo = sum(powerOfTwo)

On peut maintenant appliquer sumInts, sumSquares et sumPowersOfTwo comme n'importe quelle autre fonction :

 
Sélectionnez
scala> sumSquares(1, 10) + sumPowersOfTwo(10, 20)
res0: Int = 2096513

Comment appliquer des fonctions qui renvoient des fonctions ? Dans l'expression sum(x => x * x)(1, 10), par exemple, la fonction sum peut s'appliquer à la fonction carré (x => x * x) et la fonction résultante est ensuite appliquée à la seconde liste de paramètres (1, 10). Cette notation est possible, car l'application des fonctions est associative à gauche : si arg1 et arg2 forment une liste d'arguments, alors f(arg11)(arg22) est équivalent à (f(arg1))(arg2).

Dans notre exemple, sum(x => x * x)(1, 10) est donc équivalent à (sum(x => x * x))(1, 10).

Les fonctions qui renvoient des fonctions sont si utiles que Scala dispose d'une syntaxe spéciale pour les exprimer. La définition suivante de sum, par exemple, est équivalente à la précédente, mais est plus courte :

 
Sélectionnez
def sum(f: Int => Int)(a: Int, b: Int): Int =
    if (a > b) 0 else f(a) + sum(f)(a + 1, b)

De façon générale, une définition de fonction curryfiée :

 
Sélectionnez
f (params_1) ... (params_n) = E

dans laquelle n > 1 se traduit en :

 
Sélectionnez
def f (params_1) ... (params_n-1) = { def g (params_n) = E ; g }

g est un nouvel identificateur. Avec une fonction anonyme, cette traduction est encore raccourcie :

 
Sélectionnez
def f (params_1) ... (params_n −1) = ( params_n ) => E

Si l'on applique n fois cette transformation, on trouve donc que :

 
Sélectionnez
def f (params_1) ... (params_n) = E

équivalaut à :

 
Sélectionnez
def f = (params_1) => ... => (params_n) => E

ou, avec une définition de valeur :

 
Sélectionnez
val f = (params_1) => ... => (params_n) => E

Ce style de définition et d'application des fonctions s'appelle curryfication, en hommage aux travaux du mathématicien et logicien Haskell B. Curry dans les années 1930 - bien que ce concept remonte plus loin aux articles de Moses Schönfinkel et Gottlob Frege.

Le type d'une fonction renvoyant une fonction s'exprime de façon analogue à sa liste de paramètres. Le type de la dernière formulation de sum, par exemple, est (Int => Int) => (Int, Int) => Int. Cette écriture est possible, car les types des fonctions sont associatifs à droite : T1 => T2 => T3 est donc équivalent à T1 => (T2 => T3).

Exercice 5-2-1 : La fonction sum utilise une récursion linéaire. Écrivez une version récursive terminale en remplaçant les ?? dans le code ci-dessous :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
def sum(f: Int => Int)(a: Int, b: Int): Int = {
    def iter(a: Int, result: Int): Int = {
        if (??) ??
        else iter(??, ??)
    }
    iter(??, ??)
}

Exercice 5-2-2 : Écrivez une fonction product qui calcule le produit des valeurs d'une fonction pour les points appartenant à un certain intervalle.

Exercice 5-2-3 : Écrivez factorielle en termes de product.

Exercice 5-2-4 : Pouvez-vous écrire une fonction encore plus générale, qui généralise à la fois sum et product ?

5-3. Exemple : Trouver les points fixes des fonctions

Un nombre x est appelé point fixe d'une fonction f si f(x) = x.

Pour certaines fonctions f, nous pouvons trouver le point fixe en commençant par une valeur supposée et en appliquant f jusqu'à ce que cette valeur ne change plus (ou que la modification soit inférieure à un seuil de tolérance donné). Ceci est possible si la suite

 
Sélectionnez
x, f(x), f(f(x)), f(f(f(x))), ...

converge vers le point fixe de f. Ce principe est capturé par la fonction suivante :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
val tolerance = 0.0001
def isCloseEnough(x: Double, y: Double) = abs((x - y) / x) < tolerance
def fixedPoint(f: Double => Double)(firstGuess: Double) = {
    def iterate(guess: Double): Double = {
        val next = f(guess)
        if (isCloseEnough(guess, next)) next
        else iterate(next)
    }
    iterate(firstGuess)
}

Nous pouvons maintenant appliquer ce principe pour reformuler la fonction racine carrée que nous avions étudiée précédemment. Commençons par spécifier sqrt :

 
Sélectionnez
sqrt(x) = y tel que y * y = x
        = y tel que y = x /y

Par conséquent, sqrt(x) est un point fixe de la fonction y => x / y. Ceci suggère qu'elle peut être calculée à l'aide de fixedPoint :

 
Sélectionnez
def sqrt(x: double) = fixedPoint(y => x / y)(1.0)

Cependant, nous constatons alors que ce calcul ne converge pas. Ajoutons à la fonction fixedPoint une instruction d'impression affichant la supposition courante :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
def fixedPoint(f: Double => Double)(firstGuess: Double) = {
    def iterate(guess: Double): Double = {
        val next = f(guess)
        println(next)
        if (isCloseEnough(guess, next)) next
        else iterate(next)
    }
    iterate(firstGuess)
}

L'appel sqrt(2) produit alors :

 
Sélectionnez
2.0
1.0
2.0
1.0
2.0
...

Un moyen de contrôler ces oscillations consiste à empêcher la supposition de trop changer. Ceci peut se faire en calculant la moyenne des valeurs successives de la suite initiale :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
scala> def sqrt(x: Double) = fixedPoint(y => (y + x/y) / 2)(1.0)
sqrt: (Double)Double

scala> sqrt(2.0)
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
1.4142135623746899

En fait, la traduction de la fonction fixedPoint produirait exactement notre définition précédente du point fixe de la section 4.4Exemple : racines carrées par la méthode de Newton.

Les exemples précédents ont montré que la puissance expressive d'un langage s'améliore considérablement lorsque l'on peut passer des fonctions en paramètre. L'exemple suivant montre que les fonctions qui renvoient des fonctions peuvent également être très utiles.

Reprenons à nouveau nos itérations pour trouver le point fixe. Nous sommes partis de l'observation que (x) est un point fixe de la fonction y => x / y. Puis, nous avons fait en sorte que l'itération converge en faisant la moyenne des valeurs successives. Cette technique d'amortissement par la moyenne (average damping) est si générale que nous pouvons l'envelopper dans une autre fonction :

 
Sélectionnez
def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2

Grâce à averageDamp, nous pouvons reformuler la fonction racine carrée :

 
Sélectionnez
def sqrt(x: Double) = fixedPoint(averageDamp(y => x/y))(1.0)

Cette définition exprime aussi clairement que possible les éléments de l'algorithme.

Exercice 5-3-1 : Écrivez une fonction calculant les racines cubiques en vous servant de fixedPoint et de averageDamp.

5-4. Résumé

Nous avions montré dans le chapitre précédent que les fonctions sont des abstractions essentielles, car elles permettent d'introduire des méthodes générales de calcul sous la forme d'éléments explicites et nommés dans le langage. Dans le présent chapitre, nous avons montré que ces abstractions pouvaient être combinées en fonctions d'ordre supérieur afin de créer d'autres abstractions. En tant que programmeurs, nous devons rechercher les opportunités d'abstraction et de réutilisation. Le niveau d'abstraction le plus haut n'est pas toujours le meilleur, mais il est important de connaître les techniques d'abstraction pour pouvoir les utiliser à bon escient.

5-5. Éléments du langage déjà vus

Les chapitres 4 et 5 ont présenté les éléments du langage qui permettent de créer des expressions et des types formés de données primitives et de fonctions. Nous indiquerons ci-dessous la syntaxe sans contexte de ces éléments selon le formalisme Backus-Naur étendu, où | représente une alternative, [ … ] un élément facultatif (0 ou 1 occurrence) et { … } une répétition (0 ou plusieurs occurrences).

5-5-1. Caractères

Les programmes Scala sont des suites de caractères Unicode. Nous distinguons les jeux de caractères suivants :

  • les espaces, comme ' ', la tabulation ou les caractères de fin de ligne ;
  • les lettres de 'a' à 'z' et de 'A' à 'Z' ;
  • les chiffres de '0' à '9' ;
  • les délimiteurs . , ; ( ) { } [ ] \ " ' ;
  • les opérateurs comme '#' '+' ':'. Essentiellement, il s'agit des caractères affichables qui n'appartiennent à aucun des ensembles précédents.

5-5-2. Lexèmes

 
Sélectionnez
ident    = lettre {lettre | chiffre}
         | opérateur { opérateur }
         | ident '_' ident
littéral = "comme en Java"

Les littéraux sont les mêmes qu'en Java. Il définissent des nombres, des caractères, des chaînes ou des valeurs booléennes. Des exemples de littéraux sont 0, 1.0e10, 'x' , "il a dit 'bonjour !'" ou true.

Les identificateurs ont deux formes. Ils peuvent commencer par une lettre suivie (éventuellement) d'une suite de lettres ou de symboles, ou commencer par un caractère opérateur, suivi (éventuellement) d'une suite de caractères opérateurs. Les deux formes peuvent contenir des caractères blanc souligné '_'. En outre, un blanc souligné peut être suivi par une forme ou l'autre d'identificateur. Les identificateurs suivants sont donc corrects :

 
Sélectionnez
x          Room10a       +       --       foldl_:       +_vector

Cette règle signifie que les identificateurs formés d'opérateurs doivent être séparés par des espaces. L'entrée x+-y sera donc analysée comme une séquence de trois lexèmes x, +- et y. Si nous voulons exprimer la somme de x avec l'opposé de y, nous devons ajouter un caractère espace pour écrire, par exemple, x+ -y.

Le caractère $ est réservé pour les identificateurs produits par le compilateur ; ne l'utilisez pas dans les sources de vos programmes.

Les mots suivants sont réservés et ne peuvent donc pas servir d'identificateurs :

 
Sélectionnez
abstract  case     catch      class     def
do        else     extends    false     final
finally   for      if         implicit  import
match     new      null       object    override
package   private  protected  requires  return
sealed    super    this       throw     trait
try       true     type       val       var
while     with     yield
_   :   =   =>   <-   <:   <%   >:   #   @

5-5-3. Types

 
Sélectionnez
Type         = TypeSimple | TypeFonction
TypeFonction = TypeSimple '=>' Type | '('  [Types] ')' '=>'  Type
TypeSimple   = Byte | Short | Char | Int | Long | Float | Double |
               Boolean | Unit | String
Types        = Type {','  Type}

Les types peuvent être :

  • des types numériques : Byte, Short, Char, Int, Long, Float et Double (ce sont les mêmes qu'en Java) ;
  • le type Boolean avec les valeurs true et false ;
  • le type Unit avec la seule valeur () ;
  • le type String ;
  • des types fonctions, comme (Int, Int) => Int ou String => Int => String.

5-5-4. Expressions

 
Sélectionnez
Expr         = ExprInfixe | ExprFonction | if '(' Expr ')' Expr else Expr
ExprInfixe   = ExpPréfixe | ExprInfixe Opérateur ExprInfixe
Opérateur    = ident
ExprPréfixe  = ['+' | '-' | '!' | '~'] ExprSimple
ExprSimple   = ident | littéral | ExprSimple '.' ident | Bloc
ExprFonction = (Liaisons | Id) '=>'  Expr
Liaisons     = '(' Laison {',' Liaison} ')'
Liaison      = ident [':'  Type]
Bloc         = '{' {Def ';' } Expr '}'

Les expressions peuvent être :

  • des identificateurs comme x, isGoodEnough, * ou +- ;
  • des littéraux comme 0, 1.0 ou "abc" ;
  • des sélections de champs ou de méthodes comme System.out.println ;
  • des appels de fonctions comme sqrt(x) ;
  • des applications d'opérateurs comme -x ou y + x ;
  • des conditionnelles comme if (x < 0) -x else x ;
  • des blocs comme { val x = abs(y) ; x * 2 } ;
  • des fonctions anonymes comme x => x + 1 ou (x: Int, y: Int) => x + y.

5-5-5. Définitions

 
Sélectionnez
Def         = DefFonction | DefValeur
DefFonction = 'def' ident {'(' [Paramètres] ')'} [':' Type] '=' Expr
DefValeur   = 'val' ident [':' Type] '=' Expr
Paramètres  = Paramètre {',' Paramètre}
Paramètre   = ident ':' ['=>'] Type

Les définitions peuvent être :

  • des définitions de fonctions comme def square(x: Int): Int = x * x ;
  • des définitions de valeurs comme val y = square(2).

précédentsommairesuivant

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2017 Martin Odersky. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.