Recursion sobre una lista de listas sin isinstance()

Question

Acabo de leer "isinstance() considered harmful", y parece razonable. En resumen, argumenta para evitar el uso de esta función.

Bueno, ahora estoy escribiendo un programa que toma entradas estructuradas como un árbol, y necesita la información de la estructura del árbol. Sin tiempo para implementar una GUI, le impongo al usuario que la escriba en un archivo de configuración (sé que esta es una mala interfaz, pero el cronograma es muy ajustado). Mis usuarios son muy técnicos, pero no necesariamente conocen Python. Elegí que el archivo contendría listas de listas (de listas de listas, etc.) que representaban los árboles de entrada, y los elementos finales eran los nodos de las hojas de los árboles. Creo que esto es mucho mejor que imponer el sintaxis de diccionarios a los usuarios.

planeo para analizar las listas de forma recursiva como las siguientes (ommiting el uso de la estructura del árbol, vamos a simplificar y decir treatLeafNode() debe ser llamado en cada nodo hoja):

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

A la luz de la artículo, me pregunto si hay una manera simple de recurse sobre eso sin usar isinstance() ...

¿Alguien sabe uno?

Answer 1

Su situación es una de esas en las que usaría isinstance. Su estructura de datos está bien restringida y necesita distinguir entre una lista y no una lista. Use isinstance para preguntar si se trata de una lista. No lo dices, pero imagino que las cadenas pueden estar entre las hojas de tu árbol, y son iterables como lo son las listas, por lo que es complicado distinguirlas en forma de pato.

Answer 2

Usted podría utilizar

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

Tenga en cuenta que esto también va a iterar sobre las cadenas sin embargo.

Answer 3

Lo que puede funcionar mejor se encapsula la estructura de árbol con un objeto de nodo que puede contener un valor y una lista de los niños:

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

Ahora un nodo es explícita, ya sea una hoja con un valor o un elemento con niños (técnicamente, los nodos de hoja también pueden tener valores en este ejemplo, pero el código de la aplicación puede elegir forzar que los nodos de hoja nunca tengan valores). parseTree se puede escribir como:

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

Tenga en cuenta que se trata de una búsqueda en profundidad en el árbol.

Puede haber formas más agradables de resumir esto para que parseTree sea un método de Node, pero esto debería darle una idea. Por supuesto, todavía tiene el problema de que le está pidiendo al usuario que escriba el código de Python, que es listas de listas como entrada, y para analizar eso en la estructura de árbol anterior que necesitaría usar isinstance. Tal vez yaml sería una mejor opción de lenguaje de descripción, ya que los usuarios no pueden luego inyectar código Python arbitrario en su entrada?

Answer 4

¿Qué le parece usar yaml? Tampoco tendrá que hacer la validación y la lógica de análisis usted mismo.

El árbol podría parecerse a

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

código para analizar que

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

Salida:

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

Answer 5

¿Existe una razón por la que usted ha elegido una lista de listas como ¿tu estructura de árbol preferida? Puedo pensar en muchas mejores formas de escribir uno en un archivo de configuración. Supongamos que usted está tratando de codificar:

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

¿Qué tal

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

Puede analizar esto en un diccionario con bastante facilidad, y unirlo a un árbol. De hecho, creo que ConfigParser ya lo hará por ti.

O si no, ¿qué tal:

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