人気ブログランキング | 話題のタグを見る

Eliza (3) match

eliza.hs の2番めの関数は match だ。この関数は第1引き数のパターンを第2引き数の文字列から探し出す。パターンの先頭にはワイルドカード "*" を使うことができる。

match :: String -> String -> Maybe String
match pat@('*':rp) str = maybe (matchWildcard str) Just (match rp str)
                         where matchWildcard (s:rs)= (fmap (\x -> s : x) (match pat rs))
match (p:rp) (s:rs)
    | p == s    = match rp rs
    | otherwise = Nothing
match [] [] = Just ""
match _ _ = Nothing

まず、この関数がどういう動作をするのかを知っておくと便利だ。それには test.hs などの適当な名前をつけたファイルに上のソースを貼り付けて、ghci で動作確認をすればいい。実行例を次に示す。

Prelude> :l test.hs
[1 of 1] Compiling Main ( test.hs, interpreted )
Ok, modules loaded: Main.
*Main> match "hello" "world"
Nothing
*Main> match "hello" "hello"
Just ""
*Main> match "*world" "hello, world"
Just "hello, "

これを見ると、パターンマッチが成功しなかったときは Nothing が、成功したときは Just "" が、パターンにワイルドカードを使用したときは、ワイルドカードにマッチした部分が Just "hello, " のように帰ってくる。プログラムを見てみると、定義の3番目と4番目は再帰的定義の the base case なのでとりあえず置いておいていい。再帰的定義で重要なのは the recursive case の場合だからだ。

the recursive case の再帰的定義は1番目と2番目だが1番目の定義は複雑なので、2番目の方を先に見てみる。2行目の定義は次のように単純だ。

match (p:rp) (s:rs)
    | p == s    = match rp rs
    | otherwise = Nothing

ここでは2つの単語を先頭の文字から順に比較していって、文字が途中で一致しなければ Nothing を返す。また、ずっとマッチしていれば reduction を続けて残りの文字列の比較を次々に行なっていく。reduction の最後は the base case に委ねられるが、3行目のように比較する文字列が2つとも空になっていれば Just "" が帰り、4行目のようにどちらかに文字列が残っていれば Nothing が返る。

*Main> match "hello" "hello"
Just ""
*Main> match "hello" "hello, world"
Nothing

それでは、いよいよ、一番複雑そうな1番目の定義を見てみよう。

match pat@('*':rp) str = maybe (matchWildcard str) Just (match rp str)
                         where matchWildcard (s:rs)= (fmap (\x -> s : x) (match pat rs))

定義の1行目は、maybe (matchWildcard str) Just (match rp str) だから、match rp str の戻値が Nothing のときは match の戻値は matchWildcard str で、ワイルドカードにマッチした部分の文字列が戻値になる。 match rp str の戻値が Nothing にならない場合は、Just "" でパターンと文字列が一致した場合だ。この場合、Just "" のコンテナの "" がとりだされ、再び Just にくるまれて Just "" が返される。この場合の実行例を次に示す。

*Main> match "*hello" "hello"
Just ""

match rp str の戻値が Nothing のときは、matchWildcard str が実行されるが、matchWildcard str の定義は手強い。つぎのように fmap 関数が使われているからだ。

matchWildcard (s:rs) = (fmap (\x -> s : x) (match rp str))

fmap 関数の型は次のようになる。

*Main> :type fmap
fmap :: Functor f => (a -> b) -> f a -> f b

上の型の表示の Functor というのは関手だが、数学は置いておいてデータコンストラクタのことだと考えると良い。そうすると fmap は普通の関数 (a -> b) をデータコンストラクタに包まれたデータ f a のコンテナの部分 a に関数適用して、その結果 b を再びデータコンストラクタに包んで返すという動作をするということだ。

こういうのは、実際のデータを使って見たほうがはやい。fmap の第1引き数に (*2) を第2引き数に Just 2 を与えてみる。

*Main> fmap (*2) (Just 2)
Just 4

(*2) を Just 2 のコンテナの値 2 に適用して、その結果の 4 を再びデータコンストラクタ Just にくるんで返してくれる。ちょっとだけ数学を使うと、 fmap には Haskell 圏の関数を、モナド圏の関数に変換する働きがある。

また、fmap の第2引き数が Nothing のときは、単に Nothing が返される。

*Main> fmap (*2) Nothing
Nothing

matchWildcard の定義は再帰的定義になっているが、初期値 (the base case) の定義がない。これではエラーになってしまうのではないかと思うが、巧妙な定義でその心配はないようだ。matchWildcard の定義をロジックだけで理解しようとすると歯が立たないので、実験してみる。

matchWildcard の引き数が "ahello" でパターンが "hello" だったとしよう。この場合 matchWildcard の動作は次のようになる。

*Main> fmap (\x -> 'a' : x) (match "hello" "hello")
Just "a"

最後のパターンマッチが成功して Just "" が返されるので Just "a" が戻値になる。それでは、matchWildcard の引き数が "abhello" でパターンが "hello" のときはどうなるだろうか。この場合、matchWildcard 関数は次のように展開 (reduction) される。

*Main> fmap (\x -> 'a' : x) (fmap (\x -> 'b' : x) (match "hello" "hello"))
Just "ab"

すると、右端の方から次々に評価が進んで、最終的に Just "ab" が返る。さて、最終的なマッチが失敗したときはどうなるだろうか。最終的なマッチが失敗すると次々に Nothing が伝えられるので最終的な戻値は Nothing になる。

*Main> fmap (\x -> 'a' : x) (fmap (\x -> 'b' : x) (match "hello" "hell"))
Nothing

したがって、matchWildcard の初期値 (the base case) の定義がないにもかかわらず、この再帰的な定義はきちんと動作する。

match 関数の定義は簡素だが、実際はモナドの性質を利用したかなり凝った作りの関数だった。こういうのは自分の頭で考えつこうとしても不可能だ。しかし、ghci でひとつずつ実験しながら動作を確認していくと全く理解できなという程でもない。なんとなく、使い方がわかっていれば、自分のプログラムにも応用して使えるようになる。Haskell はとにかく使ってみないと面白さが分からない。
by tnomura9 | 2012-07-18 07:26 | Haskell | Comments(0)
<< Eliza (4) match... Eliza (2) chang... >>