Classi astratte

Per illustrare gli aspetti legati all’ereditarietà nel linguaggio Scala, si vuole come esempio definire una struttura dati che rappresenti un insieme di numeri interi.

Quando si crea una struttura dati, tipicamente la si caratterizza prima in modo astratto, specificando le operazioni che possono essere effettuate su di essa, e poi si forniscono una o più implementazioni concrete (possibilmente con complessità delle operazioni diverse, ecc) tra cui scegliere in base alle esigenze dell’applicazione.

In generale, un insieme è una “collezione” di elementi, che vengono mantenuti in modo non ordinato e senza ripetizioni. Su di esso è possibile definire svariate operazioni, ma qui per iniziare si inizia a considerarne due:

• contains, che verifica se un insieme contiene un determinato elemento
• add, che aggiunge un elemento a un insieme, restituendo un nuovo insieme (e non modificando l’insieme esistente, dato che ciò non è ammesso in un contesto puramente funzionale).

Il tipo che rappresenta la struttura dati insieme di interi può allora essere modellato mediante la seguente classe astratta, che dichiara ma non implementa i metodi corrispondenti alle operazioni che caratterizzano questo tipo:

abstract class IntSet {
	def add(x: Int): IntSet
	def contains(x: Int): Boolean
}

In Scala, le classi astratte funzinano sostanzialmente come in Java:

• Una classe astratta viene dichiarata usando il modificatore abstract
• Una classe astratta può contenere metodi astratti, che sono i metodi dichiarati senza specificarne il corpo (= ...). A differenza in Java, non si usa il modificatore abstract per contrassegnare i metodi astratti.
• Una classe astratta può anche contenere metodi concreti, cioè “normali” metodi non astratti, definiti specificandone il corpo.
• Una classe deve obbligatoriamente essere dichiarata astratta se contiene almeno un membro astratto, ma può essere dichiarata astratta anche se contiene solo membri concreti (o se è vuota)
• Non è possibile creare istanze di una classe astratta (con l’opeartore new).

In questo caso, IntSet non ha parametri di classe, ma in generale una classe astratta può avere parametri. Siccome non è possibile istanziare una classe astratta, i suoi parametri attuali vengono specificati solo dai costruttori primari delle sottoclassi, che richiamano il costruttore (primario o ausiliario) della classe astratta.

Alberi binari di ricerca

Adesso, bisogna fornire un’implementazione concreta degli insiemi interi. Nella definizione matematica di un insieme gli elementi non sono ordinati, ma quando essi vengono memorizzati si ha per forza un qualche ordine, esplicito o implicito, e bisogna fare attenzione che esso non si riperuota sui contratti dei metodi. Tuttavia, scegliendo un’opportuna struttura dati per rappresentare l’insieme si può trarre vantaggio dall’ordine degli elementi, sfruttandolo per rendere più efficienti le operazioni. Una tale struttura dati sono gli alberi binari di ricerca (BST, Binary Search Tree). Prima di implementarli, è utile presentarne la definizione formale.

Innanzitutto, un albero binario è definito come

• o l’albero vuoto
• oppure una tripla $(N, L, R)$ in cui $N$ è un nodo e $L, R$ sono alberi binari — $L$ è detto sottoalbero sinistro e $R$ è detto sottoalbero destro.