2008年11月6日木曜日

Haskell の Maybe 型に馴染む (2)

Haskell の Maybe 型に馴染む」 の続き。

モナドのすべて」を読みはじめてはいるのだけど、わからないところだらけ…。 (@_@;) 今日は、Haskell におけるモナドのサポート を読んでいたら、sequence 関数の定義でつまづいた。

sequence :: Monad m => [m a] -> m [a] 
sequence = foldr mcons (return [])
             where mcons p q = p >>= \x -> q >>= \y -> return (x:y)

foldr の第1引数に与えられた mcons 関数のこの定義。どうやって読めばいいののだろうか… (+_+)

 

カリー化

まずは無名関数の基本から。引数に数値を与えると + 1 した値を返す無名関数を定義。それを適当な値に適用するなら、

main = do
  print $ (\x -> x + 1) 1

次に、二つの与えられた引数を足し合わせる関数を作成。適当な値に適用するなら、

  print $ (\x y -> x + y) 1 2

 

ところで、カリー化と関数の部分適用 によると、

Haskellでは2つの引数を持つ関数は、1つの引数をとり「ひとつの引数をとる関数」を返す関数と同義である。このように、関数を返すことで全ての関数をひとつの引数の関数として表現することをカリー化という。

この辺り、「あ~、そういうものか」とよく考えずなあなあにしていた。 ^^; (cf. カリー化 – Wikipedia)

先ほどの無名関数を上記に書かれているような形に明示的にするなら、次のような形だろうか。

  print $ ((\x -> (\y -> x + y)) 1) 2

これで『1つの引数をとり「ひとつの引数をとる関数」』になった。(cf. 3.1 ラムダ抽象) 以下のように、内側の括弧をとっても大丈夫なようだ。

  print $ (\x -> \y -> x + y) 1 2

これは、無名関数が、関数適用と同じく 結合性 の優先順位が 10 と高いためのようだ。

 

同様に、二つの引数を足し合わせる関数もいろいろな書き方で定義できる。

addTwo x y = x + y
addTwo' x  = \y -> x + y
 
addTwo''  = \x y -> x + y
addTwo''' = \x -> \y -> x + y
addTwo'''' = \x -> (\y -> x + y)

