計算の合成

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 編 に続く ... のか? )