Il tutorial di Python, quarta parte: strutture dati, liste, tuple e sequenze. ~ Ubuntulandia

Strutture dati.
Questo capitolo descrive in maggiore dettaglio alcuni punti che sono già stati affrontati, e ne aggiunge pure alcuni nuovi.
Di più sulle liste
Il tipo di dato lista è dotato di ulteriori metodi. Ecco tutti i metodi degli oggetti lista:
append(     x)
    Aggiunge un elemento in fondo alla lista; equivale a a[len(a):] = [x].
extend(     L)
    Estende la lista aggiungendovi in coda tutti gli elementi della lista fornita; equivale a a[len(a):] = L.
insert(     i, x)
    Inserisce un elemento nella posizione fornita. Il primo argomento è l'indice dell'elemento davanti al quale va effettuato l'inserimento, quindi a.insert(0, x) inserisce x in testa alla lista, e a.insert(len(a), x) equivale a a.append(x).
remove(     x)
    Rimuove il primo elemento della lista il cui valore è x. L'assenza di tale elemento produce un errore.
pop(     [i])
    Rimuove l'elemento di indice i e lo restituisce come risultato dell'operazione. Se non è specificato alcun indice, a.pop() restituisce l'ultimo elemento della lista. L'elemento viene comunque rimosso dalla lista. Le parentesi quadrate intorno alla i, inserita dopo il metodo, informano che il parametro è facoltativo, nell'uso non dovranno essere scritte le parentesi quadre. Questa notazione è riscontrabile frequentemente nella Libreria di riferimento di Python.)
index(     x)
    Restituisce l'indice del primo elemento della lista il cui valore è x. L'assenza di tale elemento produce un errore.
count(     x)
    Restituisce il numero di occorrenze di x nella lista.
sort(     )
    Ordina gli elementi della lista, sul posto (NdT: l'output è la stessa lista riordinata).
reverse(     )
    Inverte gli elementi della lista, sul posto (NdT: come sopra).

Un esempio che utilizza buona parte dei metodi delle liste.
>>> a = [66.6, 333, 333, 1, 1234.5]
>>> print a.count(333), a.count(66.6), a.count('x')
2 1 0
>>> a.insert(2, -1)
>>> a.append(333)
>>> a
[66.6, 333, -1, 333, 1, 1234.5, 333]
>>> a.index(333)
1
>>> a.remove(333)
>>> a
[66.6, -1, 333, 1, 1234.5, 333]
>>> a.reverse()
>>> a
[333, 1234.5, 1, 333, -1, 66.6]
>>> a.sort()
>>> a
[-1, 1, 66.6, 333, 333, 1234.5]

Usare le liste come pile.
I metodi delle liste rendono assai facile utilizzare una lista come una pila, dove l'ultimo elemento aggiunto è il primo ad essere prelevato (``last-in, first-out''). Per aggiungere un elemento in cima alla pila, si usi append(). Per ottenere un elemento dalla sommità della pila si usi pop() senza un indice esplicito. Per esempio:
>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

Usare le liste come code.

Si può anche usare convenientemente una lista come una coda, dove il primo elemento aggiunto è il primo ad essere prelevato (``first-in, first-out''). Per aggiungere un elemento in fondo alla coda, si usi append(). Per ottenere l'elemento in testa, si usi pop() con indice 0. Per esempio:
>>> queue = ["Eric", "John", "Michael"]
>>> queue.append("Terry")           # Aggiunge Terry
>>> queue.append("Graham")          # Aggiunge Graham
>>> queue.pop(0)
'Eric'
>>> queue.pop(0)
'John'
>>> queue
['Michael', 'Terry', 'Graham']
Strumenti per la programmazione funzionale
Ci sono tre funzioni interne molto utili quando usate con le liste: filter(), map() e reduce().
"filter(funzione, sequenza)" restituisce una sequenza (dello stesso tipo, ove possibile) composta dagli elementi della sequenza originale per i quali è vera funzione(elemento). Per esempio, per calcolare alcuni numeri primi:
>>> def f(x): return x % 2 != 0 and x % 3 != 0
...
>>> filter(f, range(2, 25))
[5, 7, 11, 13, 17, 19, 23]
"map(funzione, sequenza)" invoca funzione(elemento) per ciascuno degli elementi della sequenza e restituisce una lista dei valori ottenuti. Per esempio, per calcolare i cubi di alcuni numeri:
>>> def cube(x): return x*x*x

...
>>> map(cube, range(1, 11))
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]
Può essere passata più di una sequenza; in questo caso la funzione deve avere tanti argomenti quante sono le sequenze e viene invocata con gli elementi corrispondenti di ogni sequenza (o None se qualche sequenza è più breve di altre). Per esempio:
>>> seq = range(8)
>>> def add(x, y): return x+y
...
>>> map(add, seq, seq)
[0, 2, 4, 6, 8, 10, 12, 14]
"reduce(funzione, sequenza)" restituisce un singolo valore ottenuto invocando la funzione binaria (NdT: a due argomenti) funzione sui primi due elementi della sequenza, quindi sul risultato dell'operazione e sull'elemento successivo, e così via. Ad esempio, per calcolare la somma dei numeri da 1 a 10:
>>> def add(x,y): return x+y
...
>>> reduce(add, range(1, 11))
55
Se la sequenza è composta da un unico elemento, viene restituito il suo valore; se la successione è vuota, viene sollevata un'eccezione.
Si può anche passare un terzo argomento per indicare il valore di partenza. In quel caso è il valore di partenza ad essere restituito se la sequenza è vuota, e la funzione viene applicata prima a tale valore e al primo elemento della sequenza, quindi al risultato di tale operazione e l'elemento successivo, e così via. Per esempio:
>>> def sum(seq):
...     def add(x,y): return x+y
...     return reduce(add, seq, 0)
...
>>> sum(range(1, 11))
55
>>> sum([])
0
Non si usi questo esempio di definizione sum(): dato che sommare numeri è piuttosto comune, è già disponibile una funzione built-in sum(sequenza) e funziona esattamente come questa. Nuovo nella versione 2.3

Costruzioni di lista.
Le costruzioni di lista forniscono un modo conciso per creare liste senza ricorrere all'uso di map(), filter() e/o lambda. La definizione risultante è spesso più comprensibile di ciò che si ottiene con i costrutti accennati. Ogni costruzione di lista consiste di un'espressione a cui segue una clausola for, quindi zero o più clausole for o if. Il risultato sarà una lista creata valutando l'espressione nel contesto delle clausole for e if che la seguono. Se l'espressione valuta una tupla, questa dev'essere racchiusa tra parentesi.
>>> freshfruit = [' banana', ' loganberry ', 'passion fruit ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']
>>> vec = [2, 4, 6]
>>> [3*x for x in vec]
[6, 12, 18]
>>> [3*x for x in vec if x > 3]
[12, 18]
>>> [3*x for x in vec if x < 2]
[]
>>> [[x,x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]
>>> [x, x**2 for x in vec]     # errore - per le tuple è richiesta la parentesi
File "<stdin>", line 1, in ?
    [x, x**2 for x in vec]
               ^
SyntaxError: invalid syntax
>>> [(x, x**2) for x in vec]
[(2, 4), (4, 16), (6, 36)]
>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [x*y for x in vec1 for y in vec2]
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [x+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]
[8, 12, -54]
Le costruzioni di lista sono molto più flessibili di map(), vi si possono applicare funzioni con più di un argomento e funzioni annidate:
>>> [str(round(355/113.0, i)) for i in range(1,6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']

L'istruzione del.
C'è un modo per rimuovere un elemento da una lista secondo il suo indice piuttosto che secondo il suo valore: l'istruzione del. È possibile usarla anche per rimuovere fette di una lista (cosa che precedentemente abbiamo ottenuto assegnando una lista vuota alle fette). Per esempio:
>>> a = [-1, 1, 66.6, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.6, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.6, 1234.5]
del può essere usata anche per eliminare intere variabili:
>>> del a
Fare riferimento al nome a dopo di ciò costituirà un errore (almeno fino a quando non gli verrà assegnato un altro valore). Si vedranno altri usi di del più avanti.

Tuple e sequenze.
Si è visto come stringhe e liste abbiano molte proprietà in comune, p.e. le operazioni di indicizzazione e affettamento. Si tratta di due esempi di tipi di dato del genere sequenza. Dato che Python è un linguaggio in evoluzione, potranno venir aggiunti altri tipi di dati dello stesso genere. C'è anche un altro tipo di dato standard del genere sequenza: la tupla.
Una tupla è composta da un certo numero di valori separati da virgole, per esempio:
>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Le tuple possono essere annidate:
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))
Come si può vedere, una tupla è sempre racchiusa tra parentesi nell'output, cosicché le tuple annidate possono essere interpretate correttamente; possono essere introdotte con o senza parentesi che le racchiudano, sebbene spesso queste siano comunque necessarie (se la tupla è parte di un'espressione più vasta).
Le tuple hanno molti usi, per esempio coppie di coordinate (x, y), record di un database ecc. Le tuple, come le stringhe, sono immutabili: non è possibile effettuare assegnamenti a elementi individuali di una tupla (sebbene si possa imitare quasi lo stesso effetto a mezzo affettamenti e concatenazioni). È anche possibile creare tuple che contengano oggetti mutabili, come liste.
Un problema particolare è la costruzione di tuple contenenti 0 o 1 elementi: la sintassi fornisce alcuni sotterfugi per ottenerle. Le tuple vuote vengono costruite usando una coppia vuota di parentesi; una tupla con un solo elemento è costruita facendo seguire ad un singolo valore una virgola (non è infatti sufficiente racchiudere un singolo valore tra parentesi). Brutto, ma efficace. Per esempio:
>>> empty = ()
>>> singleton = 'hello',    # <-- si noti la virgola alla fine
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',)
L'istruzione t = 12345, 54321, 'hello!' è un esempio di impacchettamento in tupla: i valori 12345, 54321 e 'hello!' sono impacchettati assieme in una tupla. È anche possibile l'operazione inversa, p.e.:
>>> x, y, z = t
È chiamata, in modo piuttosto appropriato, spacchettamento di sequenza. Lo spacchettamento di sequenza richiede che la lista di variabili a sinistra abbia un numero di elementi pari alla lunghezza della sequenza. Si noti che l'assegnamento multiplo è in realtà solo una combinazione di impacchettamento in tupla e spacchettamento di sequenza!
C'è una certa asimmetria qui: l'impacchettamento di valori multipli crea sempre una tupla, mentre lo spacchettamento funziona per qualsiasi sequenza.

