python - 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 结构，其中单词的公共(public)前缀存储在父级，其余部分以排序方式存储在树的叶子上。我相信这个类型定义有点类似于 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 版本中可以避免这种情况)。
看到这个 open issue在 mypy 中用于直接递归代数类型，例如

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

定义 WordTree 的最常见(虽然不一定推荐)方式您描述的是使用父类(super class)和浅层次结构:

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)。在这个例子中省略了构造函数以避免困惑；您可能想使用 dataclass 轻松获得它们和其他类型的行为。
迄今为止，Python 无法禁止不相关的类从 WordTree 继承。 ，从而破坏了对此类程序进行静态推理的一些能力。
其他一些 OOP 语言，例如 Scala 和 Kotlin 以及(很快) Java , 可以采用这样的定义(使用 sealed classes )并为您提供类似于 Haskell 等函数式语言所提供的类型检查和句法结构。

据我所知，这种设计通常只推荐用于纯数据类，例如 AST。它不太适合定义面向用户的容器，例如 trie，因为它暴露了数据结构的内部工作原理。因此，即使您采用该设计，您也可能希望将其用作实现细节，并使用另一个类 Trie , 由客户端代码通过定义良好的 API 使用。该类可以有一个 WordTree字段，或任何其他实现相同逻辑的方式。
IMO 这对于面向对象设计与功能设计的不同至关重要。后者侧重于数据流和静态推理，而前者侧重于 API、可扩展性和解耦。我认为这有助于在语言和环境之间移植时注意 - 尽管如上所述，某些语言尝试启用这两种设计方法。