Hatena::Groupbugrammer

蟲!虫!蟲!

Esehara Profile Site (by Heroku) / Github / bookable.jp (My Service)
過去の記事一覧はこちら

なにかあったら「えせはら あっと Gmail」まで送って頂ければ幸いです。
株式会社マリーチでは、Pythonやdjango、また自然言語処理を使ったお仕事を探しています

 | 

2011-12-11Python Advent Calender(全部俺):: 11日目

[]あのPythonモナドが参戦! -- PythonによるMaybeモナドの実装 02:04

 さて、Haskellを扱ったことがある人ならば、モナドを扱う機会というのが多いでしょう。このモナドについては、恐らくCのポインタくらいには、躓きやすい部分なんじゃないかな、と個人的には思っています。何かを理解するためには、その理解したい対象を実際に実装してみるのが一番だろう、と思うので、PythonでMaybeモナドを実装してみる、というのが今回の趣旨です。

Maybe モナドの実装について

 Haskellにおいて、モナド型というのは、下のような定義が与えられています。

class Monad m where
    -- chain
    (>>=)  :: m a -> (a -> m b) -> m b
    -- inject
    return :: a -> m a

 これは、要するに「モナド引数にとり、かつある引数モナドにする関数であるならば、そのモナドを返す」という機能です。また、returnはある引数を取ると、そのままモナドに返すというものですね。また、モナドの一番簡単な形であるMaybe型は、次のようなデータを返すという風に決まっています。

data Maybe a = Nothing
             | Just a

 これは、Maybe型が、「Nothingが、それともJust + 何かしらの値」である、という定義になります。これをPythonで考えるならば、タプルで、値とその型を合わせるという形を取るといいのかなという気がしたので、そのように実装してみます。

 また、Maybeモナドがどのような実装になっているのか、はソースコードを見るのが一番いいので、実際に見てみましょう。次のようになっているはずです。

instance  Monad Maybe  where
    (Just x) >>= k      = k x
    Nothing  >>= _      = Nothing

    (Just _) >>  k      = k
    Nothing  >>  _      = Nothing

    return              = Just
    fail _              = Nothing

 要するに、Just + 値であるならば、次の関数に対してその値を引数に渡します。Nothingだったらどんな関数であってもNothingを返します。returnとfailに関してはそのままですね。

 だいたい、Maybeモナドの実装方針はわかりました。Maybeモナドは下のような実装がある必要があるみたいです。

  • Maybe型の実装 -> これはタプルで代用 = ('Nothing',None) or ('Just',任意の値)
  • Monad型には、BindとReturnが必要 -> これはメソッドで代用( =<< = Monad.bind , return = Monad.just )
    • Bindは、あるモナド型を受けとると、次の関数に渡し、その関数の返り値もモナドである必要がある。
    • Returnは、ある引数を(Just + 引数)という形にパッケージングする。
  • Maybe型は、Justの値を持つデータが与えられると、モナドを返す関数に値を渡す。
  • Maybe型は、Nothingならいかなる関数であれNothingである。

Maybe Classの実装

 草稿として実装してみました。以下のgistからソースが閲覧できます。

 PyMonad (Draft Maybe) ? GitHub

 数学圏論に付いてはわかりませんが、少なくともHaskellにおいては、モナド則と呼ばれる三つの原則を守る型構成子は全てモナドになります。とりあえず、今回は単純なモナド則を満たすようにしてみます。モナド則に関しては、下のサイトを参考にしてみました。

 The monad laws

1.(return x) >>= f == f x

 これを噛み砕くと、要するに「(return x)をbindで関数に渡したものと、関数にxを渡したものは同じものである」というもののような気がするので、必要そうなところから解説しましょう。

...
class Maybe:
    def bind(self,f,arg):
        ## -- Type Check
        if not isMonad(arg):raise NotMonadException(arg)
        if (    (type(f) is not types.FunctionType) 
            and (type(f) is types.InstanceType) 
            and (type(f) is not types.MethodType)):
            raise NotFunctionException(f)

        MonadType,MonadValue = arg
        
        if MonadType == "Nothing":
            return ("Nothing",None)
        elif MonadType == "Just":   
            return = f(MonadValue)
        else:
            raise NotMonadException(arg)

    def just(self,arg):
        return ("Just",arg)
