昔、モナドがよくわからなかったので、さまよっていたら、
… ネットで見たMonadの説明で一番私がわかりやすいと思ったのは、Wikibooksの説明。Hello World!がブラックボックスな人は、是非一読を。
(404 Blog Not Found:Haskellで一番難しいのは より)
最初にこの Wikibooksの説明 を読んだのは去年の 11 月頃。そのときの文書のバージョンは 05:13, 27 October 2008 で、今は内容が随分増えている。前の文書は、現在の Haskell/Understanding monads/State に相当するようだ。
ところで、上記の解説を最初読んだとき全く意味がわからなかった。 (@_@;) 「3 Stateful Computations」 では、「ランダムな数字を生成する関数」を例に挙げてモナドの説明がされていたけれど、何が言いたいのかさっぱり意図が汲めず。 (+_+) そもそも「状態」というのは何の状態で、それがどうなることなのか？ランダムな数字を生成することと「状態」がどう関係するのチンプンカンプン。
状態の変更
Stateful Computation ということで、文字通り「状態のある計算」。
「状態」とは、例えば、Python で変数の状態を変更するとしたら、
a = 0
a = 1
print a
変数 a の内容を変えるのは全く問題がない。
しかし、Haskell において、同じノリで、
a = 0
a = 1
main = print a
と書くと以下のように怒られる。 (+_+)
Multiple declarations of `Main.a'
なぜ関数プログラミングは重要か によると、
関数プログラムは代入文を含まない。それゆえ、変数は一度 値を与えられたら変更されない。もっと一般的ないいかたをすれば、関数プロ グラムには全く副作用がない。関数の呼出しは、結果を計算する以外の作用は もたない。このことは、バグの大きな源のひとつを断つ。
A Gentle Introduction to Haskell: Functions には、
Haskell は伝統的な言語のように代入 ( assignment ) ではなく、定義 ( definition ) を用いて計算をすすめます。
つまり、`=’ は代入ではなく定義。先ほどの Haskell のコードは、a を 2 回定義したことになるのでエラーが表示された。a という名前の入れ物があり、その中身を入れ替えることはできない。 a はそれが指し示するものと分かち難く結びついている。 Python の場合、変数 a を外から眺めれば、a の中身が文の実行によって変わる。つまり、a の「状態」が変化していると見なすことができる。
「状態の変化」と言った場合、上記のように変数の値が再代入によって変わっていくことが一番シンプルな例。しかし、最初に Stateful Computation の「状態」と聞いたとき、反射的に「オブジェクトの内部状態」を連想してしまった。そのため、上記 Wikibooks の解説において「どれがオブジェクトに相当して、何が内部状態に当たるのだろう ？？？」と混乱。 (+_+) アナロジーによる理解に頼り過ぎると、その枠で固定した視点ができるので理解の阻害要因になることも。かと言って、自分の知識の枠外で想像することはできないので、「オブジェクトの内部状態」を手がかりに、自分なりに Stateful Computation について考えることに。
※ 今回は Control.Monad.State は使わずに自前で実装する。
スタックにおける状態の変化
Haskell で内部状態を持つオブジェクトの動作を模倣するには、値に関数を適用したら、更新した状態の値を新たに作り返すようにする。 (cf. 素朴にエラトステネスのふるい (3) )
Abstract data type – HaskellWiki の 2.2 Stack にはスタックの実装例がある。これを参考に必要最小限の関数を持つスタックを書いてみる。
stack.hs
pop 関数は、Stack a 型に適用するとタプルが返される。タプルの中身は、最初の要素がスタックから pop により取り出した要素で、2 番目は引数に指定した Stack a 型が、pop により要素が一つ減った状態で返される。実装を見ると、
実際は新しくスタックを作って返しているのがわかるけれど、引数と返される値だけを見るならば、この関数によって状態が変更されたと見なすことができる。値を更新できない関数型言語による状態の変更の模倣なので、これを状態の変更だと見なすかどうかは解釈の問題。
スタックの二つの要素を足し合わせる関数
では、状態の変更であると見なしたとして、 pop 関数とモナドはどう関係するのだろうか？ここからは Wikibooks の 05:13, 27 October 2008 の説明に沿いつつ、スタックでの場合を考えてみる。
最初に先ほど定義したスタックを別のモジュールから使う。Stack.hs と同じ階層にファイルを新しく作成し次のように記述。
import Stack
これで 変数 s を出力させると以下の通り。
Stack [5,4,3,2,1]
(以後この変数 s を使用する。)
sumTwoElem 関数
このスタック s に対し、「二つ要素を取り出して、足し合わせる関数」 sumTwoElem を定義する。ただし、スタックの要素は加算可能な Num クラスのインスタンス。
sumTwoElem :: Num a => Stack a -> a
sumTwoElem stack = (fst $ pop stack) + (fst $ pop stack)
…としてはダメ。 (+_+) これでは同じ状態のスタックから pop して要素を取り出しているので、 5 + 5 => 10 という結果に。 pop 関数を一度適用した後のスタックから pop しなければならない。
let 式を使って sumTwoElem を書き直す。
sumTwoElem :: Num a => Stack a -> a
sumTwoElem stack = let (x1, stack') = pop stack
(x2, _) = pop stack'
in x1 + x2
手続き指向的なたとえで言うなら、let 式は計算の結果を一時的に蓄え、後の計算で利用するためのもの。pop stack の結果に変数を束縛し、それを 2 回目の pop 関数の適用において参照。let 式は計算の依存関係を作り出しているが、それはつまり計算の前後関係を意味している。
次に上記 sumTwoElem 関数を、pop 関数のように、結果を返したときのスタックの状態も同時に返すように実装にする。
sumTwoElem :: Num a => Stack a -> (a, Stack a)
sumTwoElem stack0 = let (x1, stack1) = pop stack0
(x2, stack2) = pop stack1
in (x1+x2, stack2)
スタック s に適用すると結果は、
(9,Stack [3,2,1])
関数の抽象化
さて、ここからが混乱の元であったのと同時に興味深いところ。
Of course, we are Haskell programmers: if there are common patterns or boilerplate in our code, we should search for a way to abstract and capture them in a higher order function.
(Haskell/Understanding monads - Wikibooks, collection of open-content textbooks より)
はじめこれを読んだとき、「これ以上どこをどう抽象化すればええっちゅ～ねん」 (@_@;) と思ったけれど。
sumFourElem 関数
ここで、先ほどの sumTwoElem 関数に戻り、「4 回 要素を pop し、足し合わせる関数」に変更する。
sumFourElem :: Num a => Stack a -> (a, Stack a)
sumFourElem stack0 = let (x1, stack1) = pop stack0
(x2, stack2) = pop stack1
(x3, stack3) = pop stack2
(x4, stack4) = pop stack3
in (x1+x2+x3+x4, stack4)
抽象化、一般化
関数の抽象化とは、具体的なものを一般的なもので置きかえ、その結果、一般的なものから具体的なものを導き出せる状態にすること。その意味からすると、真っ先に上記の pop という具体的な関数を、関数の引数として渡せるように変更することが思い浮かぶ。
sumFourElem' :: Num a => (Stack a -> (a, Stack a))
-> Stack a
-> (a, Stack a)
sumFourElem' f = \stack0 ->
let (x1, stack1) = f stack0
(x2, stack2) = f stack1
(x3, stack3) = f stack2
(x4, stack4) = f stack3
in (x1+x2+x3+x4, stack4)
(変更のついでに、第 2 引数 stack をラムダ抽象の引数にした。)
じぃ～と見ていると (@_@)、繰り返し表われるパターンがなんとなく見えてくる。
まず、最初に目がいくのは、
(x, stack○’) = f stack○
という形の羅列。上から下へと全く同じような格好の文字が並ぶ。
関数を適用する流れに目をやると、各々の f の前後関係に一定のパターンがあることに気がつく。下図の赤の矢印に注目すると、関数 f が適用する対象は、最初の stack0 を除けば、直前の関数 f の適用の結果、状態が変化したスタック。(もちろん let 式なので、上から下へと順番に並べているのは便宜的なもの。)
これに対して、どのように抽象化すればいいのだろう？
おもしろいと思ったのは、先ほどのように適用する関数の一般化を考えるのではなく、関数の適用の流れに注目するところ。関数の適用を繰り返すのを見て、二つの関数のつなげ方を部品として取り出そうとするその発想。
2 つのものをつなぐこと
ところで、なぜ二つの間のつなげ方を考えるのか？ 3つ、4つではなくてなぜ二つなのか？それは、二つのもののつなげ方が決まっていれば、同じものをつなげる限り、下図のように同様な方法でどんどんつなげていけることが理由。当り前のことだけれど、つなぐということに関しては、二つの間のつなげ方がプリミティブであるということ。
続けて上図のたとえを使うなら、個々の要素を関数に見立て、左からの入力が右へと出力される装置であるとイメージする。同じものを 2つ 3つとつなげた場合、1 つのときと比べて入力から出力までの距離は長くなるが、その入口と出口の形は同じ。要素をつなぐ関数の型を考えるときに、このメタファーを思い出すこと。同じものをつなげられるようにするには、つなぎがどのようであれば良いのか？
ここまでのコード
mainbak00.hs
二つの関数をつなぐ関数
では、上記の関数 f のような型の関数を二つつなげる関数を考える。
ただし、最初は先ほどの sumFourElem’ 関数の青色の点線部分である x1 ~ x4 の扱いについては考えない。ここでは便宜的に、最後に適用された関数の結果を返すように実装しておく。
Stack a -> (a, Stack a) である型の関数をつなげる関数 comb は以下の通り。 (cf. Meet the Monads。この関数が Monad の >>= に相当。) 実装するときに思い起すことは、先ほど 4 回 pop を繰り返した sumFourElem を書いたとき、各々の pop は何に対して適用したのか？ということ。直前に適用された関数の結果に対して、次に続く関数は適用した。
comb :: (Stack a -> (a, Stack a))
-> (Stack a -> (a, Stack a))
-> Stack a -> (a, Stack a)
comb m n = \stack0 ->
let (_, stack1) = m stack0
(x, stack2) = n stack1
in (x, stack2)
comb 関数の引数 m, n は、sumFourElem’ 関数において、スタックに連続して適用する二つの関数に相当する。スタックへの適用は m が n に先行すると想定。よって、stack0 に m を適用した結果である stack1 に対して関数 n を適用している。今回は、返り値のタプルの第 1 要素はどうでもよく、第 2 要素が関数 n を stack 1 に適用した結果であることが重要。
ちなみに、この comb 関数をはじめて見たとき、返す関数の型に疑問を持った。 pop のような関数をつなぎたいのだから、第１引数と第 2 引数が
Stack a -> (a, Stack a)
であることは理解できる。しかし、なぜ、つないだ結果がまた同じ型になると考えるのか？それはそうなるように意図して作成した関数だからなのだけれど、であるなら、「なぜそうなるように型を決めたのか？」ということが引っかかった。これは当初先ほど示したメタファーを頭の中に描いていなかったことによる。
comb 関数を使う
では、comb 関数を使って pop を 2 つつなげ、それをスタック s に適用してみる。
(comb pop pop) s -- (4,Stack [3,2,1])
3 つつなげると、
(comb (comb pop pop) pop) s -- (3,Stack [2,1])
これ以上つなげると括弧で読みにくくなるので、関数を二項演算子のように扱う。
pop `comb` pop `comb` pop $ s
これで、comb 関数によってつなげられた関数内において、関数に適用されたスタック s が、あたかも「状態」を保っているかのように連続して関数が適用されることになった。
このメリットは、comb 関数という「つなぎ」を担当する関数を部品化しておくことにより、関数をつなげるとき、一々個々のつなげ方の詳細を書かなくて済むようになること。先ほど述べたように、2つの間のつなげ方を定めておけば、同じものをつなぐ限りどれだけつないでも同じ「つなぎ」を使えば済む。
ここまでのコード
mainbak01_00.hs
つなぎを変更
ここでスタックの「二つ要素を取り出して、足し合わせる関数」の問題に戻る。今定義した comb を少し変更。つなぎの部分で要素を足し合わせてみる。
comb :: Num a =>
(Stack a -> (a, Stack a))
-> (Stack a -> (a, Stack a))
-> Stack a -> (a, Stack a)
comb m n = \stack0 ->
let (x1, stack1) = m stack0
(x2, stack2) = n stack1
in (x1+x2, stack2)
このつなぎを使って、
pop `comb` pop $ s -- (9,Stack [3,2,1])
3 つつなげるなら、
pop `comb` pop `comb` pop $ s -- (12,Stack [2,1])
加算を一般化
しかし、これでは要素を足し合わせることしかできない。つなぎの部分で加算に固定されている。これを一般化してみる。
comb :: (Stack a -> (a, Stack a))
-> (Stack a -> (a, Stack a))
-> (a -> a -> a)
-> Stack a -> (a, Stack a)
comb m n f = \stack0 ->
let (x1, stack1) = m stack0
(x2, stack2) = n stack1
in (f x1 x2, stack2)
加算から関数の適用へと変更したので、制約 Num a が必要がなくなった。これを使い、
(pop `comb` pop) (+) $ s -- (9,Stack [3,2,1])
今度は 3 つつなげ、先ほどではできなかった計算を試してみる。
((pop `comb` pop) (+) `comb` pop) (*) $ s -- (27,Stack [2,1])
関数を引数に指定できるようになり、先ほどより柔軟性が増したと言える。
ここまでのコード
mainbak01_01.hs
できない計算
しかし、問題はつながれた関数同士の結び付きが強いこと。3 つつなげた場合を考えると、
(5 + 4) * 3 => 27
渡した二項演算子 +, * は隣り合った要素間でしか適用できない。例えば、数字 5, 4, 3 の順で上記 pop 関数でスタックから取り出し、comb 関数でつなげる限り以下のような計算を作り出せない。
(5 + 3) * 4
つまり、つなぎの部分に関数を渡すということは、つなぎに固定されるという点で柔軟性がない。これを克服するために、関数をつなげた後、要素を取り出す pop 関数だけ計算を先に行い、その結果を取りまとめて要素を足し合わせるような計算を後回しにできないだろうか？
クロージャ
ここで思い出すのが「カリー化」の話。
例えば、引数を加算する関数 add 。
add x y = x + y
これは次のように書ける。
add = \x y -> x + y
また次のようにも。
add = \x -> \y -> x + y
関数 add に引数を一つ渡すと、引数を一つ取る関数が返される。例えば、値 5 に add を適用したとき、次のようなイメージができる。
add = 5 –> \y –> 5 + y
add 5 と適用したときの引数 `5’ は、返される関数の中に埋め込まれる。返される関数 \y –> 5 + y の立場で考えてみれば、`5’ は自分の伺い知ることのできる範疇の外からやってくる値。で、この値がポイント。
上記の関数を見ると、無名関数の中に無名関数が閉じ込められている。引数 x は内側の関数から参照できる変数。add 5 と適用した時点で、内側の関数の x は決定する。
もう少し複雑な例で確認しておく。
hoge = \x ->
let a = x + 10
in \y ->
x + y + a
内側の関数は、外側の値を参照できている。
念のためもっとネストさせてみると、
piyo = \x ->
let a = x + 10
in \y ->
let b = x + y + 100
in \z ->
x + y + z + a + b
これもちゃんと動作する。
自由変数
Closure – HaskellWiki によると、
A closure, the opposite of a combinator, is a function that makes use of free variables in its definition. It 'closes' around some portion of its environment. for example
f x = (\y -> x + y)
f returns a closure, because the variable x, which is bound outside of the lambda abstraction is used inside its definition.
上記 free variables とは、
プログラミングにおいては、自由変数とは関数の中で参照されるローカル変数や引数以外の変数を意味する。
(自由変数と束縛変数 – Wikipedia より)
上記の関数 f の右辺の無名関数内の変数 x は、無名関数内において参照されるローカル変数でも引数でもない変数。よって、その無名関数は自由変数を含むのでクロージャ。先ほどポイントである「値」と言ったのは、「環境」と呼ばれる。
関数を適用する関数
上記を頭の隅に置きつつ、先ほどの計算に戻る。
(5 + 4) * 3
これを分解するための apply 関数を導入。定義は以下の通り。
apply :: a -> (a -> a) -> a
apply x f = f x
第１引数に渡された値に対して、第２引数で与えた関数を適用するという内容。 (これは Monad の >>= の型を真似て作った。)
普通、関数と言ったら、直接関数を値に適用する。 apply 関数の引数で言えば、第 2 引数の関数を直接第１引数の値に適用。図示するなら、下図のように青色の部分が関数で、黄色が値とイメージできる。
これに対して、apply 関数は、関数と値との間を取り持つ。
(5 + 4) * 3 を apply 関数を使って表現するなら、
5 `apply` (+ 4) `apply` (* 3)
これを見ると、apply 関数が計算を構成するつなぎの役割をしている雰囲気が伝わってくる。先ほどの図のように書くなら、
次に、セクションの部分を無名関数に置き換えると、
5 `apply` (\x -> x + 4) `apply` (\x -> x * 3)
`apply` の左側の値が右側に投入されている感じが明確になる。
しかし、このままでは相変らず `apply` のつなぎ方に全体の計算が固定されてしまっている。左側の値は常に真横の右隣の中で使われるだけ。
クロージャで外側の変数を参照
そこで先ほどのクロージャによる方法で書き直す。
5 `apply` (\x -> 4 `apply` (\y -> 3 `apply` (\z -> (x + y) * z)))
下図は、無名関数を点線で表現し、その中にあるものが内部関数であると想定。内部関数はその外側の関数の値を参照できる。
ところで、無名関数は「できるだけ右へ拡張される」ように解析されるので、括弧を省略できる。
5 `apply` \x -> 4 `apply` \y -> 3 `apply` \z -> (x + y) * z
複数行に渡って書いてみるなら、
5 `apply`
\x -> 4 `apply`
\y -> 3 `apply`
\z -> (x + y) * z
apply の定義に戻って、具体的に何が行われるのかを見ていくと、最初の値 `5’ に適用すると、その定義より、続く無名関数の引数として適用されることになる。その様子を書くと、
4 `apply`
\y -> 3 `apply`
\z -> (5 + y) * z
続いて `4’
3 `apply`
\z -> (5 + 4) * z
更に `3’
(5 + 4) * 3
となる。
関数の内側へ内側へと引数を渡していき、最内の関数において全ての引数を参照して計算を組立てるというイメージ。
更に戻って、先ほど不可能だった以下の計算、
(5 + 3) * 4
を構成したいなら、
5 `apply`
\x -> 4 `apply`
\y -> 3 `apply`
\z -> (x + z) * y
ポイントは、内側の関数から外側の関数にアクセスできるので、好き勝手できること。
つなぎでクロージャ
apply :: a -> (a -> a) –> a を真似して comb 関数を変更する。
comb :: (Stack a -> (a, Stack a))
-> (a -> (Stack a -> (a, Stack a)))
-> Stack a -> (a, Stack a)
comb m n = \stack0 ->
let (x1, stack1) = m stack0
(x2, stack2) = n x1 stack1
in (x2, stack2)
ここで 関数 n の型は、前の comb 関数の n とは型が違うことに注意。
とりあえず、最初は使えるか試してみる。型だけ合わせることを考えて…
pop `comb` (\x1 -> pop) $ s -- (4,Stack [3,2,1])
当然ながらエラーはでないけれど、pop が 2 回適用されただけ。
では、徐々に変更してみる。pop した要素を `comb` の右側の無名関数に渡し…
pop `comb` (\x1 -> pop
無名関数の中で無名関数を記述する。その際、pop して要素を `comb` で右側の無名関数に渡し…
pop `comb` (\x1 -> pop `comb` (\x2 –>
最後は、返される型 Stack a -> (a, Stack a) に合わせると同時に外側の変数を参照して計算を組立てる。
pop `comb` (\x1 -> pop `comb` (\x2 -> (\stack -> (x1 + x2, stack)))) $ s
実行すると結果は、
(9,Stack [3,2,1])
括弧を省略するなら、
pop `comb` (\x1 -> pop `comb` \x2 -> \stack -> (x1 + x2, stack)) $ s
ret 関数
ところで、最後は型を合わせるために Stack a -> (a, Stack a) に値を投入した。これを毎回書くのは面倒なので、stack の内容は変化させない ret 関数を導入。(Monad クラスの return に相当。)
ret :: a -> (Stack a -> (a, Stack a))
ret x = \stack -> (x, stack)
書き直すと、
pop `comb` (\x1 -> pop `comb` \x2 -> ret(x1 + x2)) $ s
先ほど構成できなかった計算を複数行で書くなら、
print $ pop `comb` (\x1 ->
pop `comb` \x2 ->
pop `comb` \x3 ->
ret $ (x1 + x3) * x2) $ s
ここまでのコード
mainbak01.hs
module Mainbak01 where
import Stack
comb :: (Stack a -> (a, Stack a))
-> (a -> (Stack a -> (a, Stack a)))
-> Stack a -> (a, Stack a)
comb m n = \stack0 ->
let (x1, stack1) = m stack0
(x2, stack2) = n x1 stack1
in (x2, stack2)
ret :: a -> (Stack a -> (a, Stack a))
ret x = \stack -> (x, stack)
comb_ :: (Stack a -> (a, Stack a))
-> (Stack a -> (a, Stack a))
-> Stack a -> (a, Stack a)
comb_ m n = m `comb` (\_ -> n)
main = do
print $ pop `comb` (\x1 -> pop) $ s
print $ pop `comb` (\x1 -> pop `comb` \x2 -> ret(x1 + x2)) $ s
print $ pop `comb` (\x1 ->
pop `comb` \x2 ->
pop `comb` \x3 ->
ret $ (x1 + x3) * x2) $ s
関数の型に別名を付ける
それにしても、comb 関数の型が長い。 (+_+)
comb :: (Stack a -> (a, Stack a))
-> (a -> (Stack a -> (a, Stack a)))
-> Stack a -> (a, Stack a)
これを短くしたいなら、型に別名を付ければ良い。スタックの操作に関する関数なので、「スタック操作型」という意味で次のような名前を付けた。関数も型を持つので、type で別名を付けることができる。
type StackOp a = Stack a -> (a, Stack a)
comb を書き直すと、
comb :: StackOp a -> (a -> StackOp a) -> StackOp a
comb m n = \stack0 ->
let (x1, stack1) = m stack0
(x2, stack2) = n x1 stack1
in (x2, stack2)
第１引数の結果に関心がない場合
comb 関数は、第 1 引数の計算の結果を受けて、次の関数の計算に進む。つなげる関数によっては結果を必要としないので、comb 関数を使い comb_ 関数を定義。 ( >> に相当。)
comb_ :: StackOp a -> StackOp a -> StackOp a
comb_ m n = m `comb` (\_ -> n)
渡される値を`_’ で無視。それに伴い第 2 引数の型が変わる。
型は十分か？
ところで、先ほど付けた関数の別名、
type StackOp a = Stack a -> (a, Stack a)
型は本当にこれで十分なのだろうか？
… と言うのは、スタックに適用する関数で、例えば、
「スタックから pop した要素が、特定の基準を満しているかどうか？」
を調べる関数 topis を想定して考える。
第１引数が「特定の基準」を表わす述語、第 2 引数が適用対象のスタック。
topis :: (a -> Bool) -> Stack a -> (Bool, Stack a)
topis p s = let (a, s') = pop s
in (p a, s')
これを comb 関数を使って、
「連続して pop した要素が、全て特定の基準を満しているかどうか」
を判断できる関数を作ってみる。topis を comb に適用するためには、第 1 引数に関数を与えてから渡す。
print $ topis (> 4) `comb` (\x1 ->
topis (> 3) `comb` \x2 ->
topis (> 2) `comb` \x3 ->
ret $ and [x1,x2,x3]) $ s
これを実行してみると結果は… (@_@;)
Couldn't match expected type `Bool' against inferred type `Integer'
Expected type: Stack Bool
Inferred type: Stack Integer
このエラーは、スタックの要素が数字であるのに対して、上記の関数の結果のタプルの第 1 要素が真偽値のため。これを解決するためには、スタックの要素の型と、スタックに対して操作する関数が返す型 (タプルの第 1 要素) が異なってもいいように、次のように別名を修正しなければならない。
type StackOp a b = Stack a -> (b, Stack a)
これに伴い、comb, comb_, ret 関数の型を変更する。 ( cf. 余談 (失敗) )
comb :: StackOp a b -> (b -> StackOp a c) -> StackOp a c
comb m n = \stack0 ->
let (x1, stack1) = m stack0
(x2, stack2) = n x1 stack1
in (x2, stack2)
comb_ :: StackOp a b -> StackOp a c -> StackOp a c
comb_ m n = m `comb` (\_ -> n)
ret :: b -> StackOp a b
ret x = \stack -> (x, stack)
これで上記 topis 関数を使った関数を実行できるようになった。
push, empty もつなげられるように変更
ところで、Stack モジュールの push 関数は次のような定義だった。
push :: a -> Stack a -> Stack a
push x (Stack xs) = Stack (x:xs)
これに対して、comb 関数の型は、
comb :: StackOp a b -> (b -> StackOp a c) -> StackOp a c
別名の定義は、
type StackOp a b = Stack a -> (b, Stack a)
上記の型に合わせるには push 関数を変更する必要がある。
push' :: a -> Stack a -> ((), Stack a)
push' x (Stack xs) = ((), Stack (x:xs))
これで push’ 関数の第 1 引数に値を適用すると、StackOp a b 型の値を受け入れる関数に渡せるようになった。
例えば、「適用するスタックを変化させない」関数を定義してみる。
print $ pop `comb` push' $ s
print $ push' 10 `comb_` pop $ s
結果は、
((),Stack [5,4,3,2,1])
(10,Stack [5,4,3,2,1])
連続して push するなら、
print $ push' 10 `comb_` push' 9 `comb_` push' 8 $ s
結果は、
((),Stack [8,9,10,5,4,3,2,1])
empty 関数も同じように StackOp a b 型に合うように変更してみる。
empty' :: Stack a -> ((), Stack a)
empty' _ = ((), Stack [])
これを使って、
print $ empty' $ s
print $ push' 10 `comb_` empty' `comb_` push' 0 `comb_` push' 1 $ s
結果は、
((),Stack [])
((),Stack [1,0])
ここまでのコード
stack.hs
mainbak03.hs
余談 (失敗)
関数の型に別名を付けたときに、型を間違えて修正したところより。
(>>=) の型を見誤る
実は当初、間違えて以下のように関数の型を定義していた。
comb :: StackOp a b -> (b -> StackOp a b) -> StackOp a b
comb_ :: StackOp a b -> StackOp a b -> StackOp a b
これに気がつかず、push’ 関数を使ってエラーが… (@_@;)
Couldn't match expected type `()' against inferred type `Integer'
Expected type: Stack ()
Inferred type: Stack Integer
原因に ずーーーーーーっと 気がつかなくてハマった。(+_+)
最初は 「クラスで型宣言せずに、type を使って別名にしているのがダメなのかなぁ ?」 と思い、newtype 宣言で、
newtype StackOp a b = StackOp {run :: Stack a -> (b, Stack a)}
Monad クラスを真似て、
class MyMonad m where
comb :: m a -> (a -> m a) -> m a
ret :: a -> m a
instance MyMonad (StackOp a) where
ret x = StackOp $ \stack -> (x, stack)
m `comb` n = StackOp $ \stack0 ->
let (x1, stack1) = run m stack0
(x2, stack2) = run (n x1) stack1
in (x2, stack2)
このときも、まだ (>>=) を真似たつもりの comb 関数の型定義を間違えているのに気がつかず。。(+_+)
間違えたままで、上記を使った関数を定義。スタックの要素を二つ足し合わせる関数 popop 。
poppop = StackOp pop `comb` \x1 ->
StackOp pop `comb` \x2 ->
ret $ x1 + x2
ここでは問題が表面化しない。なぜなら、poppop 関数において扱っているスタックの要素と、ret 関数によって返した結果のタプルの第 1 要素が同じ Integer 型であるため。
しかし、次にスタックから pop して push する関数 poppush を定義してエラーが発生。
poppush = StackOp pop `comb` (\x -> StackOp (push' x))
poppush' = StackOp pop `comb` (StackOp . push')
エラーの内容は、
Couldn't match expected type `()' against inferred type `Integer'
Expected type: Stack ()
Inferred type: Stack Integer
このエラーが発生する理由は、Stack モジュールの push’ の型を見直せば、
push' :: a -> Stack a -> ((), Stack a)
返ってくる結果のタプルの第 1 要素と、スタックの要素の型が異なるから、comb 関数を push’ に適用できない。
Monad の (>>=) の型を見直すと、
(>>=) :: forall a b. m a -> (a -> m b) -> m b
このときになって、やっと次のように見間違えていたことに気がついた。 パタッ(o_ _)ｏ~†
(>>=) :: m a –> (a –> m a) –> m a
よって、MyMonad クラスの comb 関数の型を次のように修正する必要がある。
comb :: m a -> (a -> m b) -> m b
これで poppush 関数が定義できた。
クラスで型宣言してオーバーロードする方が型がスッキリ
次に、(>>) に相当する comb_ 関数も定義してみる。
comb_ :: StackOp a b -> StackOp a b -> StackOp a b
comb_ m n = m `comb` (\_ -> n)
ここでもまた最初、間違えに気がつかなかった。(+_+)
この関数を用いて「スタックの要素を 2 回 push’ する」関数を定義。
pushpush = StackOp (push' 10) `comb_` (StackOp (push' 9))
問題なし。
次にスタックの要素を pop し、それが特定の基準を満しているかチェックする topis 関数を使って、
print $ run (StackOp (topis (> 4)) `comb` (\x1 ->
StackOp (topis (> 3)) `comb` \x2 ->
StackOp (topis (> 2)) `comb` \x3 ->
ret $ and [x1, x2, x3]))$ s
これまた問題なし。
しかし、次に「スタックを pop して push’ する」関数を定義してやっと問題が表面化。
pushpop = StackOp (push' 10) `comb_` StackOp pop
エラーがでる理由は、push’ の返すタプルの第 1 要素が () であるのに対して、pop はこの関数が適用されるスタックの要素の型に依存するため、先ほど定義した comb_ 関数の型に合わないから。comb_ 関数の型を次のように修正しなければならない。
comb_ :: StackOp a b -> StackOp a c -> StackOp a c
クラスで型宣言した方がシンプル
それにしても、使う型変数が 2 つ以上だと、慣れてないと見落してしまう。 (+_+) これは、comb_ 関数を MyMonad クラスとは独立に定義したために、型の定義が複雑になったことによる。
MyMonad クラスの型定義において comb_ 関数を追加するなら、
comb_ :: m a -> m b -> m b
この関数を StackOp a を MyMonad のインスタンス宣言に追加する。
m `comb_` n = m `comb` (\_ -> n)
こちらの方が型変数が少ない分、型の間違えに気づきやすいなぁ～。 ^^
ここまでのコード
mainbak05.hs
関連記事
まずは Maybe a 型に対応したクラスを書く。Java ではパターンマッチによって、コンストラクタで作った中身を取り出せないので、Maybe<T> クラスに fromJust メソッドを実装。これにより Just で包んだ中身の値を取り出す。
