Tipo astratto Lista

Il tipo astratto Lista rappresenta sequenze di elementi ciascuno dei quali è di un certo tipo prefissato. La sua definizione è la seguente.

TipoAstratto Lista(T)

Domini

  

Lista

: dominio di interesse del tipo

T

: dominio degli elementi che formano le liste

Funzioni

  

listaVuota()  Lista

 
pre: nessuna
post: RESULT è la lista vuota

estVuota(Lista l)  Boolean

 
pre: nessuna
post: RESULT è true se la lista l è vuota, false altrimenti

cons(T e, Lista l)  Lista

 
pre: nessuna
post: RESULT è la lista ottenuta da l inserendo e come primo elemento

car(Lista l)  T

 
pre: l non è la lista vuota
post: RESULT è il primo elemento di l

cdr(Lista l)  Lista

 
pre: l non è la lista vuota
post: RESULT è la lista ottenuta da l eliminando il primo elemento

FineTipoAstratto

Note

I nomi delle funzioni del tipo astratto provengono dal LISP che è un linguaggio di programmazione interamente basato sulle liste. Tale linguaggio definito nel 1958 da McCarthy, è stato il linguaggio che ha introdotto il paradigma di programmazione funzionale (vedi Unità 1). I nomi car e cdr sono un retaggio storico. Essi traggono origine da un particolare calcolatore dell'epoca, l'IBM 704, dove erano rispettivamente l'abbreviazione per "contents of address register" (i primi 18 bit di parole da 36 bit) e "contents of the decrement register" (i secondi 18 bit).

Esempi di uso della classe Lista

Le operazioni che realizziamo sono:

• calcolo della lunghezza della lista, che dato un oggetto Lista calcola la lunghezza della lista che esso rappresenta;
• aggiunta un elemento in coda alla lista, che dato un oggetto Lista ed un elemento da aggiungere restituisce un nuovo oggetto Lista ottenuto dal primo aggiungendo il nuovo elemento come ultimo elemento della lista;
• concatenazione (``append'') di due liste, che dati due oggetti Lista restituisce un nuovo oggetto Lista ottenuto concatenando le due liste; cioè restituendo una lista composta dagli elementi della prima lista e seguiti dagli elementi della seconda lista;
• restituzione dell'elemento i-esimo della lista, che preso un oggetto Lista e un intero i (dove i = 0,.., lung. della lista - 1) restituisce l'elemento in posizione i;
• inserimento di un nuovo elemento in posizione i-esima, che preso un oggetto Lista, un intero i (dove i = 0,.., lung. della lista - 1) e un elemento da inserire, restituisce un nuovo oggetto Lista ottenuto dal primo aggiungendo in posizione i-esima il nuovo elemento.