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]

AWordTree是一种n-芳基树结构，其中单词的公共前缀存储在父级，其余部分以排序方式存储在树的叶子上。我相信这个类型定义有点类似于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中的open issue以了解直接递归代数类型，例如

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.10为这些检查提供了nice sugar）。本例中省略了构造函数以避免混乱；您可能希望使用^{}轻松地获取它们和其他类型的行为

到目前为止，Python无法禁止不相关的类从WordTree继承，从而破坏了对此类程序进行静态推理的能力

其他一些OOP语言，如Scala和Kotlin以及（很快）Java，可以采用这样的定义（使用^{} classes），并提供与Haskell等函数式语言类似的类型检查和语法结构

---

据我所知，这种设计通常只推荐用于纯数据类，如AST。它不太适合定义面向用户的容器，如trie，因为它公开了数据结构的内部工作。因此，即使您采用这种设计，您也可能希望将其用作实现细节，并使用另一个类Trie，供客户机代码通过定义良好的API使用。该类可以有一个WordTree字段，或者实现相同逻辑的任何其他方式

在我看来，这对于面向对象设计与功能设计的区别至关重要。后者侧重于数据流和静态推理，而前者侧重于API、可扩展性和解耦。我认为，当在语言和环境之间进行移植时，注意这一点很有帮助——尽管如上所述，有些语言试图同时启用这两种设计方法