Tipos de dados recursivos em Python

Question

O que pode ser a coisa em Python que está mais próxima dos tipos de dados recursivos em Haskell? (ou seja, usando a própria definição do tipo ao definir a si mesmo.)

Editar:

Para dar uma definição mais concreta de um tipo recursivo, abaixo está uma árvore binária em Haskell:

data Tree a             = Leaf a | Branch (Tree a) (Tree a) 

Como eu li isso é o seguinte: Uma árvore binária pode ser uma folha ou pode conter duas subárvores que são novamente a própria árvore de tipo.

Para obter mais informações sobre os tipos recursivos em Haskell, você pode consultar aqui: https://www.haskell.org/tutorial/goodies.html

O que eu realmente tinha em mente era converter uma definição de árvore de palavras em Haskell para Python. Esta é a definição de WordTreeum antigo projeto meu:

data WordTree = Word String | Subword String [WordTree] | Root [WordTree]

A WordTreeé uma estrutura n-arytree onde prefixos comuns de palavras são armazenados nos pais e as partes restantes são armazenadas na folha das árvores de uma maneira ordenada. Eu acredito que esta definição de tipo é um pouco semelhante a um Trie. No entanto, como Haskell é uma linguagem de programação funcional, permite que essa definição de tipo seja recursiva. O que pode ser a coisa mais próxima em Python (ou talvez, em programação orientada a objetos, em geral) para esse tipo de definição de um tipo?

Answer 1

Como o Python é tipado dinamicamente, não há problema em definir as classes de que você precisa.

class Tree:
    left = None
    right = None
    def __init__(self, left, right):
        self.left = left
        self.right = right

Mesmo se você estiver interessado em digitar essas definições, você pode fazer isso como em qualquer outra linguagem orientada a objetos baseada em classe:

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

Observe o uso de strings para o nome do tipo (que você pode evitar nas versões mais recentes do Python).

Veja este problema aberto em mypy para tipos algébricos recursivos diretos, como

Tree = Union[Tuple['Tree', 'Tree'], int]

---

A maneira mais comum (embora não necessariamente recomendada) de definir o que WordTreevocê descreve é ​​usando uma superclasse e uma hierarquia 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]

Usar tal implementação pode exigir o uso de isinstanceverificações (embora Python3.9 forneça um bom açúcar para elas). Construtores são omitidos neste exemplo para evitar confusão; você pode querer usar dataclasspara obtê-los, e outros tipos de comportamento, facilmente.

Até o momento, o Python não oferece nenhuma maneira de impedir que classes não relacionadas herdem de WordTree, interrompendo assim parte da capacidade de raciocinar estaticamente sobre tais programas.

Algumas outras linguagens OOP, como Scala e Kotlin e (em breve) Java , podem aceitar essa definição (usando sealedclasses ) e fornecer verificações de tipo e construções sintáticas semelhantes às fornecidas por linguagens funcionais como Haskell.

---

Pelo que sei, esse tipo de design geralmente é recomendado apenas para classes de dados puros, como ASTs. É menos adequado para definir o contêiner voltado para o usuário, como trie, uma vez que expõe o funcionamento interno da estrutura de dados. Portanto, mesmo se você seguir esse design, talvez queira usá-lo como um detalhe de implementação e usar outra classe,, Triepara ser usada pelo código do cliente por meio de uma API bem definida. Essa classe pode ter um WordTreecampo, ou qualquer outra forma de implementar a mesma lógica.

IMO, isso é essencial para saber como o design orientado a objetos difere do design funcional. O último se concentra no fluxo de dados e no raciocínio estático, enquanto o primeiro se concentra em APIs, extensibilidade e desacoplamento. Acho que isso é útil observar, ao fazer a portabilidade entre linguagens e ambientes - embora, conforme observado acima, algumas linguagens tentem habilitar ambas as abordagens de design.