Chapitre 4 · encre prune

Les collections

Iterable, Seq, Set, Map. Filtrer, transformer, agréger. L'arsenal fonctionnel qui rend Scala vraiment expressif — l'examen testera ta capacité à lire ces opérations.

~ 55 min Source : Scala_04 — Collections (Zaouche, Dujol) 14 flashcards · 8 QCM

📄 Ressources du cours

📥 Télécharger les slides · 🔗 Ouvrir dans un nouvel onglet · 📝 Ouvrir le TD

🎥 Vidéos recommandées

🇫🇷 Scala Tutorial 24 - map, flatMap, flatten and filter (Higher-order Methods)
ProgrammingKnowledge · 13:30 · 41k vues — In this video we will cover the basic syntax and capabilities of Higher-order Methods like map, flatMap, flatten and filter in Scala. In Scala map, flatMap, ...
🇫🇷 Scala Tutorial 21 - Scala Maps
ProgrammingKnowledge · 12:55 · 30k vues — In this video we will cover the basic syntax and capabilities of Maps in Scala. In Scala maps are the collections of key value pairs. Scala maps can be mutab...
🇬🇧 Scala Tutorial 24 - map, flatMap, flatten and filter (Higher-order Methods)
ProgrammingKnowledge · 13:30 · 41k vues — In this video we will cover the basic syntax and capabilities of Higher-order Methods like map, flatMap, flatten and filter in Scala. In Scala map, flatMap, ...

1. La hiérarchie des collections

Définition Une collection est un container d'un nombre arbitraire d'éléments du même type. Exemple déjà vu (kinda) : Option[T].

Deux packages principaux :

scala.collection.immutable — la PF favorise ces collections
scala.collection.mutable — à utiliser avec parcimonie

Concurrent programming favorise aussi l'immutable (cf. CM6 Akka).

Hiérarchie principale (Scala 2.13+). L'étoile ★ marque l'implémentation par défaut.

2. Iterable — le sommet

Tout Iterable possède un iterator Accessible via la méthode iterator. C'est un objet mutable avec deux méthodes essentielles :

hasNext — y a-t-il encore des éléments ?
next — donne l'élément suivant (s'il existe)

// Forme idiomatique (functional)
scala> List(1, 3, 5) foreach { x => println(s"Current element is $x") }
Current element is 1
Current element is 3
Current element is 5

// Forme equivalente avec iterator (rarement utilisee en FP)
scala> val it = List(1, 3, 5).iterator
scala> while (it.hasNext) println(s"Current element is ${it.next()}")

3. Seq — séquences ordonnées

Seq[+T] Collection ordonnée. Type parameter covariant. Méthodes principales : head, tail, apply, length. Implémentation par défaut : List.

IndexedSeq vs LinearSeq

IndexedSeq[T] Pour les séquences avec accès aléatoire rapide : apply et length efficaces. Défaut : Vector[T].

LinearSeq[T] Pour les séquences avec accès linéaire : head et tail efficaces. Défaut : List[T]. Autres : Queue[T], LazyList[T].

NB : en Scala, tout String est vu implicitement comme un Seq[Char]. ⇒ on peut filtrer/mapper sur les caractères d'une String.

Méthodes de base — à lire dans le code

scala> val s = Seq(5, 1, 3, 1)
s: Seq[Int] = List(5, 1, 3, 1)

scala> s.length    // 4
scala> s.head      // 5
scala> s.tail      // List(1, 3, 1)
scala> s(1)       // 1  — raccourci pour s.apply(1) — ⚠ indexation a partir de 0
scala> s == Seq(1, 1, 3, 5)
res5: Boolean = false   // Seq compare l'ORDRE

Opérateurs de séquence

Opérateur	Effet	Mnémonique
`++`	Concaténation	Concat de 2 séquences
`:+` / `+:`	Append / Prepend	Le `:` est du côté de la collection
`reverse`	Miroir	—

scala> Seq(5, 1, 3) ++ Seq(1, 4)
res0: Seq[Int] = List(5, 1, 3, 1, 4)

