Haskellのモナドまでの12ステップ

前置き

本記事では、パーサーを題材にして、モナドというソリューションへ至る道筋をたどってみます。理詰めでモナドを導き出そうという試みです。結果的には、最初から答えを知ってて、それに向けてつじつまが合うような理由をくっつけただけみたいになってしまいましたが…。

参考にしたのは「プログラミングHaskell(2009年、オーム社)」と「関数プログラミング入門(2012年、オーム社)」です。

★本記事のコードにはコンパイルに通らないものが含まれます。イメージを伝えるためのものとご理解下さい。

ステップ0. 予備知識 ~ ネストしたラムダ

本記事には、ラムダ、クロージャ、カリー化といったトピックが少し関与します。サラッとコードで示します。

3引数の関数
Prelude> let add x y z = x + y + z
Prelude> add 1 2 3
6
Prelude> :t add
add :: Num a => a -> a -> a -> a
1引数の関数
Prelude> let adduc (x, y, z) = x + y + z
Prelude> adduc (1, 2, 3)
6
Prelude> :t adduc
adduc :: Num a => (a, a, a) -> a
カリー化
Prelude> let addc = \x -> (\y -> (\z -> x + y + z))
Prelude> addc 1 2 3
6
Prelude> :t addc
addc :: Integer -> Integer -> Integer -> Integer

注目して欲しいのは、カリー化されたaddcの定義です。

  • 1引数を取るラムダがネストしている
  • 最内のラムダ(zを引数にとるやつ)の中では、外側のラムダの引数(xとy)が見える

本記事では、この「ラムダは、それが定義された周りの環境を引き継ぐ」という性質を利用するので、覚えておいて下さい。

ステップ1. パーサー

パーサーは、ある文法に従って書かれたテキストを構文解析するプログラムです。

数式パーサー

パーサーを関数とみなすと、それは文字列を引数に取り、パース結果(たとえば木)を返します。

String -> Tree

テキストをパースした結果、そのテキストの一部が消費されずに残る場合もあるので、パース結果と共に残りの文字列も返すように改良しましょう。2値を返したいのでタプルを使います。

String -> (Tree, String)

パースに失敗したときは何を返せば良いでしょうか? HaskellならMaybeを使うのが筋ですが、ここでは、なるべく基本的な型だけを使って実現したいです(実はMaybe自体がモナドなので、ここでMaybeを使うのは反則という気もしますし)。いくつかの方法が考えられますが、失敗の場合は空リストを返し、成功したときは (Tree, String) をひとつだけ要素に持つリストを返すことにしましょう。

String -> [(Tree, String)]

また、パース結果がTreeじゃないパーサーもあるので、パース結果の型は変えられるようにしておきたいです。

String -> [(α, String)]

結局、パーサーの型は、以下のようになります。

data Parser α = String -> [(α, String)]

αの部分には、任意の型を入れることができます。数式パーサーのようにパース結果が木構造になるならParser Tree、パース結果が整数ならParser Int、パース結果が文字ならParser Charといった具合になります。

複数のパーサーを連続してかける様子を図にしてみましょう。

パーサー連結

前段のパーサーの残り文字列が後段のパーサーへの入力文字列になります。このように、文字列をパーサー間で引き回すことを、パース対象文字列の「バケツリレー」と呼ぶことにします。本記事内でバケツリレーと言えば、このことを指すと思って下さい。

ステップ2. 原始的パーサー

プリミティブなパーサーの例を挙げましょう。まずは、先頭の数値をパース結果とするパーサーp1です。

数値パーサーp1
p1 "123"      -- [(1, "23")]
p1 "abc"      -- []

次は、先頭の小文字だけを受け入れるパーサーp2です。

小文字パーサーp2
p2 "abc"      -- [('a', "bc")]
p2 "ABC"      -- []

何の役に立つのか分からないような単純なパーサーですが、こういったプリミティブなパーサーと、そのパース結果を加工する関数とを組み合わせれば、より複雑なパーサーを作ることができます。

