Haskell Advent Calendar 2014 の22日目のエントリーです。
導入
Haskell では計算を持った値であることを型で表わすことができる。 とくに計算を持っていない型は Int や a のような形をしている。 しかし例えば Maybe Int ならば、結果の型 Int の値は得られるかもしれないし得られないかもしれない。 Functor f => f a なら、結果の型 a を得るためには何らかの計算 f が必要だと考える。
プログラムを書くときには結果の値を計算するにあたって、様々な計算を利用する。 複数の計算をうまく組み合わせる方法が重要だ。
計算の連続適用
型 a に計算 h を適用したものにさらに計算 g を適用し、さらに f を適用すれば f (g (h a)) である。
ここでは、どんな計算を適用するかだけを考えることにして、単に fgh の様に並べて書くことにしよう。
例えば fgh のような3種類の計算を欲しい順に欲しいだけ適用するには、 fghfghfgh ... というように並べ、さらに、f, g, h のそれぞれに、実は何もしない計算があればよいことになる。 それぞれを Id_f, Id_g, Id_h と書くことにし、fghfgh の適用の中に Id が混ざっているものを考えれば、
f Id_g h Id_f g I_h == fhg
という様に結果的に欲しい計算を欲しい順に適用できる。
計算の直和
また、別のアプローチもある。 仮に計算 f または g を適用することを表現するのに f+g と書くことにしよう。 f または g または h を適用するのは f+g+h である。
これを繰り返し適用すると、
(f+g+h)(f+g+h) = ff + fg + fh + gf + gg + gh + hf + hg + hh
となる。
これを繰り返し回数を増やしていけば、繰り返し回数だけやはり欲しい計算を欲しい順に適用できる。
Monad Transformer
前者のアプローチの実装例が Monad Transformer である。 Monad Transformer の場合は transformer の中のモナドを持ち上げる (lift する) と 計算が内側に入ることになる ( StateT や ReaderT は違うと気がつくかもしれない。 だが f (s -> (a, s)) -> s -> f (a, s) や f (r -> a) -> r -> f a は \mf s -> fmap ($ s) mf とやると簡単に作り出せることがわかるので、 少なくとも Functor の計算が Monad Transformer の力を持っていることを認めて話を先に進める ) 。
Monad Transformer で作り出した、複数の計算の複合した Monad は、 (>>=) で繰り返し適用することができる。 そして何もしない計算に相当するのは id や lift である。
Monad Transformer を利用することで、計算を欲しいだけ欲しい順に適用できる。
Data Types á la carte
後者のアプローチは Data Types á la carte や Extensible Effects(実装) である。
ここでは Data Types á la carte の方をとりあげる。 Data Types á la carte は
data (f :+: g) a = Inl (f a) | Inr (g a)
と定義したときに、f, g が Functor であるときには f :+: g も Functor になることを利用する。 残念なことに f, g が Monad であったとしても f :+: g は Monad になるとは限らない。 Monad であれば (>>=) で繰り返し適用することができたが、こちらではそうはいかない。
ではどうするのか。計算の繰り返しのデータ型を定義することで対応する。
data Expr f = In (f (Expr f)) foldExpr :: Functor f => (f a -> a) -> Expr f -> a foldExpr f (In t) = f (fmap (foldExpr f) t)
Expr の定義は一見、いくらでも計算が出てくるので、本当に停止するのか心配になる。 が、foldExpr は各計算から結果を導く関数 ( f a -> a ) が停止するなら全体が停止するとも読める。
Data Types á la carte の前半では結果が Int になるような evaluator の例が紹介されている。
class Functor f => Eval f where evalAlgebra :: f Int -> Int eval :: Eval f => Expr f -> Int eval expr = foldExpr evalAlgebra expr
このようにして、Functor の直和を利用することで、計算を欲しいだけ欲しい順に適用できる。
ここに至ると、この Functor を Free Monad に入れたらどうなるのかが気になるところだろう。 しかし、今回は survey の時間が十分に取れなかったので、このあたりにしておきたい。
( Free Monad 編、Codensity, Yoneda, Lens 編 に続く ... のか? )
