Le Touilleur Express

  • Accueil
  • A propos de l’auteur
  • A propos du Touilleur Express
Next Previous

Scala Kata – 01

8 février, 2021

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

Notons d’abord plusieurs caractéristiques avant de se lancer dans l’implémentation :

  • la liste en sortie fait la même longueur que la liste en entrée
  • une liste vide en entrée devrait retourner une liste vide en résultat
  • le premier élément de la nouvelle liste sera forcément toujours identique au premier élément de la liste en entrée
  • de même, le dernier élément ne peut pas être sommé avec un autre élément. Donc la nouvelle liste doit se terminer aussi ici avec -8
  • lorsque l’on a plus assez d’éléments dans la liste restante, on prend le max mais on continue à sommer (comme pour le 5ème calcul)

On en sait maintenant assez pour écrire quelques tests unitaires. Je vais utiliser Scala. Vous pourriez d’ailleurs écrire votre code en Java, tout en le testant avec Scala, c’est possible.

Commençons par quelques tests simples :

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.

0 no like

Articles similaires:

Default ThumbnailScala, case, Option, None et Some Default ThumbnailScala, partie 2 Default ThumbnailSoirée Scala au Paris JUG Default ThumbnailPrésentation de Play! Scala au Scala User Group
  • Fabien Lamarque 8 février 2021 at 11 h 55 min

    Et hop, une solution en java en impératif, pour ceux qui voudraient essayer le kata :

    https://gist.github.com/Fabinout/abc8725fc810c2abdc0f1445d9204284

Chercher

Derniers articles

  • L’instant T où tu poses ta dém…
  • The « Robinson » projection – comprendre son système d’information
  • Réussir son démarrage comme Staff/Principal Engineer dans une nouvelle entreprise
  • Gérer les situations de blocage en tant que Staff Engineer
  • Un monolithe, c’est quoi ?

Commentaires récents

  • Nicolas Martignole dans The « Robinson » projection – comprendre son système d’information
  • Lucas dans The « Robinson » projection – comprendre son système d’information
  • Guillaume dans The « Robinson » projection – comprendre son système d’information
  • Francois Dechery dans The « Robinson » projection – comprendre son système d’information
  • Gaëtan dans The « Robinson » projection – comprendre son système d’information

Les plus lus

  • Les revenus d’un informaticien indépendant en EURL - 89 688 affichage(s)
  • Optional en Java 8 - 70 976 affichage(s)
  • Changer la batterie d’un MacBook Pro de 2011 - 65 601 affichage(s)
  • Quelle est la différence entre volatile et synchronized ? - 65 527 affichage(s)
  • Retour sur la soirée du lundi 12 juillet chez Doctolib - 63 082 affichage(s)
  • Un modèle de Product Backlog et de Sprint Backlog avec Excel - 57 816 affichage(s)
  • Redis, découverte d’un moteur clé-valeur simple et puissant - 51 025 affichage(s)
  • Comment simuler le navigateur de l'iphone avec Firefox ou Safari ? - 45 678 affichage(s)
  • serialVersionUID mythes et légendes - 41 909 affichage(s)
  • Développeur après 31 ans ? Ridé et chauve tu seras - 39 401 affichage(s)

Mots clés

agile ajax Apple architecture barcamp BarCampJavaParis ddd devoxx esb exo flex geek google grails groovy humeur humour independant iphone Java javascript jazoon jboss jboss seam jsf jug Linux mac mule paris jug parisjug pjug play playframework portlet recrutement ria Scala scrum spring Startup usi usi2010 web xebia

Derniers articles

  • L’instant T où tu poses ta dém…

    Retour d’expérience sur la démission et le moment où vous devez quitter une entreprise.

    7 likes

    24 octobre, 2024
  • The « Robinson » projection – comprendre son système d’information

    Nous sommes en juillet 2022 chez Doctolib. Je travaille sur un projet

    5 likes

    22 octobre, 2024
  • Réussir son démarrage comme Staff/Principal Engineer dans une nouvelle entreprise

    Je prépare une présentation avec mon collègue Théotime pour la conférence Cloud

    3 likes

    6 octobre, 2024

Mots clés

Apple (32) Architecture (14) Big Data (5) Conference (8) Devoxx (55) Dev Web (37) Doctolib (2) geekevent (1) groovy (2) Innoteria (11) Java (517) Linux (10) Non classé (15) Perso (266) Recrutement (2) Scala (30) scrum (43) Société (3) Staff Engineer (5) Startup (21) Web 2.0 (67)

Le Touilleur Express

Blog par Nicolas Martignole

Contactez-moi : nicolas@touilleur-express.fr

Suivez-moi sur X (Twitter) : @nmartignole

Copyright© 2008 - 2024 Nicolas Martignole | Tous droits réservés
  • A propos de l’auteur
  • A propos du Touilleur Express
  • Reset Password

Le Touilleur Express