ステップ3. パーサーと加工関数の合成

例えば、数値パーサーp1とnegate関数を組み合わせてみましょう。p1のパース結果をnegateで加工するわけです(ちなみにnegateは、数値の符号を逆転させる関数です)。パーサーと加工関数を合成して新しいパーサーを作る関数combo'があれば、次のように書けるでしょう。

(combo' p1 negate) "3"      -- [(-3, "")]
(combo' p1 negate) "8"      -- [(-8, "")]

括弧で囲んだ部分が新しいパーサーです。このような関数combo'は簡単に定義できます。

combo' p f = \inp -> case p inp of
                      [] -> []
                      [(v, out)] -> [(f v, out)]

野暮ですが、言葉で説明してみましょう。

  • (combo' p f) はパーサーなので、文字列inpを引数に取る関数
  • このパーサーは、まずinpにパーサーpを適用し
  • その結果が失敗なら[]を返し
  • 成功ならpのパース結果vに加工関数fを適用したものをパース結果とする
  • pの残り文字列outは、そのまま新しいパーサーの残り文字列となる

ステップ4. 2つのパーサーと加工関数の合成

次は2つのパーサーを使ってみましょう。p1とp2と加工関数replicateを組み合わせると、ある文字を繰り返した文字列を返すパーサーを作ることができます。

(combo'' p1 p2 replicate) "3c"     -- [("ccc", "")]
(combo'' p1 p2 replicate) "4f"     -- [("ffff", "")]

最初の例の場合、まずp1を"3c"に適用して [(3, "c")] を得ます。続けてp2を"c"に適用し、[('c', "")] を得ます。それぞれのパース結果にreplicateを適用すると、replicate 3 'c' = "ccc" となり、最終的にパーサーは [("ccc", "")] を返します。

combo''の定義は以下のようになります。

combo'' p1 p2 g = \inp -> case p1 inp of
                           [] -> []
                           [(v1, out1)] -> case p2 out1 of
                                             [] -> []
                                             [(v2, out2)] -> [(g v1 v2, out2)]

p1かp2のどちらかがパースに失敗したら、新しいパーサーも失敗します。

上記の通り、複数のパーサーや加工関数を組み合わせて新しいパーサーを合成できることが分かりました。しかし、組み合わせるパーサーの数や加工関数が変わるたびに、combo'やcombo''の変種を定義するのはナンセンスです。何とかして合成関数を一般化したいですね。

ステップ5. 汎用合成関数への作戦

整理してみると、combo'とcombo''のアプローチには、以下の問題があります。

  • 組み合わせるパーサーの数に応じて、合成関数の引数の数が変わってしまう
  • 加工関数の型もケースバイケース

これらを解決するため、一般化した合成関数comboでは、以下のような作戦をとります。

  • comboが引数に取るパーサーは1つとする
  • 複数パーサーを使いたいときは、comboを繰り返し適用する
  • 加工関数を直接comboの引数に指定する代わりに、加工関数を包んだラムダをcomboの引数に指定する
  • そのラムダは、パース結果を1つだけ引数に取り、加工関数を呼ぶ
  • 複数のパース結果を加工関数へ届けるには、ネストしたラムダを使う(「予備知識」の項参照)

この作戦に基づいてcomboの完成像を描いてみましょう。combo'をcomboで置き換えると、以下のような感じになります。

combo呼び出し(☆1)
(combo p1 (\v1 -> ...(negate v1)...)) "3"

加工関数negateをラムダで包みました。このラムダをw1と名付けておきます(wはwrapperの意味)。w1の引数v1はp1のパース結果です。w1の中では、何をやっても良いのですが、少なくともnegateを呼ぶ必要はありますね。w1が何を返すかは、まだナゾです。ラムダをブルー、comboが作るパーサーをピンク、そしてナゾの部分をグレーで色分けすると、以下のようになります。

combo1

ステップ6. comboの繰り返し

次に、combo''はどうでしょうか。作戦では、comboを繰り返し適用することになっています。またそのとき、ラムダをネストさせたいので、以下のようになるでしょう。

combo呼び出し(☆2)
(combo p1 (\v1 -> ...(combo p2 (\v2 -> ...(replicate v1 v2)...))...)) "3c"

コードでは構造が分かりにくいので、図示してみます。

combo2

作戦通り、加工関数replicateにp1とp2のパース結果(v1とv2)を伝えることができています。このようにラムダをネストさせていけば、いくらパーサーが増えても大丈夫です。そして、ラムダの本体(ナゾのグレー部分)についても、新しいヒントが見出せます。それは、ラムダ本体の中にはパーサーが存在するということです。図を見れば明らかですが、外側のラムダw1(ブルー)の中に、内側のcomboが作るパーサー(ピンク)がありますね。今のところ、内側のラムダw2の中にパーサーは見当たりませんが、そこはひとまず棚上げしておきます。

次はcomboの定義を想像してみましょう。

combo定義(★)
combo p w = \inp -> case p inp of
                      [] -> []
                      [(v, out)] -> ...

またしてもナゾが残りました。等式の左辺(combo p w)はパーサーですから、...の部分にどんな式を置くにしろ、その結果は [(α, String)] の形になる必要があります。その際、手持ちの情報として、wとvとoutが使えます。wはパース結果vを引数に取る関数なので、w v という式が出てきそうな気はしますね。

もうひとつ忘れてはいけないのがバケツリレーです。上記のoutは、次のパーサーへの入力文字列となるはずです。でも上記の式に登場するパーサーは、pだけです。次のパーサーって、どこにあるんでしょう?

ステップ7. ナゾに答える

ここで、これまでに挙がったナゾを整理してみましょう。

第1のナゾは「ラムダwの戻り値は何か?」です。前述の☆の部分ですね。これについては、以下のようなヒントがあります。

  • wは、パース結果を引数に取る
  • wがネストするとき、wは、パーサーを包み込む

第2のナゾは、★のところで示した「comboが合成するパーサーの中で何をすれば良いか?」です。これについても、以下のことが分かっています。

  • 使える情報は、wとvとout
  • 結果が [(α, String)] の形になるような何かである
  • 次のパーサーへoutをバケツリレーする必要がある

さて、ここで論理展開が少し飛躍します。集まったヒントを満たしつつ2つのナゾに答える方法は一通りだけじゃないでしょう。しかしHaskellは、ある解を採用しました。そこに必然性は無いかもしれませんが、とにかくそれがHaskellの答えです。Haskellの答えとは、以下の2つです。

  • wは、パーサーを返す
  • comboが合成するパーサーの中では、(w v) が返すパーサーにoutをバケツリレーする

ただ、この解には、ひとつ問題が残ります。それは、negateやreplicateのような加工関数の結果は、パース結果形式 [(α, String)] ではない、という点です(この点は、棚上げしておいたのでした)。これに対してもHaskellは、解を用意しています。

  • 文字列を消費せず、加工関数の結果をパース結果とするようなパーサーを動的に作る

パーサーを動的に作る…。そんなことをしてくれる関数を仮にmkcpと呼びましょう(make constant parserの略)。mkcpは簡単に定義できます。

mkcp v = \inp -> [(v, inp)]

mkcpが作るパーサーは、入力文字列を消費せず、常に定数値vをパース結果とするようなパーサーです。使用例は、以下の通りです。

(mkcp -3) "123"         -- [(-3, "123")]
(mkcp "ccc") "123"      -- [("ccc", "123")]

よって、加工関数の結果をmkcpの引数に指定すれば、欲しいパーサーを作ることができます。

ステップ8. 汎用合成関数の完成

以上をまとめて、これまで...だった箇所を埋めると、以下のようになります。

-- combo呼び出し。
(combo p1 (\v1 -> mkcp (negate v1))) "3"                             -- [(-3, "")]
(combo p1 (\v1 -> combo p2 (\v2 -> mkcp (replicate v1 v2)))) "3c"    -- [("ccc", "")]

-- combo定義。
combo p w = \inp -> case p inp of
                      [] -> []
                      [(v, out)] -> (w v) out

comboの役割を言葉にすると、以下のようになります。

  • comboは2つのパーサーを合成して新しいパーサーを作る
  • 新しいパーサーは、2つのパーサーの間でバケツリレーを行う
  • 第1のパーサーが失敗したら、新しいパーサーも失敗する

当初のcomboの目的は、パーサーと加工関数を組み合わせることでした。しかし、mkcpを導入すれば加工関数をパーサーに昇華(格上げ)できるので、結局comboは、2つのパーサーを合成する関数になったのです。

ステップ9. comboの意義

もう一度、comboの呼び出し側のコードを見てみましょう。

(combo p1 (\v1 -> mkcp (negate v1))) "3"                             -- [(-3, "")]
(combo p1 (\v1 -> combo p2 (\v2 -> mkcp (replicate v1 v2)))) "3c"    -- [("ccc", "")]

ここにはoutが出てこないという点に注意して下さい。バケツリレーはcomboの内部に隠されており、呼び出し側が意識する必要は無いのです。

また、もし途中で1つでもパースに失敗した場合は、全体としても失敗する(つまり[]を返す)べきですが、これについてもcomboがケアしてくれます。

(combo p1 (\v1 -> combo p2 (\v2 -> mkcp (replicate v1 v2)))) "8A"    -- []

この例の場合、p2で失敗するはずですが、comboの呼び出し側はそれをチェックしていません。それなのに、式全体がヌルポで落ちるような心配が無いのです。つまりcomboは、パース対象文字列だけでなく、「パースに失敗してないか」という情報もバケツリレーしているのです。

このようにcomboを使うと、バケツリレーしながら複数のパーサーを連結するコードを非常にスッキリ書くことができます。

ステップ10. さらにスッキリ

前節の最後で「非常にスッキリ」と言いましたが、これは相対的な主張です。つまり、呼び出し側でoutのバケツリレーや失敗時のチェックをする場合と比べればスッキリしているという意図でした。そういった背景を踏まえなければ、下記のコードがスッキリしていると感じる人は少ないでしょう。

(combo p1 (\v1 -> combo p2 (\v2 -> mkcp (replicate v1 v2)))) "3c"    -- [("ccc", "")]

組み合わせるパーサーが増えれば、さらに複雑になります。

combo p1 \v1 ->
  combo p2 \v2 ->
    combo mkcp (replicate v1 v2) \v3 ->
      combo p4 \v4 ->
        combo p5 \v5 ->
          combo mkcp (someFunc v3 v4 v5) \v6 ->
            combo p7 \v7 -> p8

このようにラムダをネストさせていくコードは読みにくいので、Haskellは、上記のようなコード用に特別な構文(do構文)を提供しています。do構文を使うと、上記のコードは、以下のように書くことができます。

do
  v1 <- p1
  v2 <- p2
  v3 <- mkcp (replicate v1 v2)
  v4 <- p4
  v5 <- p5
  v6 <- mkcp (someFunc v3 v4 v5)
  v7 <- p7
  p8

これなら誰の目にもスッキリですね。<- によりパース結果を取り出すのはオプションです。<- の右側には、パーサーが来ます(パーサーを呼び出す式ではなく、パーサー自体が来る)。また、最後のパーサー(この例ではp8)に対しては、<- を付けることができません。元のコードにも、v8なんて無かったですしね。

ただし、このdo構文が使えるのは、Parser αが、ある条件を満たすときだけです。その条件とは……、そう、モナドです。

ステップ11. パーサーの中にモナドを見る

Parser αという表現が久しぶりに出てきましたが、これはパーサー自体の型でした。

data Parser α = String -> [(α, String)]

これを出発点として、パーサーを連結する関数comboを導出したのでした。comboの型は以下の通りです。

combo::Parser α -> (α -> Parser β) -> Parser β

(α -> Parser β) の部分が、これまでwと呼んでいたラムダです。

そして、パーサーと(パーサーでない)加工関数を組み合わせるときに重宝するのがmkcpでした。mkcpの型を見れば、mkcpが普通の型のデータをパーサー型へ格上げする関数だと分かるでしょう。

mkcp::α -> Parser α

実は、この3つこそがモナドの条件なのです。一般化するため、"Parser"を"M"で置き換えると、以下のようになります。

  • M α という型
  • M α -> (α -> M β) -> M β という型を持つ関数による連結
  • α -> M α という型を持つ関数による格上げ

この3つを備えたMが、モナドです。別の言葉で説明してみます(どう説明しても分かりやすくはならないのですが…)。

  • M αは、ある「計算(または情報)」を抽象化したもの
  • それに付随する「コンテキスト」をバケツリレーしつつ、M αとM βを連結できる
  • 裸のαを、M αへ格上げできる

パーサーに当てはめると、「計算(または情報)」とは、入力文字列からパース結果を算出する関数に相当します。また「コンテキスト」は、パース対象文字列と「パースに失敗してないか」という情報を指します。そしてmkcpにより、例えば裸のデータ3を、入力文字列から3というパース結果を算出する関数に格上げできます。

ステップ12. で、結局モナドとは?

Haskellのモナドは、型クラスの1つです。ある型がモナド型クラスのインスタンスであるためには、それが型変数(αやβ)を伴う抽象型であり、かつcomboとmkcpに相当する関数をサポートする必要があります。ただしモナドでは、comboの代わりに >>= を、mkcpの代わりにreturnを使います。

(>>=) :: m α -> (α -> m β) -> m β
return :: α -> m α

モナドの最大の利点は、コンテキストのバケツリレーをdo構文で書けることでしょう。いくつか、パーサー以外のモナドの例を挙げます。

Maybe

  • Maybe αは、「単なるα型のデータ」を抽象化する
  • Maybe αには、「失敗かもしれない」というコンテキストが付随する
  • >>= は、このコンテキストをバケツリレーしつつ、Maybe αとMaybe βを連結する
foo = do
  x <- Just 3
  y <- if x > 0 then Just 'c' else Nothing
  return (replicate x y)     -- Just "ccc"

bar = do
  x <- Just (-3)
  y <- if x > 0 then Just 'c' else Nothing
  return (replicate x y)     -- Nothing

リスト

  • [α]は、「1つに定まらない(複数の選択肢がある)値」を抽象化する
  • [α]には、「非決定性」というコンテキストが付随する
  • >>=は、このコンテキストをバケツリレーしつつ、[α]と[β]を連結する
  • つまり>>=は、選択肢の組み合わせを作る

例えば、[1, 2, 3]というリストを、「1かもしれないし、2かもしれないし、3かもしれない、何か」を表現したものと見なすわけです。

foo = do
  x <- [1, 2, 3]
  y <- [x, -x]
  return y                   -- [1,-1,2,-2,3,-3]

一見、リストから1か2か3を取り出してxに入れているような印象を受けますが、そうではありません。この式は、xには3つの可能性があり、yには、それぞれのxに対して、xと-xの2つの可能性があると言っています。よってyは、「1か-1か2か-2か3か-3のどれか」となります。

もう1つ例を挙げましょう。要素の型が違っても、各リストに相関が無くても、「非決定性」という共通のコンテキストはバケツリレーされます。

bar = do
  x <- [1, 2, 3]
  y <- ['a', 'b']
  return "ok"                -- ["ok","ok","ok","ok","ok","ok"]

最後のreturn "ok"だけを見ると["ok"]が返りそうですが、実際は、それまでのバケツリレーの結果、6つの選択肢が返りました。実のところ上記のコードは、リスト内包に他なりません。

bar = ["ok" | x <- [1, 2, 3], y <- ['a', 'b']]   -- ["ok","ok","ok","ok","ok","ok"]

IOアクション

  • IO αは、「副作用と共にα型の結果を返す計算」を抽象化する
  • IO αには、「World(外界)」というコンテキストが付随する
  • >>=は、このコンテキストをバケツリレーしつつ、副作用を連結する
main = do
    putStrLn "Hello"
    name <- getLine
    putStrLn name            -- IO ()

putStrLnとgetLineの型は以下の通りです。

putStrLn :: String -> IO ()
getLine :: IO String

putStrLn呼び出しの結果を <- で受け取ることは稀です。なぜなら、()型の値は()しかないからです。()型は、CやJavaでのvoidのようなものです。つまりIO ()を返すputStrLnは、その副作用のみが意味を持つ関数です。

「World(外界)」の正体については、あまり気にしない方が良いでしょう。関数の純粋性にこだわるための詭弁に近いです。例えばputStrLn呼び出しの結果は、「stdoutに文字列を出力する」という副作用を伴うIOアクションです。この IO () を、World -> ((), World) のような型の関数と考えます。つまり、今現在のWorldを引数に取り、文字列を出力したあとの新しいWorldを返す関数と見なします。そうするとこの関数には、結果を返すこと以外の作用(つまり副作用)はありません。同様に IO String も、World -> (String, World) と考えれば、参照透明性があるように見えなくもありません(同じWorld値を引数に与えれば、いつも同じ結果を返す)。

とは言え、あくまでもWorldは概念的な型なので、World型の値を具現化することはできません。それもあって、IOモナドが使えるのはmainの中に限られます。

おまけ

本記事を書くキッカケは、「プログラミングHaskell(2009年、オーム社)」の8章でした。小さなパーサーやパーサーを作る関数を組み合わせて複雑なパーサーを作る流れが秀逸です。主なものを挙げてみます。

パーサーを作る関数
+++ p1 p2
p1が失敗したらp2を適用するようなパーサーを作る。
sat pred
先頭文字が述語predを満たすならそれをパース結果とするようなパーサーを作る。
char x
先頭文字がxならそれをパース結果とするようなパーサーを作る。
string xs
入力文字列がxsならそれをパース結果とするようなパーサーを作る。
many p
失敗するまでpを適用し、各パース結果のリストをパース結果とするようなパーサーを作る。1度も成功しなければ空リストをパース結果とする。
many1 p
失敗するまでpを適用し、各パース結果のリストをパース結果とするようなパーサーを作る。1度も成功しなければパース失敗とする。
プリミティブなパーサー
failure
常に失敗する。
item
入力文字列の先頭文字をパース結果とする。
digit
1文字目が数字なら、それをパース結果とする。
lower
1文字目が小文字なら、それをパース結果とする。
upper
1文字目が大文字なら、それをパース結果とする。
letter
1文字目がアルファベットなら、それをパース結果とする。
alphanum
1文字目がアルファベットか数字なら、それをパース結果とする。
やや高度なパーサー
ident
識別子をパース結果とする。lowerとmany alphanumの組み合わせ。
nat
自然数をパース結果とする。many1 digitと加工関数readの組み合わせ。
space
空白を読み飛ばす。manyとsat isSpaceの組み合わせ。パース結果は無意味なので()とする。
さらに
token p
spaceしてpしてspaceするパーサーを作る。
identifier
識別子を見つける。token ident。
natural
数値を見つける。token nat。
symbol xs
文字列xsを見つける。token (string xs)。

以上を組み合わせて、readっぽいパーサーを作ることができます。

myRead =
  do symbol "["
     n <- natural
     ns <- many (do symbol ","
                    natural)
     symbol "]"
     return (n:ns)

使用例は、こんな感じです。

myRead " [ 1, 2, 3 ]   "       -- [([1,2,3],"")]
Last modified:2014/01/02 14:50:55
Keyword(s):
References:[FP: 関数型プログラミング]
This page is frozen.