Scala Kata – 01

Chaque matin, quelques lignes de code, un grand verre de jus d’orange et un bon café. Si vous prenez 10mn par jour pour lire / essayer quelques lignes de code, croyez-moi : cela va booster votre cerveau.

Une pratique simple : faire des Kata (型 ou 形) comme cela se pratique dans les Arts Martiaux. Au Karaté par exemple, nous apprenons des enchaînements en groupe, à réaliser tout seul. Cela permet d’exercer son corps à prendre des repères physiques et à perfectionner des mouvements, afin de les reproduire ensuite instinctivement.

Bon ce matin on va faire un peu de Scala. Ne partez pas, ce qui va suivre sera aussi un exercice pour les développeurs Java.

Voici l’énoncé de ce matin :

Soit une liste de nombres entiers en entrée. Construire une nouvelle liste où pour tout n de la liste (pour un élément P, à l’index n), le n-ième élément de la nouvelle liste est la somme de P et des n éléments suivants

Par exemple pour la liste en entrée suivante :

List(2, 5, 1, -9, 24, 3, 6, -8) 

le résultat attendu sera le suivant :

List(2, 6, 16, 24, 25, 1, -2, -8) // On va détailler comment ce calcul est fait

package exercises.trash

import org.scalatest.funsuite.AnyFunSuite
import org.scalatestplus.scalacheck.ScalaCheckDrivenPropertyChecks

class ListCalculatorTest extends AnyFunSuite with ScalaCheckDrivenPropertyChecks {

  test("Empty list should return empty list as a result") {
    assert(ListCalculator.processSum(List.empty[Int]) == List.empty[Int])
  }

  test("List of one element returns the same List") {
    assert(ListCalculator.processSum(List(2)) == List(2))
  }
}

Avec ces 2 petites tests, nous sommes en mesure maintenant d’écrire notre class ListCalculator et de définir une fonction processSum. Si nous pensons d’abord aux Types, c’est facile : pour une List de Int en entrée, la fonction processSum doit retourner une liste de Int en sortie. Je n’ai donc plus qu’à écrire une fonction avec les types attendus :

object ListCalculator{
  def processSum(inputList:List[Int]):List[Int]={
        inputList // en Scala, la dernière expression évaluée est la valeur de retour
  }
}

Je compile, je teste : ça marche. Bon évidemment nous savons que la fonction processSum n’est pas celle qui va répondre à tous nos cas de tests. Patience…

Le premier élément de la liste est à l’indice 0. D’après la consigne, on doit faire la somme de cet élément avec les n éléments suivants, ici 0. Donc cela veut dire que le premier élément de la nouvelle liste, sera identique à la liste originale. Ok allons-y :

package exercises.trash

import org.scalatest.funsuite.AnyFunSuite
import org.scalatestplus.scalacheck.ScalaCheckDrivenPropertyChecks

class ListCalculatorTest extends AnyFunSuite with ScalaCheckDrivenPropertyChecks {

  test("Empty list should return empty list as a result") {
    assert(ListCalculator.processSum(List.empty[Int]) == List.empty[Int])
  }

  test("List of one element returns the same List") {
    assert(ListCalculator.processSum(List(2)) == List(2))
  }

test("The first element of the new processed list is the same as the original list") {
  forAll() { inputList: List[Int] =>
    whenever(inputList.nonEmpty) {
      val updated = ListCalculator.processSum(inputList)
      assert(updated.head == inputList.head)
    }
  }
}
}

Sur l’exemple ci-dessus j’utilise le Property Base testing de ScalaTest. La fonction forAll() va générer plusieurs séries de List de Int. Des listes vides, des listes avec un seul élément, ou des Lists avec des milliers d’éléments. Ici le contrat est le suivant : quelque soit la liste, tant que celle-ci n’est pas vide, le premier élément de la nouvelle liste doit être égal au premier élément de la liste original. La fonction head en Scala prend le premier élément d’une liste (il existe aussi headOption mais je ne voulais pas complexifier le code ici, pour les personnes qui ne connaissent pas Scala).

Les tests par propriétés sont très pratiques pour couvrir rapidement des cas auquel nous n’aurions pas forcément pensés. J’imagine souvent les caractéristiques de la fonction que je vais devoir écrire, et j’en déduis ensuite des tests de propriétés.

Vous pouvez aussi dire que

• le dernier élément de la liste créé par processSum doit forcément être égal au dernier élément de la liste original. En effet, on fait la somme du dernier élément, et c’est tout. Il ne reste plus d’autres éléments à ajouter.
• la liste générée doit forcément faire la même taille que la liste en entrée. C’est une caractéristique très intéressante, qui nous permet de comprendre que notre fonction ne fera pas de réduction, mais un parcours spécial de la liste original… On aime bien ça nous en programmation fonctionnel.

