オブジェクトの相互参照 と 関数の相互再帰 (1)

オブジェクトの相互参照

例えば、「人」には「名前」があり、将来一人の「パートナー」を得ることができるとする。生まれたてはパートナーがいない状態。「結婚」によりパートナーを得て、「離婚」によりパートナーを失う。ただし、結婚により相互に参照することが可能だとする。これを示したのが下図。

Python で表現するなら、まずはインスタンス変数と get メソッド、print 文に対応するための __str__() を定義。 (cf. print 文でオブジェクトの情報を表示)

class Person:
    def __init__(self, name):
        self.__name = name
        self.__partner = None

    def getName(self): return self.__name

    def __str__(self):
        return self.__name + "<" + (self.__partner.getName() if self.__partner else "None") + ">"

次に、結婚したとき相互に参照できるよう marry() メソッドを定義。既にパートナーがいるときは何もしないことにする。

class Person …

    def marry(self, partner):
        u""" 結婚 """
        if self.__partner: return
        self.__partner = partner
        partner.marry(self)

離婚したときはパートナーを参照できないようにする。ただし、パートナーがいないときは何もしない。

class Person …

    def divorce(self):
        u""" 離婚 """
        if not self.__partner: return
        partner = self.__partner
        self.__partner = None
        partner.divorce()

動作を確かめる。

tarou  = Person("Tarou")
hanako = Person("Hanako")

# 結婚
tarou.marry(hanako)
print tarou, hanako  #=> Tarou<Hanako> Hanako<Tarou>

# 離婚
hanako.divorce()
print tarou, hanako  #=> Tarou<None> Hanako<None>

コード全体はこちら。

 

相互再帰

Python ではオブジェクトが相互参照している状態と、その後、参照をなくすという変化を自然に記述することができる。ここで自然と感じるのは、自分が考える枠組みがそれに馴染んでいるということに過ぎない。では、これと同様のことを表現するのに Haskell ではどうすればいいのだろう？ ただし、まずはオブジェクトシステムにおけるオブジェクト識別子 (OID) のようなものついて考慮しない。

ところで、「相互参照」から連想するのは「相互再帰」という言葉。これは Haskell の let 式の説明で出てきた。

let 式によってつくられる束縛の集りは、相互再帰的 ( mutually recursive )で、パターン束縛は遅延パターンとして扱われます

(A Gentle Introduction to Haskell: Patterns の let 式 より)

Let 式 は let { d₁ ; ... ; d_n } in e という一般形式を持ち、入れ子でレキシカルスコープで相互再帰的な宣言リスト (このような let は他の言語ではよく letrec と呼ばれる) を持つ。

(Haskell 98 Report: 式 の 3.12 let 式 より)

Haskell に限らず一般的な意味として、相互再帰 - Wikipedia によると、

再帰呼び出しの一種であり、2つの関数が互いを使って定義されているものをいう。

 

相互再帰の例

この例として、Mutual recursion - Wikipedia には、数字が奇数であるか (odd?) 偶数か (even?) 判定する関数が互いを使って定義されている。

function even?(number : Integer)
    if number == 0 then
        return true
    else
        return odd?(abs(number)-1)

function odd?(number : Integer)
    if number == 0 then
        return false
    else
        return even?(abs(number)-1)

0 をベースにして、even? は odd? を、odd? は even? を使って定義しているのがわかる。

(cf. Fun with Functional Dependencies における定義も興味深い。理解できてないんだけど… ^^; )

 

また、A Gentle Introduction to Haskell: Patterns の “4.4 遅延パターン” の例 においても、サーバとクライアントのやりとりを表現した関数が定義されているが、ここでもリクエスト (reqs) とレスポンス (resps) が互いを使って定義されている。

reqs                     = client init resps
resps                    = server reqs

A Gentle Introduction to Haskell: Patterns via kwout

このように、オブジェクトが相互参照している状態は、関数の相互再帰によって表現できそう。

 

相互再帰的な関数 (値) の定義

