Merge sort su liste di interi

Si vuole implementare il merge sort sulle liste, considerando inizialmente per semplicità solo liste di numeri interi. L’algorimo opera in questo modo:

• se la lista è vuota o contiene esattamente un elemento, allora è ordinata
• altrimenti, si spezza la lista in due sotto-liste aventi (circa) il medesimo numero di elementi, si ordinano le due sotto-liste e si effettua il merge di queste ultime in un’unica lista ordinata.

def msort(xs: List[Int]): List[Int] = {
	val half = xs.length / 2
	if (half == 0) xs
	else {
		def merge(xs: List[Int], ys: List[Int]): List[Int] = /* ... */

		val fst = xs take half
		val snd = xs drop half
		merge(msort(fst), msort(snd))
	}
}

Il merge di due liste ordinate xs e ys in un’unica lista ordinata viene eseguito come segue:

• se xs è vuota si restituisce l’altra lista ys
• altrimenti, il comportamento dipende da come è fatta ys
  • se ys è vuota si restituisce xs (questo caso è simmetrico a quello in cui xs è vuota)
  • altrimenti si seleziona il minore tra i primi elementi delle due liste, lo si mette come tsta della lista risultante e si continua il merge ricorsivamente sul resto delle liste

def merge(xs: List[Int], ys: List[Int]): List[Int] = xs match {
	case Nil => ys
	case x :: xs1 => ys match {
		case Nil => xs
		case y :: ys1 =>
			if (x <= y) x :: merge(xs1, ys)
			else y :: merge(xs, ys1)
	}
}

Tuple e assegnamenti strutturati

Per comodità, Scala fornisce una sintassi di supporto per rappresentare tuple: una tupla costituita dagli elementi $e_1,..., e_N$, i quali possono essere di tipi differenti, è scritta come $(e_1, ..., e_N)$.

Una tupla è gestita come un unico valore, che può essere assegnato a un nome e ha il tipo $(T_1,..., T_N)$, dove $T_1, ..., T_N$ sono i tipi dei suoi elementi $e_1,..., e_N$: ad esempio:

val pair = ("pippo", 5) // pair: (String, Int) = (pippo,5)

(il commento indica l’output dell’interprete)

E’ possibile fare pattern matching sugli elementi di una tupla tramite pattern del tipo $(p_1,..., p_N)$; ad esempio:

pair match {
	case ("pippo", n) => n
	case _ => 0
} // res0: Int = 5

In generale, oltre che in un’espressione match un pattern può essere usato a sinistra dell’uguale in una definizione di nome con val. Ciò prende il nome di assegnamento strutturato, ed è utile ad esempio per assegnare a dei nomi gli elementi di una tupla:

val (label, len) = pair // label: String = pippo
                        // len: Int = 5

Traduzione delle tuple in oggetti

Le tuple sono zucchero sintattico che il compilatore traduce nell’uso di delle normali classi scala.TupleN (definite per $N=1, ..., 22$), che hanno essenzialmente la seguente struttura: