Fonctions d’ordre supérieur en Scala

Dans cet article, je vous propose de vous plonger dans l’une des caractéristiques les plus intéressantes de la programmation fonctionnelle et de Scala en particulier : les fonctions d’ordre supérieur !

Qu’est ce qu’une fonction d’ordre supérieur ? C’est une fonction qui prend en argument une ou plusieurs fonctions et/ou qui retourne une fonction. Un exemple courant de fonction d’ordre supérieur en Scala est la fonction map permettant de transformer le contenu d’une liste par exemple :

scala> List(1, 2, 3).map { x => x * 2 }
res0: List[Int] = List(2, 4, 6)

La fonction d’ordre supérieur map prend en argument une fonction f: A => B où A est le type de départ (ici Int) et B le type d’arrivée (ici encore Int). Nous pouvons donc à l’aide de map et d’une fonction transformer une List[A] en List[B]. Les fonctions en Scala sont des first-class-citizen ce qui signifie qu’elles sont des objets (dans notre cas, {x => x * 2} est une instance de Function1) et donc passer une fonction en paramètre revient à passer un objet de type FunctionN.

Fonctions prenant une autre fonction en paramètre

Avant d’écrire notre première fonction d’ordre supérieure, nous allons rappeler comment écrire une fonction en Scala :

scala> def add = { (x:Long, y:Long) =>  x + y } // équivalent à def add(x:Long, y:Long) = x + y
add: (Long, Long) => Long

Cette fonction prend en argument deux entiers et les additionne (notez que le type de retour Long est inféré par le compilateur Scala). Voyons maintenant comment écrire notre fonction d’ordre supérieur :

scala> def operate(x:Long, y:Long, f: (Long, Long) => Long) = f(x, y)
operate: (x: Long, y: Long, f: (Long, Long) => Long)Long
scala> operate(1, 2, add)
res1: Long = 3

Nous pouvons bien entendu remplacer add par toute fonction donc la signature est (Long, Long) => Long.

Il est aussi possible de définir des fonctions d’ordre supérieur génériques :

scala> def apply[A, B](x:A, f: A => B):B = f(x)
apply: [A, B](x: A, f: A => B)B
scala> apply("test", { x:String => x.size })
res2: Int = 4

Nous venons de définir une fonction générique d’ordre supérieur apply prenant en paramètre une valeur x de type A et une fonction f de type A => B. Nous l’utilisons ensuite en lui passant une chaîne de caractères ainsi qu’une fonction anonyme prenant en entrée une String et retournant sa taille Int.

Ces fonctions sont largement présentes dans les API de Scala. On les retrouve notamment dans l’API collection ou encore avec le type Option.

Fonctions retournant une autre fonction

L’autre cas qui va maintenant nous intéresser se rapporte aux fonctions retournant une fonction. Prenons l’exemple suivant :

scala> def inc(step:Int) = { x:Int => x + step }
inc: (step: Int)Int => Int

scala> val incBy10 = inc(10)
incBy10: Int => Int = <function1>

scala> incBy10(5)
res5: Int = 15

La méthode inc prend en argument un Int et retourne une fonction de type Int => Int. Il est possible d’utiliser cette méthode pour créer diverses fonctions (incBy10 …) qui sont ensuite utilisées dans le reste de l’application. Il est intéressant de noter que incBy10(5) est équivalent à incBy10.apply(5). Ce type de fonction d’ordre supérieur peut, par exemple, être utilisée pour implémenter un foobarqix.

Il est aussi possible de retourner des fonctions possédant un état (aussi communément appelé une closure) :

def counter() = {
  var count = 0
  () => { count += 1; count }
}
scala> val count = counter()
count: () => Int = <function0>

scala> count()
res6: Int = 1

scala> count()
res7: Int = 2

La fonction d’ordre supérieur counter retourne une fonction ayant pour état la variable count qui s’incrémente à chaque appel.

Call-by-name

Nous allons maintenant voir l’utilisation particulière d’une fonction d’arité 0 dans une fonction d’ordre supérieur. Une fonction 0-aire est une fonction ne prenant pas d’argument, dont voici un exemple :

scala> def sayHello() = "%s> Hello".format(new Date())
sayHello: ()String
scala> def doSomething(f: () => String):String = f()
doSomething: (f: () => String)String
scala> doSomething( sayHello )
res3: String = Mon Feb 13 09:38:52 CET 2012> Hello

Cette fonction prend en argument une autre fonction (de type () => String) et retourne le résultat de cette dernière. Nous pouvons aussi utiliser une variante appelée call-by-name :

scala> def doSomething(f: => String) = f  // f est une expression retournant une String
doSomething: (f: => String)String
scala> doSomething( sayHello )
res4: String = Mon Feb 13 09:41:25 CET 2012> Hello

Bien, nous avons gagné un peu en concision dans le cas d’utilisation de fonctions 0-aire. What Else ?

Prenons un exemple un peu plus pratique pour illustrer ce concept. Lorsque l’on souhaite avoir des informations sur le déroulement d’une application, nous utilisons généralement un framework de log permettant d’obtenir des informations contextuelles. Cette utilisation est généralement pointée du doigt lors des audits de performance car nous retrouvons généralement du code comme celui-ci :

logger.debug("My object state : " + myObject.toString());

Le problème avec ce code est que même si le niveau de log n’est pas DEBUG, l’évaluation de l’expression "My object state : " + myObject.toString() sera effectuée. La solution est généralement d’utiliser un if(logger.isDebug())… pour l’éviter. Voyons comment résoudre ce problème avec Scala :

object Logger {
  def debug(message: => String) {
    val level = ...
    if (level == DEBUG) { out.println(message) }
    ….
  }
}

Remarquez que message est une fonction qui ne prend pas d’argument et retourne une chaîne. Du coup, l’évaluation de message ici ne sera effective que si le niveau de log est défini a DEBUG et nous n’aurons donc pas d’overhead si l’évaluation n’est pas requise. Un autre exemple de cas d’utilisation de ce type de fonction serait une API de cache.

object Cache {
…
  def get[K](key:K):Option[Any] = …  // get returns either None or Some(value)
  def set[K](key:K, value:Any) = …
  def getOrElse[K,V](key:K, value: => V):V = get(key) match {
    case Some(cached) => value.asInstanceOf[V]
    case None => {
      val result = value   // value expression is evaluated here
      set(result)
      result
    }
  }
}

Cette API nous propose les méthodes get et set permettant respectivement de récupérer une valeur et d’insérer (ou modifier) une paire clé-valeur. Nous disposons aussi d’une méthode getOrElse prenant en argument une clé et une expression. Dans le cas où la clé correspond à une valeur dans le cache, celle-ci sera retournée. Si elle n’existe pas, l’expression value sera évaluée, stockée dans le cache et retournée. Ici encore, le passage de value en call-by-name nous assure que cette expression ne sera évaluée que si elle est utilisée.

Voilà qui termine notre tour d’horizon des fonctions d’ordre supérieur en Scala. Ces fonctions ont la particularité de prendre d’autres fonctions en argument et/ou de retourner une autre fonction. Ces fonctions sont très utilisées dans le monde de la programmation et notamment dans l’API Collection de Scala qui fournit un grand nombre de fonctions d’ordre supérieur permettant d’opérer sur les collections (map, flatMap, fold, filter, groupBy …).