samedi 7 juin 2014

Scala : collections et monades (initiation)

Le but de cet article d’initiation est de présenter à travers des exemples simples quelques unes des possibilités offertes par la programmation fonctionnelle et en particulier par Scala, autour des collections et des monades.


Commençons avec un exemple simple : le tri d’une liste. Dans un style impératif, par exemple en Java(< 8) ou en C, on créerait une nouvelle liste vide, puis on parcourrait la liste d’origine pour ajouter les éléments que l’on souhaite ajouter à la nouvelle liste.
Beaucoup de code fastidieux, répétitif si on a beaucoup de listes à manipuler et surtout sans grand intérêt!
Voici un exemple de code impératif :
List<String> origin = Arrays.asList("john", "jerry", "bob");
List<String> result = new ArrayList<String>();

for (String name: origin){
    if(name.startsWith("j")){
        result.add(name)
    }
}
En réalité seule la condition if(name.startsWith("j")) porte une valeur “métier” dans le code ci dessus.
En Scala on préfère se focaliser sur l’essentiel, en écrivant le code suivant :
val origin = List("john", "jerry", "bob")
val result = origin.filter(name => name.startsWith("j"))
L’approche fonctionnelle permet une vision plus haut niveau que la programmation impérative : le code décrit ce qu’on fait, pas comment on le fait.
Ne pas préciser la manière à de faire, donc l’ordre d’itération par exemple, permet de laisser les optimisations à la charge l’auteur de la fonction.
Par exemple, on peut imaginer que ce traitement se fasse en parallèle, ce qui est facilement réalisable avec l’API collections Scala (voir cette documentation).

Les collections

Scala vient avec une API de collections très riche. Il existe des collections mutables et immutables, mais pour coller au style fonctionnel, on essaie d’utiliser des collections immutables le plus souvent possible.

Note : L’immutabilité est excellente pour la programmation concurrente ou parallèle, ne pas avoir de données mutables partagées par plusieurs threads permet d’éviter les locks et la synchronisation.
Vos processeurs multi-coeurs vont adorer la programmation fonctionnelle :)
Découvrons maintenant quelques exemples de collections Scala :

List

Pour déclarer une liste, on passe simplement la liste des éléments :
List(1,2,3) // List[Int]
L’inférence de type de Scala définit le bon type de liste en fonction des paramètres donnés.

Note sur l’immutabilité :
Faisons quelques tests avec la console Scala :
scala> val l = List("a", "b")
l: List[String] = List(a, b)

scala> l :+ "c"
res0: List[String] = List(a, b, c)

scala> l
res1: List[String] = List(a, b)

scala> l = l :+ "c"
<console>:8: error: reassignment to val
       l = l :+ "c"
On constate que :
* lorsque que l'on ajoute un élément à une liste, la liste n'est pas modifiée : on récupère à la place une nouvelle liste
* on ne peut modifier une liste, ou n'importe quel objet, déjà défini à l'aide du mot clé "val"

Array

Un Array Scala représente un tableau. On peut définir un Array d’entiers comme ceci :
val array = Array(1, 3, 5) 

Map

Pour définir une Map, c’est à dire un ensemble de couples clé/valeur, on procède ainsi :
val m = Map("a" -> 1, "b" -> 2) // Map[String, Int]
On peut ensuite lire une valeur comme ceci :
val v = m("b") // 2

Range

Un Range est un interval d’entiers :
Range(0,10) // entiers compris entre 0 et 10

Opérations disponibles sur les collections : quelques exemples

foreach

foreach permet de parcourir simplement une collection et d’effectuer un traitement à chaque itération :
Range(0,10).foreach(n => println("number " + n ))

map

map permet de transformer une collection en une autre collection de même taille, en appliquant une transformation (une fonction) sur chaque élément
Range(0,10).map(n => "number " + n ) // renvoie un Seq[String]

flatMap

flatMap permet de récupérer une structure “à plat” après avoir effectué une transformation :
val sentences = List("scala est super", "scala est fonctionnel")
val words = sentences.map(sentence => sentence.split(" ")) 
// List(Array(scala, est, super), Array(scala, est, fonctionnel))