scala> Seq(5, 1, 3) :+ 1      // append : la seq est a gauche
res1: Seq[Int] = List(5, 1, 3, 1)

scala> 2 +: Seq(5, 1, 3)      // prepend : la seq est a droite
res2: Seq[Int] = List(2, 5, 1, 3)

scala> Seq(5, 1, 3).reverse
res3: Seq[Int] = List(3, 1, 5)

4. Set — ensembles

Set[T] Collection non ordonnée, sans doublons. Type parameter invariant. Méthodes : contains, diff. Défaut : HashSet[T]. Sous-trait SortedSet[T] → TreeSet[T].

Opérateur	Effet
`++`	Union ensembliste
`&`	Intersection
`&~`	Différence
`apply`	Équivalent à `contains`

scala> val s = Set(5, 1, 3, 1)
s: Set[Int] = Set(5, 1, 3)              // pas de doublons

scala> s contains 4                       // false
scala> s ++ Set(2, 3, 4)                   // Set(5, 1, 2, 3, 4)
scala> s & Set(2, 3, 4)                    // Set(3)
scala> s &~ Set(2, 3, 4)                   // Set(1, 5)
scala> s == Set(1, 3, 5)                   // true (ordre ignore !)
scala> s(1)                                // true — apply ≡ contains

⚠ Set.empty et invariance Comme le type paramètre est invariant, Set[Nothing] n'est pas sous-type de Set[T]. Donc le type exact doit être connu d'avance : val s = Set.empty[Int].

5. Map — dictionnaires clé/valeur

Map[K, +V] Clés invariantes, valeurs covariantes. Méthodes : get, removed. Défaut : HashMap. Variantes : SortedMap → TreeMap, SeqMap → VectorMap.

scala> val m = Map("dze" -> "Cergy", "rdl" -> "Pau")
m: Map[String,String] = Map(dze -> Cergy, rdl -> Pau)

scala> m("rdl")                               // "Pau" — apply
scala> m("bge")                               // java.util.NoSuchElementException ⚠
scala> m.get("bge")                          // Option[String] = None — safe

scala> val m1 = m + ("bge" -> "Cergy")         // ajout
scala> m1 - "rdl"                              // retrait

🔑 Le réflexe à avoir
m(k) peut throw. Pour un accès safe, préférer m.get(k) qui renvoie Option[V]. Combine très bien avec match ou .getOrElse(default).

6. Conversions `to(_)`

Direction	Méthode	Effet
`Seq → Seq variant`	`to(IndexedSeq)`, `to(Vector)`, `to(LinearSeq)`, `to(List)`	change l'implémentation
`Seq → Set`	`to(Set)`, `to(SortedSet)`	élimine les doublons, perd l'ordre
`Set → Seq`	`to(Seq)`, `to(List)`, …	donne un ordre arbitraire
`Map → Seq[(K,V)]` ou `Set[(K,V)]`	`to(Seq)`, `to(Set)`	vue comme tuples
`Seq[(K,V)] → Map`	`to(Map)`	indexer par clé

Syntaxe alternative : toSeq, toList, toSet, toMap (anciennes formes).

7. Méthodes communes — la pierre angulaire

Toutes ces méthodes existent sur Iterable[T]. Selon la collection appelante, le type de résultat est le même type que l'entrée.

Recherche

Méthode	Signature	Renvoie
`isEmpty` / `nonEmpty`	—	`Boolean`
`size` (alias `length`)	—	nombre d'éléments
`exists`	`(p : T => Boolean) : Boolean`	au moins un `x` avec `p(x) == true`
`forall`	`(p : T => Boolean) : Boolean`	tous les `x` avec `p(x) == true`
`count`	`(p : T => Boolean) : Int`	nombre de `x` satisfaisant `p`
`find`	`(p : T => Boolean) : Option[T]`	premier `x` trouvé, ou `None`

Filtre

