6

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)

dataPython には Haskellに相当するものがないことは知っています。もしあれば教えてください。

では、Python で二分木をどのように定義し、上記の 2 つの関数をどのように実装するのでしょうか?

4

4 に答える 4

4

ここでは、関数型プログラミングである 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))
于 2013-09-03T09:14:53.970 に答える
3

最も近いのは、おそらくメソッドを持つクラスでしょう。

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 バージョンのいくつかの品質も欠いています。最も重要なことは、同じモジュール内で関数定義をクラスと一緒に定義する必要があることです。メソッドの代わりに単一ディスパッチのジェネリック関数を使用して、それを取り戻すことができます。その結果、メソッドと Haskell 関数の両方よりもオープンな世界になり、有益な場合は複数のモジュールに定義を広げることができます。

@singledispatch
def height(_):
    raise NotImplementedError()

@singledispatch
def count(_):
    raise NotImplementedError()

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

@height.register(Leaf)
def height_leaf(leaf):
    return 1

@height.register(Leaf)
def count_leaf(leaf):
    return 1    

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

@height.register(Branch)
def height_branch(b):
    return 1 + max(b.left.height(), b.right.height())

@count.register(Branch)
def count_branch(b):
    return 1 + b.left.count() + b.right.count()
于 2013-09-03T08:44:43.167 に答える
1

Python には、Haskell のような「データ コンストラクター」の概念がありません。他のほとんどの OOP 言語と同様に、クラスを作成できます。別の方法として、常にビルトインでデータ型を表現し、それらを処理する関数のみを定義することもできます (これは、heapqビルトイン モジュールでヒープを実装するために使用されるアプローチです)。

Python と Haskell の違いは非常に大きいため、Haskell と Python の構文/機能を厳密に比較することは避けたほうがよいでしょう。そうしないと、非 Pythonic で非効率的な Python コードを作成することになります。

Python に関数型の機能がいくつかあるとしても、それは関数型言語ではないため、プログラムのパラダイムを完全に変更して、読みやすく、pythonic で効率的なプログラムを取得する必要があります。

クラスを使用した可能な実装は次のとおりです。

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。

class Nil(object):
    def height(self):
        return 0
    count = height

nil = Nil()

class Bint(object):
    def __init__(self, value, left=nil, right=nil):
        self.value = value
        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()

これらの実装では、子を 1 つだけ持つノードが許可されることに注意してください。

ただし、クラスを使用してデータ型を定義する必要はありません。たとえば、Binta は単一の要素のリスト、ルートの値、または値、左の子、右の子の 3 つの要素を持つリストであると言えます。

この場合、関数を次のように定義できます。

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)
于 2013-09-03T08:39:02.677 に答える