val flattenWords = sentences.flatMap(sentence => sentence.split(" ")) 
// List(scala, est, super, scala, est, fonctionnel)
Là où map nous donnait une liste de tableaux, flatMap nous donne ce que l’on veut, à savoir une liste de mots.

filter

Comme son nom l’indique, filter permet de filtrer une collection.
Exemple, si on ne veut que les chiffres pairs d’un Range :
Range(0,10).filter(n => n%2 == 0)

fold

Imaginons que nous voulions additionner les éléments d’une liste d’entiers. La solution la plus naturelle en programmation impérative serait de définir un compteur et d’incrémenter sa valeur au fur et à mesure du parcours de la liste. Comment faire cela sans avoir recours à une variable mutable?
La fonction foldLeft permet de parcourir récursivement une collection, en passant à chaque appel récursif un accumulateur à l’appel suivant, cet accumulateur prenant une nouvel valeur à chaque appel.
Prenons un exemple, pour addition tous les entiers compris entre 0 et 10, on procède ainsi :
* On parcours la collection  élément par élément et on travaille avec un accumulateur pour sauvegarder les résultats intermédiaires.

* On donne un élément initial qui sera la valeur de l'accumulateur avant la première itération, et une fonction à appliquer à chaque itération :
foldLeft permet de parcourir la liste de gauche à droite, tandis que foldRight procède dans le sens inverse :
Range(0,10).foldLeft(0)((accu, elem) => accu + elem) //45
Range(0,10).foldRight(0)((accu, elem) => accu + elem) //45
Parfois il est important de choisir un ordre de parcours : le résultat peut être différent si l’opération n’est pas commutative!
Exemple :
Range(0,10).foldLeft(0)((accu, elem) => accu - elem) // -45
Range(0,10).foldRight(0)((accu, elem) => accu - elem) // -5
Si l’ordre n’a pas d’importance, on peut utiliser fold qui ne garantie pas l’ordre de parcours (ordre aléatoire).

reduce

Similaire à fold, mais la valeur de départ est le premier élément de la collection.
Avec un fold le résultat final aura le même type que l’élément initial. Pour pouvoir utiliser reduce, il faut donc que le résultat attendu corresponde au type du premier élément de la collection.
Range(0,10).reduceLeft((accu, elem) => accu + elem)
Comme pour fold, si l’ordre n’a pas d’importance, on peut utiliser reduce qui ne garantie pas l’ordre de parcours.

On dispose aussi d'opérations plus "amusantes" qui peuvent s'avérer utiles :

zip

zip permet de grouper 2 collections, élément par élément :
val a = List(1, 2, 3)
val b = List("a", "b", "c")

a.zip(b) // List((1,"a"), (2,"b"), (3,"c"))

intersect

intersect permet de ne garder que les éléments communs à 2 collections :
val a = List("a", "b", "c")
val b = List("b", "c", "d")
a.interesct(b) //List("b", "c")

combinations

Cette fonction permet de créer toutes les combinaisons possibles à partir d’une liste.
Elle prend en paramètre le nombre d’éléments désirés par combinaison.
a.combinations(2) //Iterator(List("a", "b"), List("a", "c"), List("b", "c"))

Les monades

Si vous avez commencé à étudier Scala ou un autre langage fonctionnel par vous même, vous avez sûrement entendu le mot “monade” plusieurs fois sans savoir à quoi le faire correspondre.
Sur Internet, on peut trouver des définitions comme “Les monades sont juste des monoïdes dans la categorie des endofoncteurs.”

Si on ne possède pas un doctorat en mathématiques et qu’on ne connait pas la théorie des catégories ce genre de définition peut être perturbant, voire effrayant!

Essayons de présenter ce concept bien pratique au quotidien, de manière plus simple, en regardant uniquement les propriétés qui nous intéressent.

Une monade permet d’encapsuler une valeur, un traitement, un résulat potentiel…
On peut voir une monade comme une boite, vide ou ayant un contenu, qui nous fournit des abstractions et des opérations au dessus de la valeur éventuellement encapsulée.

