Recursive data types in Python

Question

What might be the thing in Python that is closest to the to the recursive data types in Haskell? (i.e. using the type's own definition while defining itself.)

Edit:

To give a more concrete definition of a recursive type, below is a binary tree in Haskell:

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

How I read this is like the following: A binary tree can either be a leaf, or can contain two sub-trees which are again the type tree itself.

For further information about recursive types in Haskell, you can refer to here: https://www.haskell.org/tutorial/goodies.html

What I actually had in mind was converting a word tree definition in Haskell to Python. This is the definition of the WordTree from an old project of mine:

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

A WordTreejest strukturą n-arytree, w której wspólne przedrostki słów są przechowywane u rodziców, a pozostałe części są przechowywane na liściach drzew w posortowany sposób. Uważam, że ta definicja typu jest nieco podobna do Trie. Ponieważ jednak Haskell jest funkcjonalnym językiem programowania, pozwala na rekurencję tej definicji typu. Co może być najbliższe w Pythonie (a może ogólnie w programowaniu obiektowym) dla tego rodzaju definicji typu?

Answer 1

Ponieważ Python jest typowany dynamicznie, nie ma problemu z definiowaniem potrzebnych klas.

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

Nawet jeśli chcesz wpisać te definicje, możesz to zrobić tak, jak w każdym innym języku obiektowym opartym na klasach:

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

Zwróć uwagę na użycie ciągów znaków w nazwie typu (czego można uniknąć w nowszych wersjach Pythona).

Zobacz ten otwarty problem w mypy dla bezpośrednich rekurencyjnych typów algebraicznych, takich jak

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

---

Najczęstszym (choć niekoniecznie zalecanym) sposobem definiowania WordTreeopisywanego obiektu jest użycie nadklasy i płytkiej hierarchii:

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]

Korzystanie z takiej implementacji może wymagać użycia isinstancesprawdzeń (chociaż Python3.9 daje do tego niezłą cukier ). W tym przykładzie pominięto konstruktory, aby uniknąć bałaganu; możesz chcieć użyć, dataclassaby je łatwo zdobyć i inne rodzaje zachowań.

Do tej pory Python nie daje możliwości uniemożliwienia dziedziczenia niepowiązanych klas z WordTree, co ogranicza możliwość statycznego wnioskowania o takich programach.

Niektóre inne języki OOP, takie jak Scala i Kotlin oraz (wkrótce) Java , mogą przyjąć taką definicję (przy użyciu sealedklas ) i dać ci sprawdzanie typów i konstrukcje składniowe, które są podobne do tych, które są podawane przez języki funkcjonalne, takie jak Haskell.

---

Z tego, co wiem, ten rodzaj projektowania jest zwykle zalecany tylko dla klas czystych danych, takich jak AST. Jest mniej odpowiedni do definiowania kontenera skierowanego do użytkownika, takiego jak trie, ponieważ ujawnia wewnętrzne działanie struktury danych. Więc nawet jeśli pójdziesz z tym projektem, możesz chcieć użyć go jako szczegółu implementacji i użyć innej klasy Trie, która będzie używana przez kod klienta za pośrednictwem dobrze zdefiniowanego interfejsu API. Ta klasa może mieć WordTreepole lub inny sposób implementacji tej samej logiki.

IMO this is essential to how object-oriented design differs from functional design. The latter focuses on data flow and on static reasoning, whereas the former focuses on APIs, extensibility and decoupling. I think this is helpful to note, when porting between languages and environments - though as noted above, some languages try to enable both design approaches.