filter(p : T => Boolean)            // sous-collection des x avec p(x) == true
filterNot(p : T => Boolean)         // ≡ filter(x => !p(x))
partition(p : T => Boolean)         // (filter p, filterNot p) en une passe

Features :

Type de résultat = type de la collection d'entrée (List → List)
Si la collection est ordonnée, l'ordre relatif est préservé

Extraction

Position fixe :

take(n)      // n premiers
takeRight(n) // n derniers
drop(n)      // sans les n premiers
dropRight(n) // sans les n derniers
splitAt(n) ≡ (take n, drop n)

Conditionnelle :

takeWhile(p)   // prend tant que p(x)
dropWhile(p)   // drop tant que p(x)
span(p) ≡ (takeWhile p, dropWhile p)

⚠ Pureté sur les collections non ordonnées Sur un Set (non ordonné), take(2) ne donne pas un résultat déterministe — il dépend de l'ordre interne de stockage. La méthode n'est pas garantie d'être pure.

Transformation — `map`, `flatMap`, `flatten`

Trois sœurs essentielles

flatten : aplatit une collection de collections en une collection unique
map(f : T => U) : applique f à chaque élément, renvoie la collection des résultats
flatMap(f : T => Iterable[U]) ≡ map(f).flatten

// flatten — applati
scala> Seq(Seq(5, 1, 1), Seq(1)).flatten
res0: Seq[Int] = List(5, 1, 1, 1)

// Set de Seq -> Set des elements (dedoublonne)
scala> Set(Seq(5, 1, 1), Seq(1)).flatten
res1: Set[Int] = Set(5, 1)

// map — transformation 1 vers 1
scala> Seq(5, 1, 2) map { 1.0 / _ }
res3: Seq[Double] = List(0.2, 1.0, 0.5)

// flatMap — chaque element produit plusieurs sorties
scala> Seq(5, 1, 2) flatMap { x => List(x, x) }
res5: Seq[Int] = List(5, 5, 1, 1, 2, 2)

for-comprehensions

Sucre syntaxique pour map / filter / flatMap

for (x <- c) yield f(x) ≡ c map f
for (x <- c if cond(x)) yield f(x) ≡ (c filter cond) map f
for (x <- c1 ; y <- c2) yield f(x, y) ≡ c1 flatMap (x => c2 map (y => f(x, y)))

⚠ Ne pas oublier le mot-clé yield ! Sans yield, c'est une simple boucle avec effet de bord, qui retourne Unit. Avec yield, on construit une nouvelle collection.

scala> def couplesWithSum(n : Int) =
         for (i <- 0 to n ;
              j <- 0 to n if i + j == n)
           yield (i, j)

scala> couplesWithSum(4)
res1: IndexedSeq[(Int, Int)] = Vector((0,4), (1,3), (2,2), (3,1), (4,0))

📌 Analogie SGBD
• Objet ≡ Item dans une base
• Collection ≡ Table
• for (x <- table) ≡ SELECT * FROM table
• if cond(x) ≡ WHERE cond(x)
Une for-comprehension est donc une requête SQL en miniature.

8. Agrégation — `fold`

Les trois variantes du fold

foldLeft[U](z : U)(op : (U, T) => U) : U
   ≡ op(...(op(op(z, a₁), a₂)...), aₙ)

foldRight[U](z : U)(op : (T, U) => U) : U
   ≡ op(a₁, op(a₂, op(... , op(aₙ, z))))

fold[T1 >: T](z : T1)(op : (T1, T1) => T1) : T1
   // se comporte comme ci-dessus SI op est associative

Comportement :

