Le strutture dati immutable costituiscono uno degli elementi di base della programmazione funzionale pura. La libreria standard di Scala fornisce, all’interno del package scala.collection.immutable, le implementazioni di varie strutture immutable, tra cui List, Vector, Range, HashMap, HashSet, ecc. Adesso si inizierà a presentare la classe List — che è simile all’implementazione semplificata delle liste vista finora — mentre alcune delle altre strutture saranno discusse più avanti.
List[+T]La classe scala.collection.immutable.List[+T] implementa una cons-list (immutable linked list) che rappresenta collezioni ordinate di elementi di tipo T.
Così come gli array sono la struttura dati lineare “fondamentale” nei linguaggi imperativi, le liste lo sono nei linguaggi funzionali, poichè (a differenza degli array) esse sono ricorsive e immutabili. Dato che esse sono molto usate, dover ogni volta importare la classe List sarebbe piuttosto scomodo, perciò il package scala (importato automaticamente) fornisce un alias scala.List,
type List[T] = scala.collection.immutable.List[T]
che permette di usare List senza importarla.
Una lista contenente gli elementi $e_1, ..., e_n$ può essere creata con List(e1, ..., en), un costruttore (metodo apply del companion object di List) generico che accetta un numero qualsiasi di argomenti; in particolare, è ammesso specificare zero argomenti, List(), il che crea una lista vuota.
Le liste sono strutture dati omogenee, ovvero i cui elementi hanno tutti il medesimo tipo T. Quando si crea una lista con List(e1, ..., en), il compilatore deduce T selezionando il più piccolo supertipo comune ai tipi di tutti gli elementi e1, ..., en (considerando non solo le relazioni supertipo-sottotipo ma anche, ad esempio, le conversioni implicite tra i tipi numerici); per la lista vuota viene dedotto T = Nothing. Ad esempio:
List() // Tipo dedotto: List[Nothing]
List(1, 2, 3, 4, 5, 6) // Tipo dedotto: List[Int]
List(1, 2.5, 3L) // Tipo dedotto: List[Double]
List("apple", "orange", "pineapple") // Tipo dedotto: List[String]
List(List(1, 2, 3), List(4, 5, 6)) // Tipo dedotto: List[List[Int]]
List(1, "apple", List(5, 6)) // Tipo dedotto: List[Any]
List(List(1, 2, 3), List("a", "b")) // Tipo dedotto: List[List[Any]]
Si noti in particolare che il tipo dell’ultima lista è List[List[Any]] perchè il tipo parametro di List è covariante — A <: B implica List[A] <: List[B] — quindi List[Any] è supertipo dei tipi dei due elementi di tale lista, che sono a loro volta liste di tipo List[Int] e List[String] rispettivamente.
I principali costruttori delle liste sono:
Nil, che rappresenta la lsita vuota::, chiamato cons: x :: xs restituisce una nuova lista che ha l’elemento x come testa e la lista xs come coda (ovvero corrisponde al metodo xs.prepend(x) e al costruttore new Cons(x, xs) che si erano definiti nell’implementazione delle liste presentata in precedenza).In seguito sono riportati alcuni esempi di uso di questi costruttori:
val fruit = "apple" :: ("orange" :: ("pineapple" :: Nil))
val nums = 1 :: (2 :: (3 :: (4 :: (5 :: (6 :: Nil)))))
val empty = Nil
Siccome il nome dell’operatore :: termina con i due punti, tale operatore è associativo a destra: A :: B :: C è equivalente ad A :: (B :: C). Ciò significa che le parentesi negli esempi precedenti sono superflue, e omettendole si ottiene una maggiore leggibilità, si mette in evidenza la struttura delle liste costruite:
val fruit = "apple" :: "orange" :: "pineapple" :: Nil
val nums = 1 :: 2 :: 3 :: 4 :: 5 :: 6 :: Nil
Inoltre, l’uso di un operatore il cui nome termina con : è interpretato come un’invocazione di metodo sull’operando destro invece che sul sinistro, quindi gli esempi precedenti equivalgono a: