Lisp – Oltre le liste, altri usi delle cons cells – 1

l13Abbiamo visto come le liste siano un’illusione creata dalle funzioni che manipolano le cons cells. Oltre alle liste Common Lisp fornisce funzioni che dalle cons cells permettono di costruire alberi (trees), sets e lookup tables. Soliti problemi (miei) di traduzione, chissà… 🙄

Alberi (trees)

Trattare le cons cells come alberi è facile come per le liste. Un albero non è che una lista di liste. Le funzioni che li riguardano sono quelle per attraversarlo per trovare un determinato valore. Le cons cells che una  funzione lista attraversa sono chiamate struttura della lista (list structure), sono trovate partendo dalla prima cons cell e seguendo i riferimenti dei cdr fino a trovare un nil. Gli elementi della lista sono gli oggetti referenziati dai cars delle cons cells nella struttura della lista. Se una cons cell nella struttura della lista ha un car che referenzia un’altra cons cell la cons cell referenziata è considerata la testa di una lista che è un elemento della lista esterna. La tree structure, in altri termini, è attraversata seguendo entrambe le referenze a car e cdr fintanto che puntano a altre celle. I valori in un tree sono allora i valori atomici (non cons cells) referenziate da cars o cdrs delle cons cells della struttura dell’albero.

Per esempio il diagramma seguente mostra le cons cells che costruiscono la lista di liste ((1 2) (3 4) (5 6)).  La struttura della lista include solo le tre cons cells nel box tratteggiato mentre la struttura dell’albero include tutte le celle.

list-or-tree

Per vedere la differenza tra una funzione lista e una funzione tree si può considerare copy-list e copy-tree che copiano un gruppo di cons cells.
copy-list, come funzione lista, copia le cons-cells che creano la struttura della lista, cioè crea una nuova cons cell corrispondente a ogni cons cell all’interno del box tratteggiato. Il car di ognuna di queste nuove cons cells referenzia gli stessi oggetti dei cars delle cons cells originali nella struttura della lista. Quindi copy-list non copia le sottoliste (1 2), (3 4) e (5, 6), come visualizzato nel diagramma:

copy-list-list-or-tree

copy-tree d’altra parte crea una nuova cons cell di ognuna delle cons cells del diagramma e le linka insieme nella stessa struttura, così:

copy-tree-list-or-treeDove una cons cell in origine referenzia un valore atomico la corrispondente ons cell nella copia referenzia lo steso valore. Quindi i soli oggetti referenziati in comune tra l’albero originale e la copia prodotta da copy-tree sono i numeri 1-6 e il simbolo nil.

Un’altra funzione che percorre sia i cars che i cdrs di un albero è tree-equal, che compara due alberi considerandoli uguali se la tree structure ha la stessa forma e le foglie sono eql (o un altro test fornito con la chiave :test).

Altre funzioni tree-centriche sono le equivalenti di substitute, nsubstitute e le loro varianti -if e -if-not. La funzione subst, come substitute, prende un nuovo elemento, un vecchio elemento e un tree (invece della sequenza), con possibili argomenti keyword :key e :test e ritorna un nuovo tree con la stessa forma dell’originale ma con tutte le istanze al vecchio elemento rimpiazzate con il nuovo. Esempio:

c13-0

subst-if è analoga a substitute-if. Invece di un vecchio elemento prende una funzione con un argomento che viene chiamata con ogni valore atomico nel tree e se ritorna vero la posizione è riempita con il nuovo valore. subst-if-not fa la stessa cosa quando il test ritorna nil. nsubst, nsubst-if e nsubst-if-not sono le versioni riciclanti delle subst. valgono le solite considerazioni delle funzioni distruttive, nèh!

Sets (insiemi)

Anche i sets possono essere implementati in termini di cons cells. Si può trattare ogni lista come un set e Common Lisp fornisce diverse funzioni per le operazioni della teoria degli insiemi. Tuttavia queste operazioni diventano via via meno efficienti al crescere del set.
Se nel profiling si scopre che il codice è lento si possono trasformare i set in hash tables o bit vectors.

Per costruire un set si usa adjoin. adjoin prende un elemento e una lista rappresentante il set e ritorna una lista contenente l’elemento e tutti gli elementi del set originario. Per determinare se un elemento è presente si deve scannare (lo so che ai ‘taliani questa parola non piace e la scrivono diversa) la lista, se l’elemento non è trovato adjoin crea una nuova cons cell contenente l’elemento e puntante alla lista originaria e ritornandola. Altrimenti ritorna la lista originaria.

adjoin può prendere anche le solite keyword arguments :key e :test per determinare se l’elemento è presente nella lista. Come cons adjoin non modifica la lista originale; se vuoi modificare una lista particolare devi assegnare i valore ritornato da adjoin nel posto da dove viene (mah? vedi esempio sotto). La macro pushnew lo fa automaticamente:

c13-1

Si può testare se un dato elemento è presente in un set con member e relative -if e -if-not. Queste funzioni sono simili a find eccetto che possono essere usate solo con liste e invece di ritornare l’elemento se questo è presente ritornano la cons cell che lo contiene, in altri termini la sub-lista che inizia con quell’elemento. Quando l’elemento non è presente ritornano nil.

Esistono poi intersection, union, set-difference e set-exclusive-or. Ognuna di queste funzioni prendono due liste, :key e :test e ritornano una nuova lista rappresentante il set risultante dall’operazione effettuata sulle due liste. intersection ritorna la lista degli elementi contenuti in entrambe le liste. union ritorna quella contenente un’istanza di ogni elemento unico presente nelle due liste, se le liste contengono duplicati può contenere duplicati. set-difference ritorna la lista contenente tutti gli elementi della prima lista che non appaiono nella seconda. set-exclusive-or ritorna una lista contenente gli elementi che compaiono in una delle due liste ma non in entrambe. Ognuna di queste funzioni ha la corrispondente riciclante con lo stesso nome ma con il prefisso n.

Infine subsetp prende due liste e i soliti :key e :test e ritorna vero se la prima lista è un subset della seconda, cioè ogni elemento della prima lista è presente anche nella seconda. L’ordine degli elementi non ha importanza:

c13-2

Continua, mi sa :mrgreen:

Posta un commento o usa questo indirizzo per il trackback.

Trackback

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: