Cons-list

Le cons-list, una struttura dati fondamentalmente in molti linguaggi funzionali, sono linked list immutabili definite ricorsivamente a partire da:

• Nil, il caso base, che rappresenta la lista vuota
• Cons, un costruttore (il suo nome è appunto un’abbreviazione di “constructor”) che costruisce una lista a partire da un elemento e da un’altra lista (per la precisione, un riferimento al resto della lista), ovvero rappresenta una cella, un nodo della lista.

Le cons-list furono introdotte in Lisp, il primo linguaggio funzionale, nel quale erano la struttura dati principale, fornita direttamente a livello del linguaggio. In Scala, invece, esse son implementate nella libreria standard, allo stesso modo di altre strutture dati che possono essere definite dall’utente; grazie ad alcune funzionalità del linguaggio (la possibilità di definire operatori, ecc), tale implementazione rimane comunque piuttosto comoda da usare, come se fosse una struttura predefinita del linguaggio.

Le cons-list fornite dalla libreria standard di Scala possono contenere elementi di un tipo qualsiasi, ma per illustrarne l’implementazione è utile iniziare da una versione semplificata, che può contenere solo numeri interi. Tale implementazione è composta dalle seguenti definizioni:

trait IntList { /* ... */ }
class Nil extends IntList { /* ... */ }
class Cons(val head: Int, val tail: IntList) extends IntList {
	// ...
}

• un trait IntList che specifica i metodi disponibili sulle liste (qui omesi perchè si vuole prima porre l’attenzione sulla struttura ad alto livello delle definizioni)
• due sottoclassi concrete, Nil e Cons, corrispondenti ai due casi della definizione ricorsiva.

In accordo con queste definizioni, una IntList è una lista vuota, new Nil, oppure una lista new Cons(x, xs) costituita da un elemento x, che prende il nme di head (testa), e da una lista xs, che assume il ruolo di tail (coda). Ad esempio, la lista contenente gli elementi 3, -1, 7 è:

new Cons(3, new Cons(-1, new Cons(7, new Nil)))

Si noti che Nil potrebbe essere implementato come object, dato che la lista vuota è unica (tutte le sue istanze sono identiche), ma definirlo per ora come classe semplificherà la generalizzazione a liste di tipo generico che verrà fatta a breve.

Parametri val

Come già accennato in precedenza, Scala fornisce una sintassi compatta per evitare di dover introdurre esplicitamente i campi corrispondenti ai parametri di una classe. Tale sintassi è stata usata nella definizione della classe Cons:

class Cons(val head: Int, val tail: IntList) extends IntList {
	// ...
}

In generale, scrivere val di fronte a un parametro di una classe ha l’effetto di:

• definire il parametro (formale) di classe
• definire un corrispondente campo della classe, che al mometo della creazione di un oggetto viene inizializzato con il valore del parametro (attuale) di classe.

Questa funzionalità è zucchero sintattico, poichè può essere riscritta aggiungendo esplicitamente le definizioni dei campi corrispondenti ai parametri (e rinominando i parametri per evitare conflitti di nomi tra questi e i campi): ad esempio, la definizione

class Cons(val head: Int, val tail: IntList) extends IntList {
	// ...
}