main = do
  print $ addTwo 1 2
  print $ (addTwo 1) 2
  print $ (addTwo' 1) 2
  print $ (addTwo'' 1) 2
  print $ (addTwo''' 1) 2
  print $ (addTwo'''' 1) 2

 

わかっちゃいないけどモナド

sequence 関数に戻る。わからなかった定義の一部を再掲。

where mcons p q = p >>= \x -> q >>= \y -> return (x:y)

見やすくするために括弧を付けるなら、

where mcons p q = p >>= (\x -> q >>= (\y -> return (x:y)))

 

ところで、Monad クラスの定義は、

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

(>>=) 演算子の第2引数は (a –> m b) 型の関数。

sequence 関数の定義における p, q は、型宣言より、それぞれモナドのインスタンスである型の値に束縛される。sequence の最後を見ると return (x:y) となっており、リストがモナドのインスタンスで包まれたものが返される。つまり、上記の無名関数のところだけ見れば (>>=) の右側は (a –> m b) 型になっており、そこへ p または q のモナドのインスタンスで包まれた中身が (>>=) で無名関数へ投入される形。 (この説明が適切なのかわからないのだけれど…)

ということで、なんとなく読めるようにはなった。

 

とにかく使ってみる

さて、ここで「モナド」も「モナド則」もわかっていないけれど、Maybe を使って sequence の定義を真似た関数を作成してみることに。わからないものはとりあえず動作しているもの見て、見慣れてからそれが何なのか理解する方向で。 ^^;

作成するのは、「Maybe で包んだ数値を二つ引数として与えると、中身を足して、その結果を Maybe で包んで返す」関数。関数名を addTwoM とした。まずは型宣言。

addTwoM :: Num a => Maybe a -> Maybe a -> Maybe a

 

いきなり、全部真似るとわからなくなるので、まず、第1引数に渡された Maybe の中身を (>>=) で渡し、それを単純に Maybe で包んで返すだけの動作を確認。

addTwoM p _ = p >>= \x –> Just x

以下を実行。

  print $ addTwoM (Just 1) (Just 2)      -- Just 1

お~、返ってきた。^^

次に、二つの Maybe の中身を受け取り、足し合わせるように変更。

addTwoM p q = p >>= \x -> q >>= \y –> Just $ x + y

括弧をつけて見やすくすると、

addTwoM p q = p >>= (\x -> q >>= (\y –> Just $ x + y))

以下を実行。

  print $ addTwoM (Just 1) (Just 2)   -- Just 3
  print $ addTwoM (Just 1) Nothing    -- Nothing
  print $ addTwoM Nothing (Just 2)    -- Nothing

 

型宣言を Monad へ

せっかくなので、関数の型を Maybe から Monad に変更してみる。

addTwoM :: (Monad m, Num a) => m a -> m a -> m a

変更しても動くかな?と思い試してみると、

    Couldn't match expected type `m' against inferred type `Maybe'
      `m' is a rigid type variable bound by
          the type signature for `addTwoM' at lambdatest.hs:9:18
      Expected type: m a
      Inferred type: Maybe a
    In the expression: Just $ x + y
    In the second argument of `(>>=)', namely `\ y -> Just $ x + y'

定義で Just を使っているので、この関数は Maybe a 型に固定されてしまっているということだろうか。これも sequence 関数を参考にして、return に変更する。

addTwoM p q = p >>= \x -> q >>= \y -> return $ x + y

なぜ return なのだろう?これは型宣言を見るとわかるが、先ほどまで関数は Maybe について書いていた。しかし、今この関数の型宣言は、もう1つ抽象的な Monad のレベルで定義している。だから、Maybe のように特定の型について言及していてはダメということなのだろう。(多分) だから、Monad に定義されているメソッドを使って関数を定義する。

 

Maybe の定義

Maybe に戻り Maybe モナド を見ると、(>>=) や return の具体的な定義が書かれている。そもそも以下のように Monad のインスタンスであると宣言しているので、Maybe a 型の値を上記の addTwoM に適用することができる。

instance Monad Maybe where
    return         = Just
    fail           = Nothing
    Nothing  >>= f = Nothing
    (Just x) >>= f = f x

それぞれの関数の型はどうなっているのだろうかと思い、先ほどの Monad クラスの定義の中の `m’ を Maybe で置き換えて書いてみると、

class Monad Maybe where
    (>>=)  :: Maybe a -> (a -> Maybe b) -> Maybe b
    return :: a -> Maybe a

上記の Maybe の定義はこの型宣言に合わせ、また Monad の 三つの基本則

    1. (return x) >>= f == f x
    2. m >>= return == m
    3. (m >>= f) >>= g == m >>= (\x -> f x >>= g)

を満たすように定義されている。しかし、なぜこの規則を満たす必要があるのかまだ理解できない。(+_+)

 

リストもモナド

Monad クラスのインスタンスを見ると、リストも仲間だということがわかる。ということは addTwoM 関数を適用できるということ。

  print $ addTwoM [1] [2]         -- [3]
  print $ addTwoM [1,2] [2]       -- [3,4]
  print $ addTwoM [1] [2,3]       -- [3,4]
  print $ addTwoM [1,2] [2,3]     -- [3,4,4,5]
  print $ addTwoM [] [1]          -- []
  print $ addTwoM [1] []          -- []

ふ~む、[1] というのは `1’ が [ ] で包まれているということだったのか。 (@_@) それにしても、この結果はどうしてなんだろう?

List モナド を見たら、以下のように定義されてる。

instance Monad [] where
    m >>= f  = concatMap f m
    return x = [x]
    fail s   = []

具体的に試してみる。

  print $ [1..5] >>= \x -> return x             -- [1,2,3,4,5]
  print $ [1..5] >>= \x -> return (x*2)         -- [2,4,6,8,10]
  print $ concatMap (\x -> return x) [1..5]     -- [1,2,3,4,5]
  print $ [1,100] >>= (\x -> [11,12] >>= (\y -> return $ x + y))  -- [12,13,111,112]

は~、なるほど (>>=) と return はリストに対してそういう働きをするわけか。

Monad 自体の意味はよくわからないけれど、少しだけ Monad に近づけた気がした。