Haskell の State モナド (1) - 状態を模倣する | すぐに忘れる脳みそのためのメモ

昔、モナドがよくわからなかったので、さまよっていたら、

… ネットで見たMonadの説明で一番私がわかりやすいと思ったのは、Wikibooksの説明。Hello World!がブラックボックスな人は、是非一読を。

(404 Blog Not Found:Haskellで一番難しいのはより)

最初にこの Wikibooksの説明を読んだのは去年の 11 月頃。そのときの文書のバージョンは 05:13, 27 October 2008 で、今は内容が随分増えている。前の文書は、現在の Haskell/Understanding monads/State に相当するようだ。

http://en.wikibooks.org/wiki/Haskell/Understanding_monads/State

Understanding
monads/State via kwout

ところで、上記の解説を最初読んだとき全く意味がわからなかった。 (@_@;) 「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 は使わずに自前で実装する。

http://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF

スタック - Wikipedia via kwout

スタックにおける状態の変化

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

        
view raw This Gist brought to you by GitHub. 

関数の型に別名を付ける

それにしても、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

6コメント:

Unknown さんのコメント...: おかげで、やっとモナドを解れた気がします。ありがとうございました。「Monad は内部状態を保持した closure 関数を、別の関数と一般的に受け渡しする機構」だわ。

comb, comb_ を >>=, >> に書き換えたものが作れたら、もっと分かりやすくなると思います。時間があるときに挑戦してみてもらえれば助かります。

自分でやってみたのですが、下のようになりうまくいきません。

//@@
略

-- Monad を真似したクラス
class MyMonad m where
-- comb :: m a -> (a -> m a) -> m a -- これ間違い
--comb :: m a -> (a -> m b) -> m b
(>>=) :: m a -> (a -> m b) -> m b
ret :: a -> m a
comb_ :: m a -> m b -> m b -- クラスにおいて型を定義していると見間違えにくい。

instance MyMonad (StackOp a) where
ret x = StackOp $ \stack -> (x, stack) -- 関数:\stack -> (x, stack) を返している
--m `comb` n = StackOp $ \stack0 -> --(>>=) :: m a -> (a -> m b) -> m b
m >>= n = StackOp $ \stack0 -> --(>>=) :: m a -> (a -> m b) -> m b
let (x1, stack1) = run m stack0 -- (m stack0) is run type
(x2, stack2) = run (n x1) stack1 -- n(x1) stack1 is run type
in (x2, stack2)
--m `comb_` n = m `comb` (\_ -> n) --m >> k = m >>= \_ -> k
m `comb_` n = m >>= (\_ -> n) --m >> k = m >>= \_ -> k
-- 上での ret, comb`, comb_` が Stackop 型変数を取る関数として使われている

-- 連続して pop
poppop = StackOp pop >>= \x1 ->
StackOp pop >>= \x2 ->
ret $ x1 + x2

-- pop して push
poppush = StackOp pop >>= (\x -> StackOp (push' x))

poppush' = StackOp pop >>= (StackOp . push')

-- 連続して push
pushpush = StackOp (push' 10) `comb_` (StackOp (push' 9))

-- pop した要素が述語を満しているか？
topis :: (a -> Bool) -> Stack a -> (Bool, Stack a)
topis p s = let (a, s') = pop s
in (p a, s')

-- push して pop
pushpop = StackOp (push' 10) `comb_` StackOp pop

main = do
略
//@@@
//copy \#####.### temp.hs /y
//C:\lng\ghc6121\bin\runghc.exe temp.hs
temp.hs:40:20:
Ambiguous occurrence `>>='
It could refer to either `Main.>>=', defined at temp.hs:28:4
or `Prelude.>>=', imported from Prelude
略; 2010年1月22日 10:25
jutememo さんのコメント...: ちょっと細かいところまで見てないのですが、エラーの内容からして MyMonad クラスと Prelude に定義されている (>>=) がバッティングしていると思います。
最初に Prelude に定義されている (>>=) を以下のように import 宣言で遮蔽してるでしょうか？

import Prelude hiding((>>=))

(cf. http://www.sampou.org/haskell/report-revised-j/modules.html#sect5.3.1); 2010年1月22日 12:24
Unknown さんのコメント...: 子馬さん、アドバイスありがとうございます。御指摘の行を追加するだけで実行できるようになりました。
mainbak3.hs mainbak5.hs とも comb:>>=, comb_:>> の置き換えをするだけでした。

Prelude の宣言とぶつかっていることは分かっていたのですが、今年から Haskell を動かし始めたものには、その対策方までは調べられませんでした。助かりました。

----------------
mainbak3.hs のほうが closure の自由変数に状態が残されていく様子を楽に掴めます。mainbak5.hs の方は StackOp を newtype にすることで monad 構造を明示してくれます。Upper world と real world を行き来する構造を明示してくれます。

----------------
後は、この upper world, real world の行き来を圏論での具体例としてモデル化することに挑戦してみます。このモデル化ができれば monad を十分に理解したといえると思います。これが旨くいったら報告しますので見てやってください。; 2010年1月23日 9:00
kibble (quetzal egg) id さんのコメント...: covariance/contravariance is a little more general than that.
Basically, whenever you have two directed graphs that implement a composition interface, you can consider a map between the graphs F : C -> D.

Covariance means that edges x -> y in C get mapped to edges Fx -> Fy in D.
Contravariance means that edges x -> y in C get mapped to edges Fy -> Fx in D.

If you make a graph whose vertices are types and whose edges are subtyping relationships, and consider maps from this graph to itself, you recover what they talk about in the video.

If you want, a contravariant map C -> D, is a covariant map from C -> D^op, where D^op is the graph D with all arrows pointing in the opposite direction.

(I'm being slightly imprecise to avoid the category theory).
Show less; 2018年1月2日 0:59
xcom 2 war of the chosen console commands さんのコメント...: This was just brilliant, especially the diagrams. None of the tutorials I've read ever thought of calling the right operand of bind a "monad creator," but that's exactly what it is! It makes perfect sense. Thanks for all the insights. Who knows if we'll ever see part 3 on the continuation monad! One can hope.; 2018年2月6日 22:39
why do chia seeds gel さんのコメント...: This was just brilliant, especially the diagrams. None of the tutorials I've read ever thought of calling the right operand of bind a "monad creator," but that's exactly what it is! It makes perfect sense. Thanks for all the insights. Who knows if we'll ever see part 3 on the continuation monad! One can hope.; 2018年3月5日 19:25

コメントを投稿

すぐに忘れる脳みそのためのメモ

2009年10月14日水曜日