自上次更新以来五年,但这是我的答案。
使data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Show)
python...
没有类型检查(更像 python)
class Tree:
def __init__(self):
pass
def height(self):
pass
def count(self):
pass
class Leaf(Tree):
def __init__(self, value):
self.value = value
def __str__(self):
return("Leaf " + str(self.value))
def height(self):
return 1
def count(self):
return 1
class Branch(Tree):
def __init__(self, left, right):
if isinstance(left, Tree) and isinstance(right, Tree):
self.left = left
self.right = right
else:
raise ValueError
def __str__(self):
return("Branch (" + str(self.left) + " " +
str(self.right) + ")")
def height(self):
return 1 + max(self.left.height(), self.right.height())
def count(self):
return 1 + self.left.count() + self.right.count()
#usage : Branch(Leaf(5), Branch(Leaf(3), Leaf(2)))
使用类型检查(更像是 haskell)
height
, count
Tree 类的方法
class Tree:
def __init__(self, tree, type_):
def typecheck(subtree):
if isinstance(subtree, Leaf):
if not isinstance(subtree.value, type_):
print(subtree.value)
raise ValueError
elif isinstance(subtree, Branch):
typecheck(subtree.left)
typecheck(subtree.right)
else:
raise ValueError
typecheck(tree)
self.tree = tree
self.type_ = type_
def __str__(self):
return ("Tree " + self.type_.__name__ + "\n" + str(self.tree))
def height(self):
if isinstance(self, Leaf):
return 1
elif isinstance(self, Branch):
return 1 + max(self.left.height(), self.right.height())
else:
return self.tree.height()
def count(self):
if isinstance(self, Leaf):
return 1
elif isinstance(self, Branch):
return 1 + self.left.count() + self.right.count()
else:
return self.tree.count()
class Leaf(Tree):
def __init__(self, value):
self.value = value
def __str__(self):
return("Leaf " + str(self.value))
class Branch(Tree):
def __init__(self, left, right):
if isinstance(left, Tree) and isinstance(right, Tree):
self.left = left
self.right = right
else:
raise ValueError
def __str__(self):
return("Branch (" + str(self.left) + " " +
str(self.right) + ")")
#usage tree1 = Tree(Branch(Leaf(5), Branch(Leaf(3), Leaf(2))), int)
#usage tree1.height() -> 3
#usage tree1.count() -> 5
height
, count
Leaf 和 Branch 类的方法
class Tree:
def __init__(self, tree, type_):
def typecheck(subtree):
if isinstance(subtree, Leaf):
if not isinstance(subtree.value, type_):
print(subtree.value)
raise ValueError
elif isinstance(subtree, Branch):
typecheck(subtree.left)
typecheck(subtree.right)
else:
raise ValueError
typecheck(tree)
self.tree = tree
self.type_ = type_
def __str__(self):
return ("Tree " + self.type_.__name__ + "\n" + str(self.tree))
def height(self):
return self.tree.height()
def count(self):
return self.tree.count()
class Leaf(Tree):
def __init__(self, value):
self.value = value
def __str__(self):
return("Leaf " + str(self.value))
def height(self):
return 1
def count(self):
return 1
class Branch(Tree):
def __init__(self, left, right):
if isinstance(left, Tree) and isinstance(right, Tree):
self.left = left
self.right = right
else:
raise ValueError
def __str__(self):
return("Branch (" + str(self.left) + " " +
str(self.right) + ")")
def height(self):
return 1 + max(self.left.height(), self.right.height())
def count(self):
return 1 + self.left.count() + self.right.count()
#usage Tree(Branch(Leaf(5), Branch(Leaf(3), Leaf(2))), int)
#usage tree1.height() -> 3
#usage tree1.count() -> 5
height
,count
类外的方法(最像haskell)
class Tree:
def __init__(self, tree, type_):
def typecheck(subtree):
if isinstance(subtree, Leaf):
if not isinstance(subtree.value, type_):
print(subtree.value)
raise ValueError
elif isinstance(subtree, Branch):
typecheck(subtree.left)
typecheck(subtree.right)
else:
raise ValueError
typecheck(tree)
self.tree = tree
self.type_ = type_
def __str__(self):
return ("Tree " + self.type_.__name__ + "\n" + str(self.tree))
class Leaf(Tree):
def __init__(self, value):
self.value = value
def __str__(self):
return("Leaf " + str(self.value))
class Branch(Tree):
def __init__(self, left, right):
if isinstance(left, Tree) and isinstance(right, Tree):
self.left = left
self.right = right
else:
raise ValueError
def __str__(self):
return("Branch (" + str(self.left) + " " +
str(self.right) + ")")
def height(tree):
if not isinstance(tree, Tree):
raise ValueError
if isinstance(tree, Leaf):
return 1
elif isinstance(tree, Branch):
return 1 + max(height(tree.left), height(tree.right))
else:
return height(tree.tree)
def count(tree):
if not isinstance(tree, Tree):
raise ValueError
if isinstance(tree, Leaf):
return 1
elif isinstance(tree, Branch):
return 1 + count(tree.left) + count(tree.right)
else:
return count(tree.tree)
#usage tree1 = Tree(Branch(Leaf(5), Branch(Leaf(3), Leaf(2))), int)
#usage height(tree1) -> 3
#usage count(tree1) -> 5