上記を真似て、Person 型の値を相互再帰的に定義することに。まずは Person 型を定義。その後、let 式において互いを使って値を表現する。

ところで、値を生成するのはデータコンストラクタと呼ばれるが、上記の Person 型を調べればわかるように、

*Main> :t Person
Person :: String -> Partner -> Person

データコンストラクタは関数と似ている。違うのはパターンマッチで利用できるということ。よって、データコンストラクタで値を生成するときに、他の式を参照することは関数の相互再帰と同じと考えても良さげ。

data Person = Person { name    :: String
                     , partner :: Person
                     } 

instance Show Person where
    show (Person n p) = n ++ "{" ++ name p ++ "}"

main = do let tarou  = Person "Tarou"  hanako
              hanako = Person "Hanako" tarou
          print tarou  -- Tarou{Hanako}
          print hanako -- Hanako{Tarou}

tarou は hanako を使って定義し、hanako は tarou を使って定義した。

しかし、これは一見奇妙に思える。なぜなら先ほどの Python の例で、Person クラスのコンストラクタの定義を変更して、パートナーも引数として渡せるようにしたとする。

class Person:
    def __init__(self, name, partner):
        self.__name = name
        self.__partner = partner

このクラスを使って以下のように互いを参照するオブジェクトの生成を試みる。

tarou  = Person("Tarou", hanako)
hanako = Person("Hanako", tarou)

実行した結果は、

NameError: name 'hanako' is not defined

変数 tarou に Person 型のオブジェクトを代入しようとしても、オブジェクトを生成する段階でパートナーである hanako がいないのでエラー。上から下へとプログラムが順次実行され、状態の変化を記述するのが命令型言語の特徴なので、エラーが出て当り前。極めて当然な結果。

しかし、同じ目線で Haskell のコードを見ると、「hanako を定義する前に、tarou の定義で hanako を参照しているからコンパルエラーにならないの？」と思えてしまう。これは、そもそも let 式における定義は順序に意味はなく、何が何を参照して定義しているかを表現しているに過ぎないことによる。

延々と再帰呼出しが続かないよう 適切に Person 型を Show クラスのインスタンスにすれば、print 関数の呼出しも問題なし。もし、Person 型で deriving Show とした場合は出力が無限に続く。 tarou のパートナーは hanakoで、hanako のパートナーは tarou で、tarou のパートナーは… というように。

 

Maybe a 型を使ってパートナーが存在しないことを表現

相互再帰的な定義ができることがわかったので、次は Python と同じように、

1. 最初に値を生成したときはパートナーが存在しない
2. 結婚によりパートナーができる
3. 離婚によりパートナーを失う

という方向へ変更してみる。

パートナーが「いるかいないか」は Maybe a 型を利用。 (cf. Haskell の Maybe a 型と Either a b 型 (1) )

import Data.Maybe

data Person = Person { name :: String
                     , partner :: Partner
                     } deriving Eq
-- パートナー
type Partner = Maybe Person

instance Show Person where
    show (Person n Nothing) = n
    show (Person n p)       = n ++ "{" ++ (name $ fromJust p) ++ "}"

-- 誕生
born n = Person n Nothing

-- 結婚
marry p1 p2 =  (p1 { partner = Just p2 }, p2 { partner = Just p1 })

-- 離婚
divorce (p1,p2) = (p1 { partner = Nothing }, p2 { partner = Nothing })

main = do let tarou  = born "Tarou"
              hanako = born "Hanako"
              m = marry tarou hanako
              d = divorce m
          print m  -- (Tarou{Hanako},Hanako{Tarou})
          print d  -- (Tarou,Hanako)

しかし、これでは値の同値性において、Python がオブジェクトシステムを利用した場合の表現とは異なる。また、状態の変化を模倣しているとも言い難い。 (@_@;

 

関連記事

• オブジェクトの相互参照 と 関数の相互再帰 (2) – Haskell の Data.Unique 型で一意な値を生成