Insiemi.
Python include anche tipi di dati per insiemi (NdT: sets). Un insieme è una collezione non ordinata che non contiene elementi duplicati al suo interno. Solitamente viene usato per verificare l'appartenenza dei membri ed eliminare gli elementi duplicati. Gli oggetti insieme supportano anche le operazioni matematiche come l'unione, l'intersezione, la differenza e la differenza simmetrica.
Questa è una breve dimostrazione:
>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> fruits = set(basket)               # crea un insieme con frutti
                                       #+ senza duplicati
set(['orange', 'pear', 'apple', 'banana'])
>>> 'orange' in fruits                 # veloce verifica
                                       #+ dell'appartenenza del membro
True
>>> 'crabgrass' in fruits
False
>>> # Dimostrazione delle operazioni set su un'unica lettera da due
    #+ parole
...
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a                                  # unica lettera in a
set(['a', 'r', 'b', 'c', 'd'])
>>> a - b                              # lettera in a ma non in b
set(['r', 'd', 'b'])
>>> a | b                              # lettera in a o in b
set(['a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'])
>>> a & b                              # lettera comune in a ed in b
set(['a', 'c'])
>>> a ^ b                              # lettera in a od in b ma non
                                       #+ in comune tra i due
set(['r', 'd', 'b', 'm', 'z', 'l'])

