Definizione di Nil come object

Si consideri l’implementazione delle liste presentata in precedenza:

trait List[T] { /* ... */ }
class Cons[T](val head: T, val tail: List[T])
	extends List[T] { /* ... */ }
class Nil[T] extends List[T] { /* ... */ }

Al momento le liste vuote sono rappresentate da istanze della classe Nil[T], ma idealmente si vorrebbe trasformare tale classe in un object, poichè è concettualmente corretto che tutte le liste vuote siano rappresentate dal medesimo oggetto, indipendentemente dal tipo degli elementi, dato che esse non contengono alcun elemento; rappresentarle con oggetti diversi è un’inutile ridondanza, che porta solo a uno sprreco di memoria.

Un primo tentativo potrebbe essere

object Nil[T] extends List[T] { /* ... */ }

che però non viene accettato in quanto un object non può dipendere da un tipo parametro: la sua unica istanza viene automaticamente, quindi il programmatore non può specificare un tipo con cui istanziare il parametro. Allora, un object che estende un tipo parametrico deve istanziare i tipi parametro di quest’ultimo con dei tipi specifici. Nel caso di Nil, ciò significa sostanzialmente fissare il tipo di elementi della lista vuota; volendo che il valore Nil possa rappresentare una lista vuota per qualsiasi tipo di elementi, si sceglie il tipo Nothing, che è sottotipo di (compatibile con) tutti i tipi:

object Nil extends List[Nothing] { /* ... */ }

Tale scelta è coerente anche perchè Nothing è il tipo di cui non esiste alcun valore e Nil è la lista che non contiene alcun elemento.

Dichiarare Nil come sottotipo di List[Nothing] non è sufficiente a rappresentare liste vuote di qualsiasi tipo: è vero che Nothing è compatibile con qualunque altro tipo, ma con l’attuale definizione del trait List[T] non è vero che List[Nothing] (il tipo di Nil) è compatibile con qualunque lista, perchè il tipo parametro T è invariante. Ad esempio, se si prova a definire

val x: List[String] = Nil

il compilatore genera il seguente errore:

type mismatch;
found : Nil.type
required: List[String]
Note: Nothing <: String (and Nil.type <: List[Nothing]),
but trait List is invariant in type T.
You may wish to define T as +T instead. (SLS 4.5)

Perchè la cosa funzioni è necessario che List[Nothing] sia sottotipo di qualunque istanza di List, ovvero che List sia covariante nel tipo parametro T: bisogna scrivere trait List[+T] invece di trait List[T].

Complessivamente, con le modifiche appena descritte, le definizioni che formano la gerarchia di classi di List diventano:

trait List[+T] {
	def isEmpty: Boolean
	def head: T
	def tail: List[T]
}

class Cons[T](val head: T, val tail: List[T]) extends List[T] {
	def isEmpty: Boolean = false
}

object Nil extends List[Nothing] {
	override def isEmpty: Boolean = true
	
	override def head: Nothing =
		throw new NoSuchElementException("Nil.head")
	
	override def tail: Nothing =
		throw new NoSuchElementException("Nil.tail")
}

Un’osservazione interessante su quest’implementazione sono i tipi restituiti dai metodi head e tail di Nil. Siccome Nil estende il trait List[T] istanziando il parametro T con Nothing, i tipi restituiti che il trait richiede per head e tail sono rispettivamente Nothing (T) e List[Nothing] (List[T]). Per head, Nothing è il tipo più preciso possibile, dato che tale metodo solleva sempre un eccezione. Anche tail solleva sempre un’eccezione, dunque il tipo più preciso è Nothing, che infatti è il tipo indicato nell’implementazione del metodo: ciò è consentito nonostante il tipo previsto dal trait sia List[Nothing] perchè Nothing <: List[Nothing], e in generale l’implementazione di un metodo astratto (o un override di un metodo concreto) può restituire un sottotipo del tipo previsto dal metodo astratto (o dal metodo originale che si sta ridefinendo).

Metodo prepend

Adesso, si vuole aggiungere a List un metodo prepend che, dato un argomento elem di tipo T, restituisca una nuova lista ottenuta aggiungendo un nodo contenente elem in testa alla lista su cui il metodo è eseguito. Una prima definizione potrebbe essere:

trait List[+T] {
	// ...
	def prepend(elem: T): List[T] = new Cons(elem, this)
}