test("The last element of the new processed list is the same as the original list") {
  forAll() { inputList: List[Int] =>
    whenever(inputList.nonEmpty) {
      val updated = ListCalculator.processSum(inputList)
      assert(updated.last == inputList.last) // accede au dernier élément de chaque liste
    }
  }
}

test("The processSum function returns a new list with same size as input list") {
  forAll() { list: List[Int] =>
    assert(ListCalculator.processSum(list).size == list.size)
  }
}

Voilà, avec tout cela nous pouvons déjà faire pas mal de code, mais nous savons que ce n’est pas suffisant. Il nous faut un test complet pour pouvoir réellement écrire le code.

test("test processSum") {
  assert(ListCalculator.processSum(List(2, 5, 1, -9, 24, 3, 6, -8)) 
== List(2, 6, 16, 24, 25, 1, -2, -8))
}

Observez bien la liste en entrée et la liste en sortie. Au besoin, prenez une feuille de papier pour représenter le code de votre fonction. La position courante donne le nombre d’éléments à utiliser pour la somme. Lorsqu’il n’y a plus assez d’éléments, on fait la somme.

Soit la liste = 
List(2, 5, 1, -9, 24, 3, 6, -8)
2 position 1 => 2 + 0 => 2
5 position 2 => 5 + 1 => 6
1 position 3 => 1 -9 +24 => 16
-9 position 4 => -9 + 24 + 3 + 6 = 24
24 position 5 => 24 + 3 + 6 - 8 = 25 // on ne peut prendre que 4 élements et pas 5
 3 position 6 => 3 + 6 - 8 = 1
 6 position 7 => 6 - 8 => -2
 -8 en position 9 => - 8 => -8

Ce qui donne bien List(2, 6, 16, 24, 25, 1, -2, -8)

En programmation fonctionnel, on aime bien les fonctions récursives. Ici, nous voyons que nous vidons une liste en entrée pour remplir une nouvelle liste en sortie. Lorsque vous devez « penser » fonctionnel, un des premiers réflexes est de ne pas modifier d’éléments, et de n’utiliser que des objets immuables. Nous allons réellement créer une liste, mais pour cela nous allons utiliser une approche récursive. Voyez cette boite de Lego devant vous avec 8 pièces ? Vous allez construire votre résultat en prenant une pièce à la fois, et en venant la fixer sur le bloc, jusqu’à ce qu’il ne reste plus de pièces dans la boîte.

En Scala il est possible de définir des fonctions à l’intérieur d’autres fonctions. C’est très pratique pour justement faire des fonctions récursives… même des fonctions Tail-Rec (mais ça, on en parlera que demain).

J’ai compris que :

• je dois retourner une nouvelle List de Int
• je dois me souvenir de la position courante pour prendre « n » éléments de la liste à utiliser pour mon addition
• je m’arrêterai lorsque la liste original sera vide

Etape 1 : je modifie mon code afin de déclarer une fonction locale, que j’appelle innerAccumul. Cette fonction par de la position 0, prend la liste passée en paramètre, et une Liste vide, qui sera utilisée pour accumuler mes valeurs. Les 3 points d’interrogations sont une fonction spéciale de Scala qui me permet de compiler, mais qui fera évidemment échouer le code si j’appelle réellement la fonction. On s’en sert lorsque l’on souhaite voir un peu ce que le compilateur va penser de notre code.

// Etape 1
object ListCalculator {
  def processSum(inputList: List[Int]): List[Int] = {
    
    def innerAccumul(posi: Int, inner: List[Int], newList: List[Int]): List[Int] = ???  

    innerAccumul(0, inputList, List.empty[Int])
  }
}

Voici comment j’ai pensé la fonction : je me dis que ma fonction va en quelque sorte « vider » la liste en entrée (inputList) en faisant les calculs. Pour faire ce travail, la fonction innerAccumul peut se rappeler elle-même, en passant un sous-ensemble de la liste. Cet appel récursif s’arrêtera lorsque la liste en entrée sera vide.

// Etape 2
object ListCalculator {
  def processSum(inputList: List[Int]): List[Int] = {
    
    def innerAccumul(posi: Int, inner: List[Int], newList: List[Int]): List[Int] = inner match {
      case Nil => newList
      case head :: tail => {
 
           innerAccumul(posi + 1, tail, ???)
      }
    }

    innerAccumul(0, inputList, List.empty[Int])
  }
}