Dizionari.
Un altro tipo di dato built-in utile è il Tipo mappa, dizionario. I dizionari si trovano a volte in altri linguaggi come ``memorie associative'' o ``array associativi''. A differenza delle sequenze, che sono indicizzate secondo un intervallo numerico, i dizionari sono indicizzati tramite chiavi, che possono essere di un qualsiasi tipo immutabile. Stringhe e numeri possono essere usati come chiavi in ogni caso, le tuple possono esserlo se contengono solo stringhe, numeri o tuple; se una tupla contiene un qualsivoglia oggetto mutabile, sia direttamente che indirettamente, non può essere usata come chiave. Non si possono usare come chiavi le liste, dato che possono essere modificate usando i loro metodi append() e extend(), come pure con assegnamenti su fette o indici.
La cosa migliore è pensare a un dizionario come un insieme non ordinato di coppie chiave: valore, con il requisito che ogni chiave dev'essere unica (all'interno di un dizionario). Una coppia di parentesi graffe crea un dizionario vuoto: {}. Mettendo tra parentesi graffe una lista di coppie chiave: valore separate da virgole si ottengono le coppie iniziali del dizionario; nello stesso modo i dizionari vengono stampati sull'output.
Le operazioni principali su un dizionario sono la memorizzazione di un valore con una qualche chiave e l'estrazione del valore corrispondente a una data chiave. È anche possibile cancellare una coppia chiave: valore con del. Se si memorizza un valore usando una chiave già in uso, il vecchio valore associato alla chiave viene sovrascritto. Cercare di estrarre un valore usando una chiave non presente nel dizionario produce un errore.
Il metodo keys() di un oggetto dizionario restituisce una lista di tutte le chiavi usate nel dizionario, in ordine casuale (se la si vuole ordinata, basta applicare il metodo sort() alla lista delle chiavi). Per verificare se una data chiave si trova nel dizionario, si può usare il metodo has_key().
Ecco un piccolo esempio di operazioni su un dizionario:
>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'sape': 4139, 'guido': 4127, 'jack': 4098}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'guido': 4127, 'irv': 4127, 'jack': 4098}
>>> tel.keys()
['guido', 'irv', 'jack']
>>> tel.has_key('guido')
True
Il costruttore dict() crea dizionari direttamente dalla lista di coppie chiave: valore immagazzinate in tuple. Quando la coppia forma un modello, la costruzione di lista può specificare liste chiave: valore in modo compatto.
>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
{'sape': 4139, 'jack': 4098, 'guido': 4127}
>>> dict([(x, x**2) for x in vec])     # uso della costruzione di lista
{2: 4, 4: 16, 6: 36}

Tecniche sui cicli.
Quando si usano i cicli sui dizionari, la chiave e il valore corrispondente possono essere richiamati contemporaneamente usando il metodo iteritems().
>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.iteritems():
...     print k, v
...
gallahad the pure
robin the brave
Quando si usa un ciclo su una sequenza, la posizione dell'indice e il valore corrispondente possono essere richiamati contemporaneamente usando la funzione enumerate().

>>> for i, v in enumerate(['tic', 'tac', 'toe']):
...     print i, v
...
0 tic
1 tac
2 toe
Utilizzando un ciclo su due o più sequenze contemporaneamente, le voci possono essere accoppiate con la funzione zip().
>>> domande = ['nome', 'scopo', 'colore preferito']
>>> risposte = ['lancillotto', 'il santo graal', 'il blu']
>>> for q, a in zip(domande, risposte):
...     print 'Qual'e` il tuo %s? E` il %s.' % (q, a)
...
Qual'e` il tuo nome? E` lancillotto.
Qual'e` il tuo scopo? E` il santo graal.
Qual'e` il tuo colore preferito? E` il blu.
Per eseguire un ciclo inverso su di una sequenza, prima si deve specificare la direzione di avanzamento e quindi chiamare la funzione reversed().
>>> for i in reversed(xrange(1,10,2)):
...     print i
...
9
7
5
3
1
Per eseguire un ciclo ordinato su di una sequenza, si deve usare la funzione sorted() che restituisce una nuova lista ordinata finché rimane inalterata la sorgente dei dati da elaborare.
>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for f in sorted(set(basket)):
...     print f
...
apple
banana
orange
pear

