Tipos de datos recursivos en Python
¿Cuál podría ser la cosa en Python que está más cerca de los tipos de datos recursivos en Haskell? (es decir, usar la propia definición del tipo mientras se define a sí mismo).
Editar:
Para dar una definición más concreta de un tipo recursivo, a continuación se muestra un árbol binario en Haskell:
data Tree a = Leaf a | Branch (Tree a) (Tree a)
La forma en que leo esto es como lo siguiente: un árbol binario puede ser una hoja o puede contener dos subárboles que son nuevamente el árbol de tipos en sí.
Para obtener más información sobre los tipos recursivos en Haskell, puede consultar aquí: https://www.haskell.org/tutorial/goodies.html
Lo que realmente tenía en mente era convertir una definición de árbol de palabras en Haskell a Python. Esta es la definición de WordTreeun antiguo proyecto mío:
data WordTree = Word String | Subword String [WordTree] | Root [WordTree]
A WordTreees una estructura de n-árboles donde los prefijos comunes de palabras se almacenan en los padres y las partes restantes se almacenan en la hoja de los árboles de manera ordenada. Creo que esta definición de tipo es algo similar a un Trie. Sin embargo, como Haskell es un lenguaje de programación funcional, permite que esta definición de tipo sea recursiva. ¿Qué podría ser lo más parecido en Python (o tal vez, en la programación orientada a objetos, en general) a este tipo de definición de un tipo?
Respuestas
Dado que Python se escribe dinámicamente, no hay ningún problema para definir las clases que necesita.
class Tree:
left = None
right = None
def __init__(self, left, right):
self.left = left
self.right = right
Incluso si está interesado en escribir estas definiciones, puede hacerlo como en cualquier otro lenguaje orientado a objetos basado en clases:
from typing import Union
class Tree:
left: Union['Tree', int]
right: Union['Tree', int]
def __init__(self, left: Union['Tree', int], right: Union['Tree', int]) -> None:
self.left = left
self.right = right
Tenga en cuenta el uso de cadenas para el nombre del tipo (que puede evitar en versiones más recientes de Python).
Vea este problema abierto en mypy para tipos algebraicos recursivos directos como
Tree = Union[Tuple['Tree', 'Tree'], int]
La forma más común (aunque no necesariamente recomendada) de definir lo WordTreeque describe es usar una superclase y una jerarquía superficial:
from typing import List, final
class WordTree: pass
@final
class Word(WordTree):
word: str
@final
class Subword(WordTree):
subword: str
children: List[WordTree]
@final
class Root(WordTree):
children: List[WordTree]
El uso de una implementación de este tipo puede requerir el uso de isinstancecomprobaciones (aunque Python3.9 le brinda un buen azúcar para ellas). Los constructores se omiten en este ejemplo para evitar el desorden; es posible que desee utilizar dataclasspara obtenerlos y otros tipos de comportamiento fácilmente.
Hasta la fecha, Python no le brinda ninguna forma de impedir que las clases no relacionadas hereden WordTree, rompiendo así parte de la capacidad de razonar estáticamente sobre tales programas.
Algunos otros lenguajes de programación orientada a objetos, como Scala y Kotlin y (pronto) Java , pueden tomar dicha definición (usando sealedclases ) y proporcionarle comprobaciones de tipo y construcciones sintácticas que son similares a las proporcionadas por lenguajes funcionales como Haskell.
Por lo que sé, este tipo de diseño generalmente se recomienda solo para clases de datos puros, como AST. Es menos adecuado para definir un contenedor orientado al usuario como trie, ya que expone el funcionamiento interno de la estructura de datos. Entonces, incluso si elige ese diseño, es posible que desee usarlo como un detalle de implementación y usar otra clase Trie, para que la use el código del cliente a través de una API bien definida. Esa clase puede tener un WordTreecampo o cualquier otra forma de implementar la misma lógica.
En mi opinión, esto es esencial para ver cómo el diseño orientado a objetos se diferencia del diseño funcional. El último se centra en el flujo de datos y el razonamiento estático, mientras que el primero se centra en las API, la extensibilidad y el desacoplamiento. Creo que es útil tener en cuenta esto cuando se realiza la migración entre lenguajes y entornos, aunque, como se señaló anteriormente, algunos lenguajes intentan habilitar ambos enfoques de diseño.