Si consideri l'implementazione di un tipo di dato "insieme", che
rappresenta un insieme di elementi di un tipo generico alpha (in
realta', un generico tipo non va bene; serve un tipo su cui e'
definito il test di uguaglianza fra due valori - in standard ML,
''a
).
Su valori di questo tipo sono definite le funzioni addin
(per aggiungere un elemento ad un insieme), removefrom
(per rimuovere un elemento da un insieme) ed isin
(per
controllare se un elemento e' in un insieme).
Una possibile implementazione puo' essere basata su liste standard
ML, con isin
che verifica se un elemento e' contenuto
in una lista, addin
che aggiunge un elemento alla lista
se non e' gia' contenuto e removefrom
che rimuove
un elemento da una lista.
Si sviluppi una possibile implementazione di questo tipo di dati.
emptyset
abbia tipo 'a list
,
isin
abbia tipo fn: ''a -> ''a list -> boole
e cosi' via...
'a set
come sinonimo di 'a list
. Sfortunatamente questa
definizione non e' molto utile (il tipo di emptyset
e' sempre "sbagliato", etc...)emptyset
ha tipo 'a set
e le varie funzioni sembrano usare i
tipi "giusti"... Ma 'a set
e' solo un sinonimo per
'a list
, non un nuovo tipo! Per rendersene conto, si
provi a lavorare con valori di tipo 'a set
come se
fossero liste...Il motivo per cui tutte le soluzioni presentate finora non riescono
ad implementare un vero e proprio tipo di dato astratto e' che
type
non introduce nuovi tipi, ma definisce solo
sinonimi per tipi esistenti. Un primo passo in questa direzione
e' quello di "raggruppare" assieme le varie funzioni che lavorano
su insiemi (ed eventualmente anche la definizione di
'a set
) tramite il costrutto delle strutture.
'a set
dentro alla
strutturaUna volta che il costrutto structure
e' utilizzato
per racchiudere tutto il codice che opera sui valori del tipo
di dato insieme, e' possibile usare un signature
per rendere opache tali definizioni (rendendo visibile solo la
"firma" delle funzioni ed i nomi dei tipi).
Ecco quindi un'ulteriore soluzione che
usa un signature per "nascondere" la
definizione di 'a set
e delle varie funzioni.