La fonction innerAccumul fait du pattern matching sur la liste inner. Si cette liste est vide alors elle retournera la liste newList. Si par contre il reste des éléments, alors le pattern matching va extraire pour nous l’élément de tête (appelé head) et le « reste » de la liste (appelé tail). La fonction se ré-appelle elle-même en avançant d’une position (posi + 1) et en passant le « reste » de la liste. Cela veut dire que nous aurons fait notre calcul et que nous aurons aussi modifié « newList ». Ici à l’étape 2 j’ai utilisé ??? et donc notre code ne fonctionnera pas.

Si je veux voir mes tests unitaires, je peux remplacer les ??? par newList. Vous verrez que l’on a avancé, mais que ce n’est toujours pas ça.

Maintenant il nous reste une partie un peu plus complexe : comment faire la somme de l’élément courant et des n-autres éléments, sans dépasser la taille de la liste originale ?

Là j’avoue que j’ai pioché dans la librairie Scala, qui est ultra-riche et simple à utiliser. La fonction take(n) sur une Liste permet de prendre « n » éléments. Cependant si la liste est plus petite que le nombre d’éléments demandés, alors le sous-ensemble sera retourné, sans plantage ou sans ArrayIndexOutOfBoundsException :

scala> val myList = List(2,9,1,13)
val myList: List[Int] = List(2, 9, 1, 13)

scala> myList.take(2)
val res0: List[Int] = List(2, 9)

scala> myList.take(0)
val res1: List[Int] = List()

scala> myList.take(6)
val res2: List[Int] = List(2, 9, 1, 13)

Et ensuite une autre fonction sympathique : la fonction sum. Celle-ci permet de faire la somme des éléments d’une Liste d’entier.

scala> val myList = List(2,9,1,13)
val myList: List[Int] = List(2, 9, 1, 13)

scala> myList.sum
val res3: Int = 25

scala> myList.take(2).sum
val res4: Int = 11

Notez aussi que je peux enchainer l’appel de take et de sum. Chaque évaluation va retourner une nouvelle valeur (res1, res2, res3, etc) sans jamais modifier les listes originales. Lorsque vous faites myList.take(2) cela va créer une nouvelle liste, mais ne modifiera pas la liste originale.

Avec tout ceci, si vous êtes développeur Scala, normalement vous devriez pouvoir écrire et terminer l’exercice.

Pour les autres, voici comment nous allons terminer notre code :

object ListCalculator {
  def processSum(inputList: List[Int]): List[Int] = {
    @tailrec
    def innerAccumul(posi: Int, inner: List[Int], newList: List[Int]): List[Int] = inner match {
      case Nil => newList
      case head :: tail => {
        val result = head + tail.take(posi).sum
        innerAccumul(posi + 1, tail, newList :+ result)
      }
    }

    innerAccumul(0, inputList, List.empty[Int])
  }
}

Deux lignes à expliquer ici :

head + tail.take(posi).sum

Cette ligne prend l’élément de tête de la liste inner, et ensuite demande X éléments de la liste de queue. Elle fait la somme des éléments de queue + l’élément courant. On stocke dans une val result pour faciliter la lecture du code.

Ensuite la deuxième ligne :

innerAccumul(posi + 1, tail, newList :+ result)

Ici nous allons rappeler la fonction innerAccumul, en avançant d’une position, en prenant la « queue » de notre liste, et en ajoutant le résultat en fin de la nouvelle liste. La fonction :+ permet de créer une nouvelle liste en ajoutant un élément à la fin.

Ce qui est difficile, lorsque l’on vient du monde impératif, c’est que l’on met un certain temps à comprendre que les objets originaux ne sont jamais modifiés. Lorsque l’on écrit newList :+ result il faut bien comprendre que l’on créé alors une nouvelle liste, mais que la liste originale n’est pas modifiée.

Et la mémoire dans tout cela ? Ici nous allons créer différents objets mais ne risque-t-on pas de dépasser le nombre d’éléments sur la pile ? On remarque que la convergence n’est fait qu’à la fin, lorsque l’on retourne newList. Avant cela, on accumule et on créé des objets temporaires pour faire notre traitement…

Je vous parlerai demain de FizzBuzz et de fonction tail recursive, on va s’arrêter là pour aujourd’hui !

Pour les développeurs Scala dans la salle, peut-on utiliser folderLeft ou foldRight à la place de la fonction innerAccumul ? Je vous laisse réfléchir.

Bonne journée et bon code.

Articles similaires:

Scala, case, Option, None et Some Scala, partie 2 Soirée Scala au Paris JUG Présentation de Play! Scala au Scala User Group