Haskell 相当于 Python 中的数据构造函数？

Question

在 Haskell 中，我可以如下定义二叉树：

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

然后我可以对它进行一些操作，如下所示：

height (Leaf a) = 1
height (Branch a l r) = 1 + (max (height l) (height r))

count (Leaf a) = 1
count (Branch a l r) = 1 + (count l) + (count r) 

我知道 Pythondata在 Haskell中没有等效项。如果有，请告诉。

那么，如何在Python中定义一棵二叉树以及如何在其中实现上述两个功能呢？

Answer 1

使用最现代的 python 习惯用法的答案是你需要：

• 类型注释
• Python 3.10+ 支持结构模式匹配
• 支持递归类型别名的静态类型检查工具（mypy、pyright）
• frozen=True用于定义不变性的数据类

from __future__ import annotations

from dataclasses import dataclass
from typing import Generic, TypeAlias, TypeVar

A = TypeVar("A")
L = TypeVar("L")
R = TypeVar("R")


@dataclass(frozen=True)
class Leaf(Generic[A]):
    value: A


@dataclass(frozen=True)
class Branch(Generic[A, L, R]):
    root: A
    left: L
    right: R


Bint: TypeAlias = Leaf[A] | Branch[A, "Bint[A]", "Bint[A]"]


def height(x: Bint[A]) -> int:
    match x:
        case Leaf():
            return 1
        case Branch(_, l, r):
            return 1 + max(height(l), height(r))


def count(x: Bint[A]) -> int:
    match x:
        case Leaf():
            return 1
        case Branch(_, l, r):
            return 1 + count(l) + count(r)

与其他答案相比，这个答案的优点是：

• 您可以完全删除运行时类型检查（isinstance），使代码读取更加简单和高效
• 当使用联合类型而不是超类时Leaf, Branch，可以进行详尽检查，因此如果match没有警告输入，则您的程序是正确的。

Answer 2

我将在这里进行与 Haskell 非常相似的函数式编程。从某种意义上说，这并不是很“Pythonic”。特别是，它不是面向对象的。不过，它仍然有用且干净。

数据类型是一个类。具有多个数据构造函数的数据类型是一个具有有关如何构造的额外信息的类。当然，它需要一些数据。使用构造函数来确保所有树都是合法的：

class BinTree (object):
    def __init__(self, value=None, left=None, right=None):
        if left == None and right == None and value != None:                
            self.isLeaf = True
            self.value = value
        elif left != None and right != None and value == None:
            self.isLeaf = False
            self.value = (left, right)
        else:
            raise ArgumentError("some help message")

这个构造函数调用起来有点不方便，所以有一些易于使用的智能构造函数：

def leaf(value):
    return BinTree(value=value)

def branch(left, right):
    return BinTree(left=left, right=right)

我们如何把这些值取出来呢？让我们也为此做一些助手：

def left(tree):
    if tree.isLeaf:
        raise ArgumentError ("tree is leaf")
    else:
        return tree.value[0]

def right(tree):
    if tree.isLeaf:
        raise ArgumentError ("tree is leaf")
    else:
        return tree.value[1]

def value(tree):
    if not tree.isLeaf:
        raise ArgumentError ("tree is branch")
    else:
        return tree.value

就是这样。您得到了一个纯“代数”数据类型，可以使用函数访问它：

def count(bin_tree):
    if bin_tree.isLeaf:
        return 1
    else:
        return count(left(bin_tree))+count(right(bin_tree))