Ricorsione su un elenco di elenchi senza alcuna istanza()

Question

Ho appena letto "isinstance() considered harmful" e sembra ragionevole. In breve, argomenta per evitare l'uso di questa funzione.

Bene, proprio ora mi capita di scrivere un programma che prende input strutturati come un albero e ha bisogno delle informazioni sulla struttura dell'albero. Senza il tempo necessario per implementare una GUI, impongo all'utente di scriverlo in un file di configurazione (so che questa è un'interfaccia errata, ma la pianificazione è molto stretta). I miei utenti sono molto tecnici, ma non necessariamente conoscono Python. Ho scelto che il file conterrà elenchi di elenchi (di elenchi di elenchi ecc.) Che rappresentano gli alberi di input, con gli elementi finali che sono i nodi foglia degli alberi. Penso che sia molto meglio che imporre il synthax dei dizionari agli utenti.

ho intenzione di analizzare le liste in modo ricorsivo come il seguente (ommiting l'uso della struttura dell'albero, cerchiamo di semplificare e dire treatLeafNode() deve essere chiamata su ciascun nodo foglia):

def parseTree(input): 
    if isinstance (input, list): 
     for item in input: 
      parseTree(item) 
    else: 
     treatLeafNode(item) 

Alla luce della articolo, mi chiedo se c'è un modo semplice per recurse su quello senza utilizzare isinstance() ...

Qualcuno ne sa uno?

Answer 1

La situazione è una di quelle in cui vorrei utilizzare isinstance. La struttura dei dati è ben vincolata e devi distinguere tra un elenco e non un elenco. Utilizzare isinstance per chiedere se si tratta di un elenco. Non dici, ma immagino che le stringhe potrebbero essere tra le foglie del tuo albero, e sono iterabili come lo sono le liste, quindi è un po 'difficile distinguerle in modi che tipizzano le anatre.

Answer 2

Si potrebbe utilizzare

def parseTree(input): 
    try: 
     for item in input: 
      parseTree(item) 
    except TypeError: 
     treatLeafNode(item) 

Si noti che questo sarà anche iterare su stringhe però.

Answer 3

Che cosa potrebbe funzionare meglio è incapsulare la tua struttura ad albero con un oggetto nodo che può contenere un valore e un elenco di figli:

class Node(object): 
    def __init__(self, children=[], value=None): 
     self.children = children 
     self.value = value 
    def isLeaf(self): 
     return len(self.children) == 0 

Ora un nodo è esplicitamente sia una foglia con un valore o un elemento con bambini (tecnicamente, i nodi non foglia possono anche avere valori in questo esempio, ma il codice dell'applicazione può scegliere di imporre che i nodi non foglia non abbiano mai valori). parseTree può essere scritta come:

def parseTree(node): 
    if node.isLeaf(): 
     treatLeafNode(node) 
    else: 
     for child in node.children: 
      parseTree(child) 

Si noti che si tratta di una ricerca in profondità sul legno della croce.

Potrebbero esserci modi migliori per eseguire il wrapping in modo che parseTree sia un metodo di Node, ma questo dovrebbe darvi un'idea. Ovviamente hai ancora il problema che stai chiedendo all'utente di scrivere il codice Python che è un elenco di liste come input, e per analizzarlo nella struttura ad albero sopra devi usare isinstance. Forse yaml sarebbe una scelta migliore del linguaggio di descrizione, in quanto gli utenti non possono quindi inserire codice Python arbitrario nel tuo input?

Answer 4

Che ne dici di usare yaml? Non devi fare anche tu la validazione e la logica del parsing.

L'albero potrebbe apparire come

- [[aMAN],[sTACK, OVER],[FLOW]] 
- [[aMAN1],[sTACK1, OVER1],[FLOW1]] 
- [[aMAN2],[sTACK2, OVER2],[FLOW2]] 

Codice di analizzarlo

import yaml      
f= open('test.yml') 
test = yaml.load(f.read()) 
print test 

uscita:

[[['aMAN'], ['sTACK', 'OVER'], ['FLOW']], [['aMAN1'], ['sTACK1', 'OVER1'], ['FLOW1']], [['aMAN2'], ['sTACK2', 'OVER2'], ['FLOW2']]] 

Answer 5

C'è un motivo per cui hai scelto una lista di liste come la tua struttura ad albero preferita? Posso pensare a molti modi migliori per scriverne uno in un file di configurazione. Supponiamo che si sta cercando di codificare:

a 
|-- b 
| |-- c 
| |-- d 
| | |-- e 
| | `-- f 
| `-- g 
|  `-- h 
|-- i 
`-- j 
    `-- k 

Come su

a: b, i, j 
b: c, d, g 
d: e, f 
g: h 
j: k 

È possibile analizzare che in un dizionario abbastanza facilmente, e unirsi in su in un albero. In effetti, penso che lo ConfigParser lo farà già per te.

Oppure, come circa:

a 
----b 
--------c 
--------d 
------------e 
------------f 
--------g 
------------h 
----i 
----j 
--------k