Haskell等价于Python中的数据构造函数？

Question

在Haskell中，我可以定义一个二叉树，如下所示：

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

然后我可以对其进行如下操作：

^{pr2}$

我知道Python在Haskell中没有等价的data。如果有，请告诉我。在

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

Answer 1

我要找一个类似Haskell的函数式编程。从某种意义上说，这不是很“Python”。尤其是，它不是面向对象的。不过，它仍然有用而且干净。在

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

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")

调用此构造函数有点不方便，因此请使用一些易于使用的智能构造函数：

^{pr2}$

我们如何得到价值观？我们也来做些帮手吧：

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))

Answer 2

最接近的可能是带有方法的类：

class Leaf:
    def __init__(self, value):
        self.value = value

    def height(self):
        return 1

    def count(self):
        return 1


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

    def height(self):
        return 1 + max(self.left.height(), self.right.height())

    def count(self):
        return 1 + self.left.count() + self.right.count()

虽然这有点老生常谈，有它自己的优点，但它也缺乏Haskell版本的一些特性。最重要的是，函数定义必须与类一起在同一个模块中定义。您可以使用single-dispatch generic functions而不是方法来取回它。其结果是比方法和Haskell函数更开放的，并且允许在有益的情况下跨多个模块扩展定义。在

^{pr2}$

Answer 3

“构造函数”没有“Python数据”的概念。您可以像大多数其他OOP语言一样创建类。或者，您可以始终用内置模块表示数据类型，并且只定义处理它们的函数（这是用于在heapq内置模块中实现堆的方法）。在

python和haskell之间的差异是巨大的，因此最好避免在haskell和python的语法/特性之间进行严格的比较，否则您最终将编写出非python和低效的python代码。在

即使python确实有一些函数特性，它仍然是一种函数式语言，因此您必须彻底改变程序的范式，以获得可读、python和高效的程序。在

---

使用类的一个可能的实现可以是：

class Bint(object):
    def __init__(self, value, left=None, right=None):
        self.a = value
        self.left = left
        self.right = right

    def height(self):
        left_height = self.left.height() if self.left else 0
        right_height = self.right.height() if self.right else 0
        return 1 + max(left_height, right_height)

    def count(self):
        left_count = self.left.count() if self.left else 0
        right_height = self.right.count() if self.right else 0
        return 1 + left_count + right_count

代码可以简化一点，为left和right提供一个“更聪明”的默认值：

^{pr2}$

注意，这些实现只允许节点有一个子节点。在

但是，您没有使用类来定义数据类型。 例如，您可以说Bint可以是单个元素的列表、根的值，或者包含三个元素的列表：value、left child和right child。在

在这种情况下，可以将函数定义为：

def height(bint):
    if len(bint) == 1:
        return 1
    return 1 + max(height(bint[1]), height(bint[2]))

def count(bint):
    if len(bint) == 1:
    return 1 + count(bint[1]) + count(bint[2])

另一种方法是使用namedtuples：

from collections import namedtuple

Leaf = namedtuple('Leaf', 'value')
Branch = namedtuple('Branch', 'value left right')

def height(bint):
    if len(bint) == 1: # or isinstance(bint, Leaf)
        return 1
    return 1 + max(height(bint.left), height(bint.right))

def count(bint):
    if len(bint) == 1:  # or isinstance(bint, Leaf)
    return 1 + count(bint.left) + count(bint.right)