Monad Note

Wadler, P. : Monads for functional programming

上記の論文を読んで、自分が忘れないように取ったノートと思ってください。

準備体操

処理順

全てが遅延評価の言語では、計算の処理順は処理系の式の展開方法に寄るためパッと見では特定できません。それでも見た目だけは処理順があるように書けます。

func = let x = ex1 in y = ex2 x in ex3 y

これは、ex1、ex2、ex3の順で計算していると思って実用上問題ないです。実際には入出力が絡まなければどんな順序で計算されてようが処理速度以外では区別できないのですが。

状態

見た目だけでも計算順序が作れれば、状態をパラメータとして明示的に渡していくことで変数を書き換えていくような真似ができます。

func = let (v, x) = (0, ex1) in
       let (v', y) = (v + 1, ex2 x) in
       (v' * 2, ex3 y)

Adaで書けばこんな状態。

type T is record V, Result: Integer; end record;
function func return T is
  v_x : T := T'(0, ex1);
  vd_y : T := T'(v + 1, ex2(v_x.Result);
begin
  return T'(vd_y.V * 2, ex3(vd_y.Result));
end func;

う～ん、Adaってば冗長。 C言語以上に記号の塊みたいなHaskellと比べると際立ちますな。

というわけであくまで真似だけ、なのですが、末尾再帰なので古いv(,v'...)は二度と使われません。ならばこれはもう変数と思っていいのではないか？という話。

で、v(,v'...)を巧妙に隠します。

type T a = (Int, a)
func :: T a

型の前にTを付けると、隠された整数が一個くっついてくるという寸法。これで、先の例のように毎回(v, _)な受け取り方をするのではなく、隠された整数を意識せずにすめば、完璧に変数でしょう。

type T a = (Int, a)

first :: a -> T a
first ex = (0, ex)

next :: T a -> (a -> b) -> T b
next (v, ex1) ex2 = (v, ex2 ex1)

*A> (first 1) `next` (\x -> x * 2)
(0,2)

普通の式と比べて、単に0がくっついてくるだけです。

nextUsingV :: T a -> (Int -> a -> b) -> T b
nextUsingV (v, ex1) ex2 = (v, ex2 v ex1)

nextModifyV :: T a -> (Int -> a -> T b) -> T b
nextModifyV (v, ex1) ex2 = ex2 v ex1

*A> ((first 1) `nextUsingV` (\v x -> 3 * (x + v))) `next` (\y -> y * 3)
(0,9)
*A> ((first 1) `nextModifyV` (\v x -> (x, v + 1))) `nextUsingV` (\v x -> x + v)
(1,2)

こんな風にすればvを途中で使ったり書き換えたりできます。

で、このような状態渡しを行うために用意された枠組みがモナドです。

Monadクラス

HaskellのclassはOOPLのclassとは微妙に違う概念です。どっちかといえば、「このテンプレート関数に渡す型Tは、operator > が必須です」みたいな。データ型がどんな関数を持っているかのセットと言えばいいでしょうか。で、クラスの条件を満たす型を、クラスのインスタンスと言ったりします。ややこしい。

ともかく、先の例のTのような型は、Monadクラスのインスタンスにすれば、構文糖とかで色々と言語側が支援してくれる、というわけです。

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

    m >> k  =  m >>= \_ -> k
    fail s  = error s

四つの関数を揃えればモナドいっちょあがり、ですが、>>とfailにはデフォルト実装が与えられていますので、実際には>>=とreturnだけ書けば他の二つも使えます。これが継承に見える人からは、「HaskellはOOPL」疑惑が囁かれていると風の噂？継承というよりはtemplateの特殊化が相当するはずなのですが、Haskellではtemplate関数とふつーの関数の区別が曖昧なので、見た目継承のように使えちゃうのかな？一段しかできねー継承なんて意味ねー。

インスタンス化はこんな感じ。

data T a = T a
instance Monad T where
  T x >>= f = f x
  return x  = x

0個の状態を持つモナド。(無意味)

型のインスタンス化は単に特定の関数を揃えればいいだけの話なので、後から、この型はこのクラスのインスタンスだと宣言できます。 OOPLと混同すると激しく混乱しますが。

Stateパターン

↑違和感あるなあ…デザインパターンのStateパターンはこの際忘れてください。「オープンソース」も「Windows」も、よく使われる名前に定義や商標を与えるほうが悪い。

論文を参考に、変数一個をもつモナド。

data T a = T (Int -> (a, Int))

peek :: T Int
peek = T (\s -> (s, s))

poke :: Int -> T ()
poke a = T (\s -> ((), a))

eval :: T a -> Int -> a
eval (T e) s = fst (e s)

instance Monad T where
  T x >>= f = T (\s -> let (a, s') = x s in let T b = f a in b s')
  return x = T (\s -> (x, s))

*C> eval (peek >>= return) 1
1
*C> eval (peek >>= poke) 1
()
*C> eval (do a <- peek; poke (a * 2); peek >>= return) 1
2

前の値を受け取って次の値を返す関数を返す関数、として定義することで、全体を、初期値を与えれば色々計算する関数として、無理なく定義できます。 templateとはまた違った方向での、メタプログラミングっぽい…僕がそう思っただけでこれをメタプログラミングと呼ぶかは知りません。

にしても、変数一個じゃ面白くねえな…。

Exceptionパターン

data T a = T a | stopみたいにして、途中stopが返されたら、>>=中でcaseで切り分けて後に続く関数を呼ばないようにすることで例外(つーかbreak文)を実現できます。

>>=毎にエラーチェックなんてのは、昔のBASICコンパイラがON event GOTOを実現する手段みたいで、あんまり効率がいいとも思えないのですけども。処理系側で用意された例外機構なら、表面的にはこんなふうに実装されている顔をして裏でSEHを使って…ってのは可能性として充分アリなので、他にもdata T a = T a | D (a, a) | ... | stopとかやった時のついででもない限り使う必要はないかも。

Outputパターン

(a, String)みたいなデータ構造をとって、それぞれの式がくっつけて返す文字列を、>>=側で全部++して溜め込んでおくというもの。ログ取りに使える…のか？

do構文

a >>= (\x -> b x) は、do x <- a; b x と書けます。
a >> b は、do a; b と書けます。

この構文のおかげで、λ関数を何重にも入れ子にして…なんて目に遭わずに済みます。

IOモナド

IOモナドとはつまり、入出力、要するにHaskellから見て外の世界の状態を表すモナドです。今までの例では状態をHaskellで定義してきましたが、外部の状態を丸ごとモナドとして次々と引き渡している、…と、概念上では考えるわけですな。

型としては、IO a :: World -> (a, World) ということになってます。 Stateです。値が関数なのですね。要するに、main :: IO ()は、巨大なλ式を組み立てるための関数で、処理系はexe = main getWorld (型は((), World)になりますね)を実行している、…と、概念上では考えるわけですな。

実際には、関数型言語以外を使っていれば当然ご存知のように、外の状態なんてものはその都度取得関数を使って得るものです。要するにIOモナドは単なるマーキングです。 FFIを使うと良くわかります。副作用のない単なる定数を返すCの関数は :: IO Int としても単に :: Int としてもどちらでも不都合は無いです。 (副作用のある関数を非IOとしてしまうと、計算順序によってはとんでもないことになるかも) 追加で何かが渡されているなんてことは決してありません。内部でも、関数ポインタを数珠繋ぎに巨大なλ式を…なんて非効率なことはやってない筈です。 IO aの値を配列にして～など特殊なことをやらない限り、手続き型言語と同じようにコンパイルされているはずだと、僕は無根拠に信じています。

[ ]モナド

リストもモナドです。もっとも、リストが状態を持っているわけではないので、モナドになっている理由は単に[a] >>= (\e -> return (f e))と書けるようにするため、じゃないでしょうか。

Prelude> 0 : do x <- [1,2,3] ; return (x * 2)
[0,2,4,6]

do記法も使えます。使えることは当然なのですが、リストの場合ありがたみはいまひとつ。