Il existe différents types de boites correspondant à différents types de structures.
Pour prendre un exemple, on est en général confronté aux monades pour la première fois avec le type Option quand on commence Scala.
Une option permet d’exprimer le fait que l’objet qu’on manipule contient peut être une valeur, mais peut être pas. Dans ce cas, la boîte nous permet de manipuler cet objet potentiel sans s’inquiéter de la présence ou non d’une valeur.
Les monades peuvent être composées pour obtenir de nouvelles boîtes.

Elles doivent obéir à certaines règles. On doit notamment pouvoir :

* créer une boite à partir d'une simple valeur à l'aide d'un constructeur
* manipuler le contenu de la boîte à partir de la boîte elle même
* composer des boites pour obtenir de nouvelles boites

Tout cela peut sembler encore un peu flou, mais ne vous inquiétez pas….
Une autre manière d’introduire la notion de monade en Scala peut être de parler d’interface monadique. On peut voir cette interface comme une simplification du concept de monade. Pour coller à cette nouvelle définition il suffit à un type de présenter les fonctions map, flatMap et filterWith (ou filter).
 Ces fonctions ont les caractéristiques suivantes :
* map permet de manipuler le contenu de la monade en appliquant un opération
* flatMap permet de composer deux monades de même type (ou de types compatibles) en appliquant une opération, pour obtenir une seule monade
* filterWith ou filter permettent de filtrer le contenu d'une monade

On peut chainer ces opérations autant que nécessaire et ainsi manipuler les valeurs contenues dans nos boîtes.
Nous allons voir quelques cas courants d’utilisation de monades.

Option

Option peut prendre deux valeurs : Some (si elle contient une valeur) et None (si elle est vide).
Pour définir une option, on dispose d’un constructeur :
val o = Option(2) //Some(2)
Il est possible d’utiliser la méthode lift sur une liste pour obtenir une option de la valeur contenue à un certain index.
On évite ainsi les erreurs en essayant de lire un index non existant :
val names = List("toto", "titi")
val maybeName = names.lift(0)
On peut manipuler l‘“intérieur” de l’option, c’est à dire la valeur sous jacente, en abstrayant le fait que cette valeur soit réellement présente ou pas.
C’est toute la puissance d’une monade :
maybeName.map(name => name.toUpperCase)
L'opération n'est appliquée que si l'option contient bien une valeur : si aucune valeur n'est présente (None), on récupère None lors de l'appel à map, sinon on récupère un nouveau Some contenant la valeur modifiée, ici en majuscules :
val maybeName = names.lift(0)
maybeName.map(name => name.toUpperCase)

>> Some(TOTO)

val maybeName2 = names.lift(2)
maybeName2.map(name => name.toUpperCase)
>> None
La méthode getOrElse renvoie le contenu de l’option si il existe (par exemple un String si on a un Some[String]), ou une valeur par défaut définie à l’appel de la méthode pour le cas où l'option est égale à None :
val name = names.lift(2).getOrElse("not found")
Ainsi on obtient dans tous les cas une valeur, et jamais une erreur.
Imaginons une fonction qui nous renvoie une option de liste :
def maybeList: Option[List[String]] = Some(List("toto", "titi"))
Maintenant créons une autre fonction qui renvoie une valeur à partir d’un index et de la liste précédemment créée, mais en majuscules.
En appelant cette fonction avec l’index 0, on devrait obtenir la valeur “TOTO”.
Avec l’index 1 on devrait obtenir “TITI”, et appelant cette même fonction avec l’index 2, on veut obtenir la valeur “not found”.

def indexValue(index: Int): Option = {
    maybeList.flatMap{ list =>
        list.lift(index).map{ value =>
            value.toUpperCase
        }
    }
}

Cette première version nous a permis de chainer la manipulation d’options : on a une option de liste, et dans cette liste une option de valeurs.
Grâce à l’utilisation de flatMap et de map, on a au final une seule option, qui contient peut être notre valeur modifiée comme on le voulait, c’est à dire en majuscules.
Mais ce n’est pas idéal! On ne veut pas une option mais une valeur finale.
Cette deuxième version corrige ce problème en utilisant getOrElse sur l’option finale obtenue après nos opérations :

def indexValue(index: Int): String = {
    maybeList.flatMap{ list =>
        list.lift(index).map{ value =>
            value.toUpperCase
        }
    }.getOrElse("not found")
}

