Listes Scala: méthodes foldLeft et foldRight

Leave a Comment
Dans ce billet je souhaite vous parler rapidement des méthodes foldLeft et foldRight de l’API des listes en Scala.

foldLeft


foldLeft est une méthode de la classe scala.collection.immutable.List et voici ce que le scaladoc nous en dit:
Applies a binary operator to a start value and all elements of this list, going left to right.
Scaladoc nous dit que foldLeft applique une fonction prenant deux paramètres (opérateur binaire) à une valeur initiale (appelée accumulateur dans le jargon fonctionnel) et à tous les éléments de la liste en partant de la gauche. Voyons attentivement la signature de la méthode pour rendre les choses un peu plus claires!

def foldLeft [B] (z: B)(f: (B, A) ⇒ B): B

Ah tiens une chose transparaît dans cette signature: foldLeft est une méthode currifiée. Si vous n’avez jamais fait de programmation fonctionnelle auparavant cette notion ne doit pas vous parler. En fait malgré les apparences la méthode foldLeft ne prend pas deux arguments! Voici comment elle fonctionne: elle prend un paramètre z de type B et renvoie une fonction qui prend à son tour un paramètre qui est une fonction de type (B, A) => B. z est représente la valeur initiale de l’accumulateur et est du même type que la valeur de retour de foldLeft. A chaque étape la fonction f est appliquée à l’accumulateur et à l’élément courant de la liste. La valeur de l’accumulateur peut changer tout au long du déroulement de l’opération. Prenez une minute pour bien visualiser la chose ce n’est pas si compliqué que cela une fois qu’on a compris la notion. La méthode fold est d’une puissance incroyable! Elle vous permet de faire quasiment de faire toutes les opérations imaginables avec les listes.

Voici un usage simple de foldLeft: Calculer la somme des éléments d’une liste d’entiers.

L’accumulateur (la valeur initiale) est égal à zéro et l’opérateur binaire est une fonction qui prend deux entiers et fait leur somme:

val nums = List(1, 2, 3, 4)
val sum = nums.foldLeft(0){
 (acc, num) => acc + num
}

En action dans le REPL:
scala> val nums = List(1, 2, 3, 4)
nums: List[Int] = List(1, 2, 3, 4)

scala> val sum = nums.foldLeft(0){
 (acc, num) => acc + num
}
sum: Int = 10

Le déroulé de l’opération foldLeft est le suivant :
((((0 + 1) + 2) + 3) + 4)
((((1) + 2) + 3) + 4)
(((3) + 3) + 4)
((6) + 4)
(10)

En image cela donne:


foldRight


foldRight est assez similaire à foldLeft mais il parcourt la liste en partant de la droite de la liste. Ainsi c’est le dernier élément de la liste qui est d’abord traitée. Voyons l’implémentation de la somme des éléments d’une liste avec foldRight:

scala> val nums = List(1, 2, 3, 4)
nums: List[Int] = List(1, 2, 3, 4)
scala> val sum = nums.foldRight(0) {(num, acc) =>
 num + acc
}
sum: Int = 10
Le déroulé de l’opération foldLeft est le suivant :

(1 + (2 + (3 + (4 + 0))))
(1 + (2 + (3 + (4))))
(1 + (2 + (7)))
(1 + (9))
(10)


Conclusion


Prenez le temps de digérer ce contenu si jamais l’envie me prend dans l’avenir je reviendrais sur une comparaison plus avancée entre ces deux méthodes.

S-99: P06, P07

Leave a Comment

Je continue la résolution des 99 problèmes en Scala. Au fur et à mesure que j'avance dans la résolutions de ces problèmes je me rends compte je fais beaucoup usage du pattern matching. Et cet épisode ne fait pas exception à la règle!


Le problème P06: Vérifier si une liste est un palindrome

C'est par là si vous voulez en savoir davantage sur le palindrome.
Exemple

scala> isPalindrome(List(1, 2, 3, 2, 1))
res0: Boolean = true


La solution à P06

Je suis rapidement arrivé à la solution suivante consistant à comparer la liste avec son inverse. J'ai ensuite cherché d'autres plus "efficace" mais je ne suis pas arrivé à trouver une solution plus "fonctionnelle" à mon goût.

def isPalindrome[T](xs: List[T]) = xs.reverse == xs


Le test de la solution

import org.specs2.mutable._

class P06Spec extends Specification {
  "P06.isPalindrome(xs)" should {    
    "return true" in {
      P06.isPalindrome(List()) must_== true
    }
    
    "return true" in {
      P06.isPalindrome(List(1)) must_== true
    }
    
    "return true" in {
      P06.isPalindrome(List(60, 60)) must_== true
    }
    
    "return true" in {
      P06.isPalindrome(List(3, 2, 1, 2, 3)) must_== true
    }
  }
}


Le problème P07: Mettre à plat une liste de listes

Il s'agit de mettre à plat une liste dont les constituants peuvent être des listes à leur tour. C'est pour le fun que nous écrivons cette fonction mais pas une nécessité car l'API des listes fournit une méthode permettant de mettre à plat une liste.
Exemple:

scala> flatten(List(List(1, 1), 2, List(3, List(5, 8))))
res0: List[Any] = List(1, 1, 2, 3, 5, 8)


La solution à P07

La solution utilise le pattern matching et la récursivité à fond!

  def flatten(xs: List[Any]): List[Any] = {
    xs match {
      case head :: tail => (head, tail) match {
        case (h: List[Any], t) => flatten(h) ++ flatten(t)
        case (h: Any, t) => h :: flatten(t)
      }
      case x => x
    }
  }


Le test de la solution

import org.specs2.mutable._

object P07Spec extends Specification {
  "P07.flatten(xs)" should {
    "return Nil" in {
      P07.flatten(Nil) must_== Nil
    }
    
    "return List(1)" in {
      P07.flatten(List(1)) must_== List(1)
    }
    
    "return List(1, 2)" in {
      P07.flatten(List(1, List(2))) must_== List(1, 2)
    }
    
    "return List(1, 2, 3, 4)" in {
      P07.flatten(List(1, List(2, 3), 4)) must_== List(1, 2, 3, 4)
    }
    
    "return List(1, 2, 3, 4, 5, 7, 8)" in {
      P07.flatten(List(1, List(2, 3), 4, List(5, List(6, List(7, 8))))) must_== List(1, 2, 3, 4, 5, 6, 7, 8)
    }
  }
}


Fin du voyage mes amis! A bientôt pour un autre épisode ;-)

© Nouhoum TRAORE.. Fourni par Blogger.