Si la collection est vide, le résultat est toujours z (l'élément zéro)
Sur une collection non ordonnée, le résultat n'est pas garanti d'être pur — sauf pour fold si op est associative ET commutative

Visualisation — `foldLeft`

L'accumulateur est à gauche, les éléments sont consommés de gauche à droite.

(List(a₁, a₂, a₃, a₄) foldLeft z)(op)

  z — op — op — op — op
            │      │      │      │
            a₁   a₂   a₃    a₄

= op(op(op(op(z, a₁), a₂), a₃), a₄)

Visualisation — `foldRight`

L'accumulateur est à droite, les éléments sont consommés de droite à gauche.

(List(a₁, a₂, a₃, a₄) foldRight z)(op)

  op — op — op — op — z
   │      │      │      │
   a₁   a₂   a₃    a₄

= op(a₁, op(a₂, op(a₃, op(a₄, z))))

foldLeft vs foldRight — comment les distinguer

Aspect	foldLeft	foldRight
Accumulateur	paramètre gauche de `op`	paramètre droit de `op`
Éléments pris	depuis la gauche	depuis la droite
Récursivité	tail-recursive (efficace)	Pas tail-recursive
Sens	« plie » à gauche	« plie » à droite

🎯 Conseil pratique
Pour des grandes collections, préférer foldLeft (tail-recursive) : pas de risque de StackOverflowError. Si l'opération est commutative et associative, choisir fold pour le maximum de flexibilité.

Exemple — calculer des combinaisons

scala> def combinations[T](s : Set[T]) =
         (s foldLeft Set(Set[T]())) { case (z, x) => z ++ (z map { _ + x }) }

scala> combinations((1 to 3).to(Set))
res0: Set[Set[Int]] = HashSet(
   Set(), Set(1, 3), Set(2), Set(2, 3), Set(3),
   Set(1, 2), Set(1), Set(1, 2, 3))

Méthodes équivalentes pour cas particuliers : sum, product, min, max — en interne, ce sont des fold spécialisés. Ex : list.sum ≡ list.fold(0)(_ + _).

★ Réviser le chapitre

🃏 Flashcards — comportement des opérations

Différence Seq / Set / Map ?

Seq = ordonnée, doublons OK. Set = non ordonnée, pas de doublons. Map = clé/valeur, clés uniques.

List ou Vector pour accès aléatoire rapide ?

Vector (IndexedSeq) — apply/length efficaces. List (LinearSeq) = head/tail efficaces.

Mnémonique pour :+ vs +: ?

Le : est du côté de la collection. seq :+ x = append (seq à gauche). x +: seq = prepend (seq à droite).

Quelle est la différence entre m(k) et m.get(k) ?

m(k) peut throw NoSuchElementException. m.get(k) renvoie Option[V] : Some ou None. Préférer get.

exists vs forall vs find ?

exists : ∃ x avec p(x) → Boolean. forall : ∀ x → Boolean. find : premier x → Option[T].

À quoi sert partition ?

Renvoie un tuple (filter p, filterNot p) en une seule passe — plus efficace que d'appeler les deux séparément.

Différence map et flatMap ?

map(f : T => U) : 1 élément → 1 résultat. flatMap(f : T => Iterable[U]) : 1 élément → plusieurs résultats, aplatis. ≡ map(f).flatten.

Que se passe-t-il sans yield dans un for ?

Le for devient une boucle avec effet de bord qui retourne Unit. Avec yield, on construit une nouvelle collection.

for (x <- c if cond) yield f(x) équivaut à ?

(c filter cond) map f. Le compilateur Scala traduit la for-comprehension en map/filter/flatMap.

foldLeft : où est l'accumulateur ?

À gauche dans op(u, t). Les éléments sont consommés de gauche à droite. Tail-recursive donc efficace.

Que vaut List().foldLeft(z)(op) ?

Tout simplement z. Si la collection est vide, le résultat est l'élément zéro.

Pourquoi fold exige une op associative ?

Parce que l'ordre d'évaluation n'est pas garanti (parallèlisation possible). Si op n'est pas associative, deux exécutions peuvent donner des résultats différents.

Que renvoie Set(1,2,3).take(2) ?

Un Set de 2 éléments… mais pas forcément les "deux premiers" (Set est non ordonné). La méthode n'est pas garantie d'être pure.

Pourquoi le compilateur dit Set[Nothing] pour Set.empty ?

Parce que Set a un paramètre de type invariant. Il faut spécifier le type : Set.empty[Int].