Python で木構造を扱う

関数型言語でよく使われるデータ構造にはリスト型以外に木構造がある。Haskell の場合には木構造は代数的データ型で定義する。例えば次のようにノードには左右の木構造を収め、リーフに文字列を収めるデータ構造 Tree を定義する。

Prelude> data Tree = Node Tree Tree | Leaf String deriving Show
Prelude> let a = Node (Leaf "hello") (Node (Leaf "world") (Leaf "."))

この木構造のリーフの値を列挙する go_around 関数は次のように再帰的に定義できる。

Prelude> :{
Prelude| let
Prelude| go_around (Leaf str) = [str]
Prelude| go_around (Node left right) = go_around(left) ++ go_around(right)
Prelude| :}
Prelude> go_around a
["hello","world","."]

Python で木構造を定義するには、ノードとリーフのデータ型をクラスで定義する。Haskell で代数的データ型で定義したところを、Python ではクラスを定義することで木構造のデータ型を作ることになる。代数的データ型のデータがクラスのインスタンスに相当するわけだ。こう考えると、クラスの定義の、新しいデータ型を定義するという一面が明らかになる。あるいは、オブジェクト指向言語のクラスの性質の一部は Haskell の代数的データ型として捉えることができることが分かる。

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

class Leaf:
    def __init__(self,data):
        self.data = data
    def get(self):
        return self.data
def go_around(tree):
    if isinstance(tree, Leaf):
        return [tree.get()]
    else:
        return go_around(tree.left) + go_around(tree.right)

a = Node(Leaf('hello'), Node(Leaf(','), Leaf('world')))
print(go_around(a))

実行例

================== RESTART: C:/Users/****/Desktop/tree.py ==================
['hello', ',', 'world']

このように、Haskell の代数的データ型とPythonのクラス定義の意味合いが同じ事が分かる。どんなプログラム言語であれ、プログラムをデータ構造とアルゴリズムとして捉えるとそれらのプログラム言語の本質をとらえて活用できるような気がする。データ構造とアルゴリズムへのアプローチの仕方に言語の特徴がみられるだけだからだ。
Python という言語の使い方がなんとなくわかった気がするので Python 関係の記事はこれで終わりにする。AI との関連性についてはもう少し沈黙して勉強しないといけない。


[PR]
by tnomura9 | 2018-01-08 15:49 | Python | Comments(0)
<< Python datetime... list.pop() >>