Maybe モナドの秘密

Real World Haskell 読書会での Maybe モナドに関する議論をまとめておきます。

case と Maybe

モナドの導入には、必ずといっていいほど、Maybe が使われます。たとえば、子供をキーとして検索すると、父親を得られる DB があるとします。

type DB = [(String,String)]
db :: DB
db = [ ("Bob","Dave")
     , ("Dave","Steve")
     , ("Steve","Tony")
     ]

コードを簡潔にするために、DB を検索するための補助関数を導入します。

lookup' :: DB -> String -> Maybe String
lookup' = flip lookup

これらと case を使って、ひいおじいさんを探すコードを書くとこうなります。

-- コード1
findGGFather :: String -> Maybe String
findGGFather x =
  case lookup' db x of
    Nothing -> Nothing
    Just y  -> case lookup' db y of
                 Nothing -> Nothing
                 Just z  -> lookup' db z

かなりグシャグシャなコードになりました。
これをすっきりさせましょうということで、モナドが登場します。

Maybe モナド

多くの入門書では、上記のコードを >>= を使って、以下のように書き換えます。

-- コード2
findGGFather' :: String -> Maybe String
findGGFather' x = lookup' db x >>= lookup' db >>= lookup' db

コードが、すっきりしました。めでたし、めでたしという訳です。しかし、コード1とコード2は、等価ではありません。なぜなら、>>= は左結合だからです。

findGGFather' :: String -> Maybe String
findGGFather' x = (lookup' db x >>= lookup' db) >>= lookup' db

これを >>= の定義に従って case に書き直すと以下のようになります。

-- コード3 (括弧は不要)
findGGFather'' :: String -> Maybe String
findGGFather'' x = 
  case (case lookup' db x of
          Nothing -> Nothing
          Just y  -> lookup' db y) of
    Nothing -> Nothing
    Just z  -> lookup' db z

とう訳で、RWH の348 ページに書いてあるように、Maybe を >>= でつなぐと、Nothing になった時点で Nothing が返るのではなく、>>= の連鎖を最後までたどってしまうのです。

最適化

モナド則は、左結合を右結合に変えても、問題が起きないことを保証しています。

(m >>= f) >>= g   ===   m >>= (\x -> f x >>= g)

という訳で、Haskell コンパイラーが、この規則を利用してコード2をコード1へ最適化してもよさそうです。

実際 GHC に最適化オプションを指定しない場合、コード3はコード1へ最適化されます。しかし、コード2 はコード1のようには最適化されません。-O2 オプションを指定すると、コード2と3の両方をコード1へ最適化します(>>= をインライン化するようになるから)。その様子は、ghc -c -ddump-simpl で確認できます。

ここでの最適化は、モナド則を使っている訳ではなく、入れ子の case に対する単純な最適化だそうです。詳しくは、A transformation-based optimizer for Haskellを読んで下さい。