Cette fois la fonction remplit le besoin demandé.
Pout terminer, on va ajouter un filtre, on ne veut que noms finissant par “I”.

def indexValue(index: Int): String = {
    maybeList.flatMap{ list =>
         list.lift(index)
         .filter(value => value.endsWith("i"))
         .map{ value =>
            value.toUpperCase
      }
    }
      .getOrElse("not found")
}
Ainsi, seul l’index 1 renvoie un résultat autre que “not found” !

Try

Try permet d’encapsuler un traitement pouvant lever une erreur.
import scala.io.Source
import scala.util.Try

def fileContent(path: String): Try[String] = Try(Source.fromFile("file.txt").mkString)

val maybeFileContent1 = fileContent("file1.txt")
val maybeFileContent2 = fileContent("file2.txt")

Try peut prendre 2 valeurs : Success et Failure.
Comme pour les options, on peut définir une valeur par défaut :

val content = maybeFileContent1.getOrElse("empty content")
On peut modifier le contenu du Try, si il existe, à l’aide de map :

maybeFileContent1.map(content => content.toLowerCase)
On peut également combiner 2 Try :

val allContents = maybeFileContent1.flatMap(content1 => maybeFileContent2.map(content2 => content1 + content2))

Future

Les futures aussi sont des monades qui permettent d’encapsuler un résultat qui arrivera plus tard, lorsque l’on fait de la programmation asynchrone.
def heavyComputing(i: Int): Future[Int] = ...
val future1 = heavyComputing(1)
val future2 = heavyComputing(2)

val sum = future1.flatMap(result1 => future2.map(result2 => result1 + result2))

For comprehension

"For comprehension" est ce qu’on appelle un “sucre syntaxique” pour map, flatMap et filterWith.
Applicable aux collections mais aussi à toutes les types correspondant à une interface monadique, c’est à dire aux options, futures etc., il permet d’écrire des enchainements de map, flatMap, filter(With) d’une manière différente qui peut être souvent plus claire et lisible.
Quelques exemples :

val sentences = List("scala est un langage", "scala est fonctionnel")
for{
  sentence <- sentences
} yield(sentence.toUpperCase) 
est équivalent à
sentences.map(sentence => sentence.toUpperCase)

Le mot clé yield permet d’accumuler des résultats pour les retrouver dans la nouvelle collection produite.
Même si ça y ressemble, il ne s’agit pas d’une boucle impérative.
Nous n’avons pas de collection mutable dans laquelle nous ajoutons un par un les résultats, yield nous permet de simuler ce genre de comportement.
Ajoutons une deuxième opération :
Au lieu de manipuler une liste de phrases, nous allons manipuler une liste de mots dans une liste de phrases, donc une liste de listes comme nous l’avons fait plus haut :

for{
  sentence <- sentences
  word <- sentence.split(" ")
} yield(word.toUpperCase)

est équivalent à

sentences.flatMap(sentence => sentence.split(" ").map(word => word.toUpperCase))
for{
  sentence <- sentences
  word <- sentence.split(" ")
} yield(word.toUpperCase)

Ceci peut s’appliquer à toute interface monadique.
Reprenons l’exemple vu pour le type Option : on peut maintenant écrire la même chose à l’aide d’un “for comprehension”.

def indexValue(index: Int): String = {
  maybeList.flatMap{ list =>
    list.lift(index).map{ value =>
      value.toUpperCase
    }
  }.getOrElse("not found")
}

est équivalent à :

def indexValue(index: Int): String = {
  (for{
    list <- maybeList
    value <- list.lift(index)  
  } yield(value.toUpperCase)).getOrElse("not found")
}

On peut également ajouter un filtre pour utiliser pleinement l’interface monadique :

def indexValue(index: Int): String = {
  (for{
    list <- maybeList
    value <- list.lift(index)
    if(value.endsWith "i")
  } yield(value.toUpperCase)).getOrElse("not found")
}

Avec cette dernière version, seule l’index 1 renverra une valeur différente de “not found”.
Pour terminer, voyons autre exemple de for comprehension, en reprenant l’exemple précédent sur les futures :

def combined: Future[Int] = for {
  r1 <- future1
  r2 <- future2
} yield r1 + r2

Et voilà, c’est tout pour ce long article d’initiation :)