Di più sulle condizioni.
Le condizioni usate nelle istruzioni while e if possono contenere altri operatori oltre a quelli di confronto classici.
Gli operatori di confronto in e not in verificano se un valore compare (o non compare) in una sequenza. Gli operatori is ed is not confrontano due oggetti per vedere se siano in realtà lo stesso oggetto; questo ha senso solo per oggetti mutabili, come le liste. Tutti gli operatori di confronto hanno la stessa priorità, che è minore di quella di tutti gli operatori matematici.
I confronti possono essere concatenati. Per esempio, a < b == c verifica se a sia minore di b e inoltre se b eguagli c.
Gli operatori di confronto possono essere combinati tramite gli operatori booleani and e or, e il risultato di un confronto (o di una qualsiasi altra espressione booleana) può essere negato con not. Inoltre questi tre operatori hanno priorità ancora minore rispetto agli operatori di confronto; tra di essi not ha la priorità più alta e or la più bassa, per cui A and not B or C è equivalente a (A and (not B)) or C. Naturalmente per ottenere la composizione desiderata possono essere usate delle parentesi.
Gli operatori booleani and e or sono dei cosiddetti operatori short-circuit: i loro argomenti vengono valutati da sinistra a destra e la valutazione si ferma non appena viene determinato il risultato. Per esempio se A e C sono veri ma B è falso, A and B and C non valuta l'espressione C. In generale, il valore restituito da un operatore short-circuit, quando usato come valore generico e non come booleano, è l'ultimo argomento valutato.
È possibile assegnare il risultato di un confronto o di un'altra espressione booleana a una variabile. Ad esempio:
>>> string1, string2, string3 = '', 'Trondheim', 'Hammer Dance'
>>> non_null = string1 or string2 or string3
>>> non_null
'Trondheim'
Si noti che in Python, a differenza che in C, all'interno delle espressioni non può comparire un assegnamento. I programmatori C potrebbero lamentarsi di questa scelta, però essa evita un tipo di problema che è facile incontrare nei programmi C: l'introduzione di = in un'espressione volendo invece intendere ==.
Confrontare sequenze con altri tipi di dati
Gli oggetti sequenza possono essere confrontati con altri oggetti sequenza dello stesso tipo. Il confronto utilizza un ordinamento lessicografico: innanzitutto vengono confrontati i primi due elementi (NdT: delle due sequenze) e, se questi differiscono tra di loro, ciò determina il risultato del confronto; se sono uguali, vengono quindi confrontati tra di loro i due elementi successivi, e così via, fino a che una delle sequenze si esaurisce. Se due elementi che devono essere confrontati sono essi stessi delle sequenze dello stesso tipo, il confronto lessicografico viene effettuato ricorsivamente. Se tutti gli elementi delle due sequenze risultano uguali al confronto, le sequenze sono considerate uguali. Se una sequenza è una sottosequenza iniziale dell'altra, la sequenza più breve è la minore. L'ordinamento lessicografico per le stringhe usa l'ordine ASCII per i singoli caratteri. Ecco alcuni esempi di confronti tra sequenze dello stesso tipo:
(1, 2, 3)              < (1, 2, 4)
[1, 2, 3]              < [1, 2, 4]
'ABC' < 'C' < 'Pascal' < 'Python'
(1, 2, 3, 4)           < (1, 2, 4)
(1, 2)                 < (1, 2, -1)
(1, 2, 3)             == (1.0, 2.0, 3.0)
(1, 2, ('aa', 'ab'))   < (1, 2, ('abc', 'a'), 4)
Si noti che confrontare oggetti di tipi diversi è lecito. Il risultato è deterministico ma arbitrario: i tipi vengono ordinati secondo il loro nome. Perciò una lista è sempre minore di una stringa, una stringa è sempre minore di una tupla, ecc. Tipi numerici eterogenei vengono confrontati secondo il loro valore numerico, così 0 è uguale a 0.0, ecc.