Рекурсивные типы данных в Python

Question

Что может быть в Python ближе всего к рекурсивным типам данных в Haskell? (т. е. используя собственное определение типа при определении самого себя.)

Редактировать:

Чтобы дать более конкретное определение рекурсивного типа, ниже представлено двоичное дерево в Haskell:

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

Я читаю это примерно так: двоичное дерево может быть либо листом, либо содержать два поддерева, которые снова являются самим деревом типов.

Дополнительную информацию о рекурсивных типах в Haskell вы можете найти здесь: https://www.haskell.org/tutorial/goodies.html

На самом деле я имел в виду преобразование определения дерева слов из Haskell в Python. Это определение WordTreeиз моего старого проекта:

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

A WordTree- это структура n-arytree, в которой общие префиксы слов хранятся в родительских элементах, а оставшиеся части хранятся в листьях деревьев в отсортированном виде. Я считаю, что это определение типа чем-то похоже на Trie. Тем не менее, поскольку Haskell является функциональным языком программирования, он позволяет этому определению типа быть рекурсивным. Что может быть ближе всего в Python (или, может быть, в объектно-ориентированном программировании в целом) к такому типу определения типа?

Answer 1

Поскольку Python имеет динамическую типизацию, нет проблем с определением нужных вам классов.

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

Даже если вы хотите ввести эти определения, вы можете сделать это, как и в любом другом объектно-ориентированном языке, основанном на классах:

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

Обратите внимание на использование строк для имени типа (чего можно избежать в более поздних версиях Python).

См. Эту открытую проблему в mypy для прямых рекурсивных алгебраических типов, таких как

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

---

Наиболее распространенный (хотя и не обязательно рекомендуемый) способ определения WordTreeописываемого вами - это использование суперкласса и неглубокой иерархии:

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]

Использование такой реализации может потребовать использования isinstanceпроверок (хотя Python3.9 дает вам хороший сахар для них). Конструкторы в этом примере опущены, чтобы избежать беспорядка; вы можете захотеть использовать dataclassих, чтобы легко получить их и другие виды поведения.

На сегодняшний день Python не дает вам возможности запретить несвязанным классам наследовать от WordTree, тем самым нарушая некоторую возможность статического анализа таких программ.

Некоторые другие языки ООП, такие как Scala и Kotlin и (скоро) Java , могут принимать такое определение (с использованием sealedклассов ) и предоставлять вам проверки типов и синтаксические конструкции, аналогичные тем, которые предоставляются функциональными языками, такими как Haskell.

---

Насколько мне известно, такой дизайн обычно рекомендуется только для классов чистых данных, таких как AST. Он менее подходит для определения контейнера, обращенного к пользователю, такого как trie, поскольку он раскрывает внутреннюю работу структуры данных. Поэтому, даже если вы выберете этот дизайн, вы можете захотеть использовать его как деталь реализации и использовать другой класс Trie, который будет использоваться клиентским кодом через четко определенный API. У этого класса может быть WordTreeполе или любой другой способ реализации той же логики.

ИМО, это важно для того, чем объектно-ориентированный дизайн отличается от функционального дизайна. Последний фокусируется на потоке данных и статических рассуждениях, тогда как первый фокусируется на API, расширяемости и развязке. Я думаю, что это полезно отметить при переносе между языками и средами - хотя, как отмечалось выше, некоторые языки пытаются задействовать оба подхода к проектированию.