...

 上記で説明した通り、justメソッドは、returnの代用です。ここではJustという型を擬似的に作っています。

 もう一つ、bindなのですが、この辺りが面倒くさいです。bindのポイントは、何らかの(m + Value)を持ち、なおかつ引数モナドに返す関数、という引数指定が行われます。Pythonには、特に引数に対する型指定が無かった気がするので、入力された時点で、fに値する引数関数メソッドでないなら、bindすることが出来ないので、その趣旨を示すErrorを吐き出します。

 次に、もう一つの引数は、擬似的に定義された型の値である必要があります。ですので、まずタプルであり、なおかつ最初の引数がString型であるという条件を満たさないのであるならば、それはそもそも予期している型ではないので、Errorを返しています。

 (a,b)というタプルの形を、可読性のために、変数MonadTypeとMonadValueに与えます。そのときに、MonadTypeが"Just"であるならば、fに渡してやります。fは、関数インスタンスの参照先が入っています。ですので、f()という形で、その参照先を呼び出して実行することが可能になります。(参照:参照渡し地獄変 -- Pythonにおける参照 - 蟲!虫!蟲! - #!/usr/bin/bugrammer )

 上記の実装が終わると、上のモナド則を確かめるためのテストが書けるようになっているはずです。

maybe.bind(f,maybe.just(x)) == f(x)

 これは、LispであるところのS式にするとわかりやすいですね。

(== (=<< f (maybe.just x)) (f x))

 上記の実装だと、bindは">>="の順序ではなく、"=<<"という順序になっているので、ちょっとわかりにくくなっていますね。すいません……

2.m >>= return == m

 これは明確です。要するにモナドをreturnにわたしたら、元のモナドに戻るというものです。これは上記の原則が満たされているなら、何もせずともスムーズにテストが書けるはずです。

maybe.bind(maybe.just,m) == m

 S式だと、こうなりますね。

(== (=<< maybe.just m) (m))
3.(m >>= f) >>= g == m >>= (\x -> f x >>= g)

 さて、三番目がとにかくややこしいです。噛み砕くと、「mをfに渡した結果をgに渡す場合、『引数xをfに渡し、その実行結果をgにbindする関数』に、mをbindする結果と一緒である」ということになるのかな、と思うので、いろいろ言うよりも、実際にテストコードを見せた方が手っ取り早いかもしれません(かなり読みにくくなっていますが)。

maybe.bind(g,maybe.bind(f,m)) == maybe.bind((lambda x:maybe.bind(g,f(x))),m)

 ここは自分の実装でも、手間をとってしまいました。左の式は、順番にbindしていけばいいだけの話なので、わかりやすいのですが、右の式は無名関数が入っているので、少々複雑になっています。まず、Haskell式の無名関数Pythonで書くとどうなるか、というのを考えてみます。

(\x -> f x >>= g) :: Haskell == (lambda x:maybe.bind(g,f(x))) :: Python

 まず第一段階として、Haskellの(f x)という値はPythonにおけるf(x)です。次にその結果をgにbindさせているわけですね。順番に書くと次のようになります。

def lambda_rewrite(x,f,g):
    result = f(x)
    return maybe.bind(g,result)

 次はその無名関数に対して、mを渡してあげればいいわけです。あえて、上の関数を使うと、下のように書き直されるはずです。

maybe.bind(lambda_rewrite,m) 

 これをひとまとめにした結果、最初のテストコードが生まれるわけです。

正直、モナドはまだわからない

 さて、愚直にHaskellモナド定義をPythonトランスレートしているわけですが、正直モナドはよくわかりません。上記の実装で果たしていいのかどうか、ちょっと不安なところがあります。現実問題として、このあたりはHaskellで、自分なりのモナドを、なれるまで実装するという手順を踏まないと、自分なりに使いこなせるという実感がわかないだろうな、と思うので、そこは自分の今後の課題だな、と思っています。

 あと、このコードを書いていて思ったのは、「これってポリモーフィズムという観点すると、柔軟性が欠けている」と思う部分があるので、その辺に関してあとで考え直してみます。

 |